pith. sign in

arxiv: 1907.07172 · v3 · pith:J6E6S6DAnew · submitted 2019-07-16 · 🧮 math.CO

Ordinal pattern probabilities for symmetric random walks

Hugh Denoncourt This is my paper

Pith reviewed 2026-05-24 20:46 UTC · model grok-4.3

classification 🧮 math.CO
keywords ordinal patternsrandom walksaffine Weyl grouppermutationsprobability distributionssymmetric stepscombinatorial probability
0
0 comments X

The pith

For symmetric random walks, the probability of each ordinal pattern is determined by the size of a weak order interval in an affine Weyl group or by level counts in the permutation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes exact probabilities for ordinal patterns—permutations that capture the relative ordering of values in a sequence—arising from symmetric random walks. For steps uniform on [-1,1], these probabilities equal the normalized size of certain intervals in the affine Weyl group of type A. For Laplace steps, they factor into a product over how often each position appears between consecutive values. This matters because it shows that the pattern frequencies depend only on combinatorial features of the permutation rather than the precise step distribution, at least for broad classes of symmetric continuous distributions.

Core claim

An ordinal pattern occurs with probability |[1,w]|/(2^n n!), where [1,w] is a weak order interval in the affine Weyl group ~A_n, for uniform [-1,1] steps. For symmetric Laplace steps the probability is 1/(2^n prod lev(π)_j). Permutations with consecutive values at most two positions apart occur with the same probability under any symmetric continuous step distribution. For normal steps, probabilities are given by entries in a matrix counting how often pairs i and j lie between consecutive values.

What carries the argument

The weak order interval [1,w] in the affine Weyl group ~A_n, which encodes the combinatorial structure that determines the pattern probability for uniform steps.

If this is right

  • Permutations with consecutive values differing by at most two positions share identical probabilities across all symmetric continuous distributions.
  • Ordinal pattern probabilities for uniform steps are given exactly by the cardinality of weak order intervals divided by 2^n n!.
  • For Laplace steps, the probability factors as the reciprocal of 2^n times the product of level values lev(π)_j.
  • Normal distribution steps yield probabilities via a matrix of pairwise between-consecutive counts.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These combinatorial formulas might allow efficient computation of pattern probabilities without simulation for large n.
  • The connection to affine Weyl groups suggests links to other areas of combinatorics involving Coxeter groups and random walks.
  • Similar techniques could extend to other step distributions or to higher-dimensional walks.

Load-bearing premise

The step distribution must be symmetric and continuous so that the probability of each ordinal pattern factors exactly through the size of a weak order interval or the product of level values rather than depending on the detailed shape of the distribution.

What would settle it

Simulate many symmetric random walks with uniform steps on [-1,1], compute the empirical frequency of a specific ordinal pattern, and check whether it matches the size of the corresponding weak order interval divided by 2^n n!.

Figures

Figures reproduced from arXiv: 1907.07172 by Hugh Denoncourt.

Figure 1
Figure 1. Figure 1: The edge diagram for a permutation and its level cou [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The address of the alcove A containing the point in Example 5.13. The group Aen has generating set s1, . . . , sn+1, where s1, . . . , sn are the same generators from An that reflect about the hyperplanes H0 i i+1. The generator sn+1 reflects about the hyperplane H1 1n . Thus, the action of si is to swap the i-th and (i + 1)-st coordinates of elements of V . The action of sn+1 is to swap the first and last… view at source ↗
Figure 3
Figure 3. Figure 3: The maximum address that is zero on the ideal [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The edge diagram for a permutation and its level cou [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
read the original abstract

An ordinal pattern for a finite sequence of real numbers is a permutation that records the relative positions in the sequence. For random walks with steps drawn uniformly from $[-1,1]$, we show an ordinal pattern occurs with probability $\frac{|[1,w]|}{2^n n!}$, where $[1,w]$ is a weak order interval in the affine Weyl group $\widetilde{A}_n$. For random walks with steps drawn from a symmetric Laplace distribution, the probability is $\frac{1}{2^n \prod_{j=1}^n \mathrm{lev}(\pi)_j}$, where $\mathrm{lev}(\pi)_j$ measures how often $j$ occurs between consecutive values in $\pi$. Permutations whose consecutive values are at most two positions apart in $\pi$ are shown to occur with the same probability for any choice of symmetric continuous step distribution. For random walks with steps from a mean zero normal distribution, ordinal pattern probabilities are determined by a matrix whose $ij$-th entry measures how often $i$ and $j$ are between consecutive values.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript derives explicit combinatorial formulas for the probabilities of ordinal patterns arising in finite random walks whose steps are drawn from three symmetric continuous distributions. For uniform steps on [-1,1] the probability of pattern π is |[1,w]|/(2^n n!), where [1,w] denotes a weak-order interval in the affine Weyl group ~A_n. For symmetric Laplace steps the probability is 1/(2^n ∏ lev(π)_j). Patterns whose consecutive values differ by at most two positions occur with identical probability under any symmetric continuous step law. For centered normal steps the probabilities are recovered from a matrix whose (i,j) entry counts the number of times i and j lie between consecutive values in the pattern.

Significance. If the derivations hold, the work supplies closed-form expressions that link ordinal-pattern statistics directly to affine Weyl-group combinatorics and to elementary permutation statistics (level counts and betweenness). The invariance result for the subclass of patterns with limited consecutive displacements is a notable strength, as is the explicit matrix description for the Gaussian case. These contributions replace simulation or numerical fitting with exact, distribution-specific combinatorial counts and therefore strengthen the theoretical foundation for ordinal analysis of random walks.

minor comments (3)
  1. [Abstract] Abstract: the quantity lev(π)_j is used without a one-sentence definition or pointer to its formal introduction; a brief gloss would aid readers who encounter the formula before reaching the relevant section.
  2. [Abstract] Abstract: the normal-distribution claim states that probabilities are “determined by a matrix” but does not indicate the precise functional dependence (e.g., whether the probability is a normalized product, determinant, or permanent of the matrix). A single clarifying sentence would remove ambiguity.
  3. The manuscript should state explicitly whether the weak-order interval size |[1,w]| is computed with respect to the standard length function on ~A_n or a different statistic; a short sentence linking the combinatorial object to the probability derivation would strengthen the presentation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, for highlighting the connections to affine Weyl groups and permutation statistics, and for recommending minor revision.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper states explicit combinatorial formulas for the probabilities of ordinal patterns under three symmetric continuous distributions, expressing them as |[1,w]|/(2^n n!) for uniform steps (weak order interval size in affine Weyl group ~A_n) and 1/(2^n prod lev(π)_j) for Laplace steps (product of level values). These quantities are independently defined combinatorial objects, not fitted parameters or quantities defined in terms of the target probabilities. The invariance result for patterns with consecutive values at most two positions apart is scoped to symmetric continuous distributions without claiming universality. No load-bearing self-citation, self-definitional reduction, or ansatz smuggling is present in the stated claims; the normal case is described as matrix-determined rather than closed-form. The derivation chain therefore does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the domain assumption that step distributions are symmetric and continuous, plus the standard mathematical identification of ordinal patterns with permutations and the correspondence between those permutations and elements of the affine Weyl group. No free parameters or new postulated entities appear in the abstract.

axioms (2)
  • domain assumption Step distributions are symmetric and continuous around zero.
    Symmetry is required for the probabilities to admit the stated closed forms independent of the precise distribution shape.
  • domain assumption Ordinal patterns correspond to permutations whose relative ordering probabilities factor through weak order intervals in the affine Weyl group.
    This identification is the key bridge between the random walk and the combinatorial count.

pith-pipeline@v0.9.0 · 5704 in / 1380 out tokens · 28955 ms · 2026-05-24T20:46:49.268154+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 2 internal anchors

  1. [1]

    Aomoto, Analytic structure of Schl¨ afli function, Nagoya Math

    K. Aomoto, Analytic structure of Schl¨ afli function, Nagoya Math. J., 68 (1977), 1–16

    work page 1977

  2. [2]

    Amig´ o, Permutation complexity in dynamical systems: ordinal patt erns, permutation entropy and all that , Springer Science & Business Media, 2010

    J. Amig´ o, Permutation complexity in dynamical systems: ordinal patt erns, permutation entropy and all that , Springer Science & Business Media, 2010

    work page 2010

  3. [3]

    Abramenko and K

    P. Abramenko and K. Brown, Buildings – Theory and Applications , Graduate Texts in Mathematics 248, Springer, New York, 2008

    work page 2008

  4. [4]

    Armstrong, Hyperplane arrangements and diagonal harmonics , J

    D. Armstrong, Hyperplane arrangements and diagonal harmonics , J. Comb. 4 (2013), no. 2, 157–190

    work page 2013

  5. [5]

    Avgustinovich and S

    S. Avgustinovich and S. Kitaev, On uniquely k-determined permutations , Discrete Math. 308 (2008), no. 9, 1500–1507

    work page 2008

  6. [6]

    Bandt and B

    C. Bandt and B. Pompe, Permutation Entropy: A Natural Complexity Measure for Time Series, Phys. Rev. Lett. 88, 174102 (2002)

    work page 2002

  7. [7]

    Bandt and F

    C. Bandt and F. Shiha, Order patterns in time series , Journal of Time Series Analysis 28 (2007), no. 5, 646–665

    work page 2007

  8. [8]

    Bj¨ orner and F

    A. Bj¨ orner and F. Brenti, Affine permutations of type A , Electron. J. Combin. 3 (1996), no. 2, R18, 35 pp

    work page 1996

  9. [9]

    Bj¨ orner and F

    A. Bj¨ orner and F. Brenti, Combinatorics of Coxeter groups , Graduate Texts in Mathe- matics 231, Springer-Verlag, New York, 2005

    work page 2005

  10. [10]

    Bj¨ orner, M

    A. Bj¨ orner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler, Oriented Matroids, second ed., Encyclopedia of Mathematics and Its Applicatio ns 46, Cambridge University Press, Cambridge, 1999

    work page 1999

  11. [11]

    Bj¨ orner and M

    A. Bj¨ orner and M. Wachs, Geometrically constructed bases for homology of partition lat- tices of types A, B, and D, Electron. J. Combin. 11 (2004), no. 2, R3, 26 pp

    work page 2004

  12. [12]

    DeFord and K

    D. DeFord and K. Moore, Random Walk Null Models for Time Series Data , Entropy 19 (2017), no. 11, 615, 28 pp

    work page 2017

  13. [13]

    Denoncourt, GitHub repository, https://github.com/HughDen/OrdinalPatterns (2019)

    H. Denoncourt, GitHub repository, https://github.com/HughDen/OrdinalPatterns (2019)

    work page 2019

  14. [14]

    Counting linear extensions of restricted posets

    S. Dittmer and I. Pak, Counting linear extensions of restricted posets , arXiv preprint, arXiv:1802.06312 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  15. [15]

    Elizalde and M

    S. Elizalde and M. Martinez, The frequency of pattern occurrence in random walks, Discrete Mathematics & Theoretical Computer Science, DMTCS Proceed ings, 27th International Conference on Formal Power Series and Algebraic Combinator ics (FPSAC 2015), January 2015

    work page 2015

  16. [16]

    J. E. Humphreys, Reflection Groups and Coxeter Groups , Cambridge University Press, 1990. 22

    work page 1990

  17. [17]

    Kreweras, Sur une classe de probl` emes d´ enombrement li´ es au trellis des partitions de entiers, Cahiers du Bur

    G. Kreweras, Sur une classe de probl` emes d´ enombrement li´ es au trellis des partitions de entiers, Cahiers du Bur. Univ. de Rech. Op´ er. (1965), no. 6, 5–105

    work page 1965

  18. [18]

    Lam and A

    T. Lam and A. Postnikov, Alcoved polytopes I, Discrete Comput. Geom. 38 (2007), no. 3, 453–478

    work page 2007

  19. [19]

    Alcoved Polytopes II

    T. Lam and A. Postnikov, Alcoved polytopes II, arXiv preprint, arXiv:1202.4015 (2012)

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  20. [20]

    Lapointe and J

    L. Lapointe and J. Morse, Tableaux on k + 1-cores, reduced words for affine permutations, and k-Schur expansions, J. Combin. Theory Ser. A 112 (2005), no. 1, 44–81

    work page 2005

  21. [21]

    Martinez, Equivalences on patterns in random walks , PhD thesis, Dartmouth College, 2015

    M. Martinez, Equivalences on patterns in random walks , PhD thesis, Dartmouth College, 2015

    work page 2015

  22. [22]

    (2019), The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A003274

    OEIS Foundation Inc. (2019), The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A003274

    work page 2019

  23. [23]

    Page, Systematic generation of ordered sequences using recurren ce relations , The Computer Journal 14 (1971), no

    E.S. Page, Systematic generation of ordered sequences using recurren ce relations , The Computer Journal 14 (1971), no. 2, 150–153

    work page 1971

  24. [24]

    Ribando, Measuring solid angles beyond dimension three , Discrete Comput

    J. Ribando, Measuring solid angles beyond dimension three , Discrete Comput. Geom. 36 (2006), no. 3, 479–487

    work page 2006

  25. [25]

    Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups , Lecture Notes in Math., vol 1179, Springer-Verlag, 1986

    J.-Y. Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups , Lecture Notes in Math., vol 1179, Springer-Verlag, 1986

    work page 1986

  26. [26]

    Shi, Alcoves corresponding to an affine Weyl group , J

    J.-Y. Shi, Alcoves corresponding to an affine Weyl group , J. London Math. Soc. (2) 35 (1987), no. 1, 42–55

    work page 1987

  27. [27]

    Shi, On two presentations of the affine Weyl groups of classical typ es, J

    J.-Y. Shi, On two presentations of the affine Weyl groups of classical typ es, J. Algebra 221 (1999), 360–383

    work page 1999

  28. [28]

    Sommers, B-stable ideals in the nilradical of a Borel subalgebra , Canad

    E. Sommers, B-stable ideals in the nilradical of a Borel subalgebra , Canad. Math. Bull. 48 (2005), no. 3, 460–472

    work page 2005

  29. [29]

    Stanley, Eulerian partitions of a hypercube , Higher Combinatorics 31 (1977), p

    R. Stanley, Eulerian partitions of a hypercube , Higher Combinatorics 31 (1977), p. 49

    work page 1977

  30. [30]

    Zare, Random permutations from Brownian motion, https://mathoverflow.net/q/97875 (2012) 23

    D. Zare, Random permutations from Brownian motion, https://mathoverflow.net/q/97875 (2012) 23

    work page 2012