pith. sign in

arxiv: 2605.16244 · v1 · pith:OOWYULWNnew · submitted 2026-05-15 · 🧮 math.PR · math.CO

Burnside process on parking functions and Dyck paths

Ivan Z. Feng , J. E. Paguyo This is my paper

Pith reviewed 2026-05-19 18:21 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords Burnside processparking functionsDyck pathsMarkov chain mixinguniform samplingCatalan structurestriangulationsgroup actions
0
0 comments X

The pith

The Burnside process on parking functions and labeled Dyck paths mixes in O(n log n) steps and yields uniform sampling algorithms.

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

The paper studies a Markov chain called the Burnside process that arises from a finite group acting on a set and projects to uniform distribution over the orbits. It applies the construction in two cases: parking functions of length n with the symmetric group permuting coordinates, and labeled Dyck paths of length 2n with the symmetric group permuting labels. The central result establishes that both chains reach stationarity in at most O(n log n) steps. This bound supplies practical algorithms for sampling an increasing parking function or a Dyck path approximately uniformly at random. The same technique also produces approximate uniform samples of triangulations of an (n+2)-gon.

Core claim

The Burnside processes defined on the set of parking functions of length n under the action of S_n by coordinate permutation and on the set of labeled Dyck paths of length 2n under the action of S_n by label permutation both mix rapidly, with mixing times bounded above by O(n log n). This establishes new Markov-chain algorithms that output an increasing parking function or a Dyck path approximately uniformly at random, and the same processes can be used to sample triangulations of an (n+2)-gon approximately uniformly at random.

What carries the argument

The Burnside process, a Markov chain on the underlying set whose transitions are chosen so that the projected chain on orbits has uniform stationary distribution.

Load-bearing premise

The specific group actions of S_n on parking functions by coordinate permutation and on Dyck paths by label permutation allow the Burnside process to maintain uniform stationary distribution on orbits and to mix rapidly under the given transition rules.

What would settle it

A direct computation or simulation for some large n showing that the total-variation distance to the uniform distribution on orbits stays larger than 1/4 after more than C n log n steps for any fixed constant C would falsify the claimed mixing-time upper bound.

Figures

Figures reproduced from arXiv: 2605.16244 by Ivan Z. Feng, J. E. Paguyo.

Figure 1
Figure 1. Figure 1: (a) The Dyck path (given by the sequence N2E E NE N2E E) corresponding to the increasing parking function u = (1, 1, 3, 4, 4). (b) The labeled Dyck path corresponding to the parking function x = (4, 1, 3, 4, 1). Let X = LDn and let G = Sn act on LDn as follows. Given σ ∈ Sn, replace the label i by σ(i), and then rearrange the labels along each vertical run so that they are in increasing order. See [PITH_F… view at source ↗
Figure 2
Figure 2. Figure 2: Example of the group action of S5 on labeled Dyck paths LD5. Here σ = (1 5 3)(2 4). Let Gx be the stabilizer of x ∈ LDn and let Xσ be the fixed set of σ under this group action of Sn on LDn. The Burnside process on labeled Dyck paths (henceforth, the Burnside process on LDn), is a Markov chain whose transition between states x, y ∈ LDn is described by the following two-step procedure: • From x ∈ LDn, pick … view at source ↗
read the original abstract

Let $G$ be a finite group acting on a finite set $X$. This group action splits $X$ into disjoint orbits. The Burnside process is a Markov chain on $X$ which has a uniform stationary distribution when the chain is projected to orbits. We initiate the study of the Burnside process on Catalan structures. We consider two special cases: the first where the state space is the set of parking functions of length $n$ and $G = S_n$ is the symmetric group on $[n]$, such that $G$ acts by permuting coordinates, and the second where the state space is the set of labeled Dyck paths of length $2n$ and $G = S_n$ acts by permuting labels. The resulting Burnside processes give novel algorithms for sampling, respectively, an increasing parking function and a Dyck path approximately uniformly at random. Our main result shows that both processes are rapidly mixing, with mixing times upper bounded by $O(n \log n)$. As an application, we show how our Burnside process can be used to sample triangulations of an $(n+2)$-gon approximately uniformly at random.

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 introduces the Burnside process on two families of Catalan structures: parking functions of length n under the coordinate-permutation action of S_n, and labeled Dyck paths of length 2n under the label-permutation action of S_n. It shows that the resulting Markov chains have uniform stationary distribution on orbits and proves, via explicit coupling arguments, that both chains are rapidly mixing with mixing-time upper bound O(n log n). The work concludes with an application to approximate uniform sampling of triangulations of an (n+2)-gon via the standard Dyck-path bijection.

Significance. If the stated mixing-time bounds hold, the paper supplies concrete, efficient sampling algorithms for increasing parking functions and for Dyck paths, objects central to enumerative combinatorics. Credit is due for the explicit coupling constructions that rely only on standard combinatorial facts (increasing orbit representatives, recursive structure of Dyck paths) rather than black-box theorems, and for the direct derivation of the triangulation-sampling application.

minor comments (3)
  1. [§2] §2, definition of the Burnside process: the transition probabilities are written in terms of fixed-point counts; a short sentence recalling that the chain is well-defined on the full set X (not only on orbits) would aid readers unfamiliar with the general construction.
  2. [Theorem 3.4] Theorem 3.4 (parking-function mixing time): the coupling argument tracks coordinate coalescence but does not explicitly bound the probability that a given coordinate has not yet been hit after t steps; adding this one-line estimate would make the O(n log n) derivation fully self-contained.
  3. [Figure 1] Figure 1 (Dyck-path example): the labels on the path are printed in a font size that is difficult to read at standard journal resolution; increasing the font or adding a magnified inset would improve clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the mixing-time results, and recommendation for minor revision. No specific major comments were raised in the report, so we have no points to address individually at this stage. We will incorporate any minor editorial suggestions in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper applies the general Burnside process (defined via group actions on orbits) to parking functions under S_n coordinate permutation and to labeled Dyck paths under label permutation. Uniformity on orbits follows immediately from the standard Burnside process construction without redefinition. The O(n log n) mixing-time upper bounds are derived via separate explicit coupling arguments that track coordinate/label coalescence, using only standard combinatorial facts (increasing orbit representatives, Dyck path recursion) that are independently verifiable. No fitted parameters are renamed as predictions, no self-citation chain carries the central claim, and the triangulation-sampling application rests on the pre-existing Dyck-path bijection. The derivation chain is therefore independent of its inputs and contains no circular reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the general definition of the Burnside process and its uniform stationary distribution on orbits under group actions, with no free parameters, invented entities, or additional axioms mentioned in the abstract.

axioms (1)
  • domain assumption The Burnside process has a uniform stationary distribution when the chain is projected to orbits.
    Stated as the general property of the Burnside process in the setup before the two special cases.

pith-pipeline@v0.9.0 · 5731 in / 1203 out tokens · 53763 ms · 2026-05-19T18:21:41.765804+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 3 internal anchors

  1. [1]

    Aldous,Mixing times for the branch-rotation chain on cladograms (or the triangulation walk), https://www.stat.berkeley.edu/~aldous/Research/OP/clad-mix.pdf, (2003)

    D. Aldous,Mixing times for the branch-rotation chain on cladograms (or the triangulation walk), https://www.stat.berkeley.edu/~aldous/Research/OP/clad-mix.pdf, (2003)

    work page 2003

  2. [2]

    Aldous and J

    D. Aldous and J. Fill,Reversible Markov chains and random walks on graphs, https://www.stat.berkeley.edu/~aldous/RWG/book.pdf, (2002)

    work page 2002

  3. [3]

    V. L. Alev, D. Frishberg, M. Sarantis, and P. Tetali,Faster mixing for triangulation via transport flows, arXiv:2605.02067 (2026)

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  4. [4]

    Exact uniform sampling over catalan structures

    A. Angelopoulos and E. Bakali,Exact uniform sampling over Catalan structures, arXiv:1803.03945 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  5. [5]

    H. C. Andersen and P. Diaconis,Hit and run as a unifying device, Journal de la Soci´ et´ e Francaise Statistique, 148 (4) (2007), 5-28

    work page 2007

  6. [6]

    Armstrong, N

    D. Armstrong, N. A. Loehr, and G. S. Warrington,Rational parking functions and Catalan numbers, Annals of Combina- torics, 20 (1) (2016), 21–58

    work page 2016

  7. [7]

    Bartholdi and P

    L. Bartholdi and P. Diaconis,An algorithm for uniform generation of unlabeled (P´ olya) trees, Forum of Mathematics, Sigma, 14:e76 (2026), 1-27

    work page 2026

  8. [8]

    Bayer and P

    D. Bayer and P. Diaconis,Trailing the dovetail shuffle to its lair, Annals of Applied Probability, 2 (2) (1992), 294-313

    work page 1992

  9. [9]

    W. K. Chen,Mixing times for Burnside processes, Master’s Thesis, National Chiao Tung University, (2006)

    work page 2006

  10. [10]

    Cohen,Problems in Catalan mixing and matchings in regular hypergraphs, PhD Thesis, Georgia Institute of Technology, ProQuest LLC, (2016)

    E. Cohen,Problems in Catalan mixing and matchings in regular hypergraphs, PhD Thesis, Georgia Institute of Technology, ProQuest LLC, (2016)

    work page 2016

  11. [11]

    Dalla Pria,On exchangeable partition ensembles, PhD Thesis, University of Turin, (2026)

    M. Dalla Pria,On exchangeable partition ensembles, PhD Thesis, University of Turin, (2026). 16 IVAN Z. FENG AND J. E. PAGUYO

    work page 2026

  12. [12]

    Diaconis,Analysis of a Bose-Einstein Markov chain, Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 41 (3) (2005), 409-418

    P. Diaconis,Analysis of a Bose-Einstein Markov chain, Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 41 (3) (2005), 409-418

    work page 2005

  13. [13]

    Diaconis,The Markov chain Monte Carlo revolution, Bulletin of the American Mathematical Society, 46 (2) (2009), 179–205

    P. Diaconis,The Markov chain Monte Carlo revolution, Bulletin of the American Mathematical Society, 46 (2) (2009), 179–205

    work page 2009

  14. [14]

    Diaconis,Some things we’ve learned (about Markov chain Monte Carlo), Bernoulli, 19 (4) (2013), 1294-1305

    P. Diaconis,Some things we’ve learned (about Markov chain Monte Carlo), Bernoulli, 19 (4) (2013), 1294-1305

    work page 2013

  15. [15]

    Diaconis and M

    P. Diaconis and M. Howes,Random sampling of partitions and contingency tables: Two practical examples of the Burnside process, Statistics and Computing, 35:181 (2025)

    work page 2025

  16. [16]

    Diaconis, A

    P. Diaconis, A. Lin, and A. Ram,A curiously slowly mixing Markov chain, arXiv:2511.01245 (2025)

    work page arXiv 2025

  17. [17]

    Diaconis, A

    P. Diaconis, A. Lin, and A. Ram,Schur-Weyl duality for diagonalizing a Markov chain on the hypercube, arXiv:2512.23285 (2025)

    work page arXiv 2025

  18. [18]

    Diaconis and C

    P. Diaconis and C. Morton-Ferguson,Markov chains on Weyl groups from the geometry of the flag variety, arXiv:2510.02285 (2025)

    work page arXiv 2025

  19. [19]

    Diaconis and M

    P. Diaconis and M. Shahshahani,Generating a random permutation with random transpositions, Z. Wahrscheinlichkeits- theorie verw Gebiete, 57 (1981), 159-179

    work page 1981

  20. [20]

    Diaconis and M

    P. Diaconis and M. Shahshahani,Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM Journal on Mathematical Analysis, 18 (1) (1987), 208-218

    work page 1987

  21. [21]

    Diaconis and C

    P. Diaconis and C. Zhong,Hahn polynomials and the Burnside process, Ramanujan Journal, doi:10.1007/s11139-021-00482- z, (2021)

    work page doi:10.1007/s11139-021-00482- 2021

  22. [22]

    Diaconis and C

    P. Diaconis and C. Zhong,Counting the number of group orbits by marrying the Burnside process with importance sampling, Advances in Applied Mathematics, 172 (2026), 102955

    work page 2026

  23. [23]

    Dittmer,Counting linear extensions and contingency tables, PhD Thesis, University of California Los Angeles, ProQuest LLC, (2019)

    S. Dittmer,Counting linear extensions and contingency tables, PhD Thesis, University of California Los Angeles, ProQuest LLC, (2019)

    work page 2019

  24. [24]

    R. G. Edwards and A. D. Sokal,Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm, Physical Review D, 38 (6) (1988), 2009–2012

    work page 1988

  25. [25]

    I. Z. Feng,The dual Burnside process, arXiv:2510.25202 (2025)

    work page internal anchor Pith review arXiv 2025

  26. [26]

    Foata and J

    D. Foata and J. Riordan,Mappings of acyclic and parking functions, Aequationes Math, 10 (1) (1974), 10-22

    work page 1974

  27. [27]

    Eppstein and D

    D. Eppstein and D. Frishberg,Improved mixing for the convex polygon triangulation flip walk, In: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), 261 (2023), 56:1-17

    work page 2023

  28. [28]

    A. M. Garsia and M. Haiman,A remarkableq, t-Catalan sequence andq-Lagrange inversion, Journal of Algebraic Com- binatorics, 5 (1996), 191-244

    work page 1996

  29. [29]

    L. A. Goldberg and M. Jerrum,The ‘Burnside process’ converges slowly, Combinatorics, Probability, and Computing, 11 (2002), 21-34

    work page 2002

  30. [30]

    Howes,Limit profiles and cutoff for the Burnside process on Sylow double cosets, Journal of Theoretical Probability, 39 (29) (2026)

    M. Howes,Limit profiles and cutoff for the Burnside process on Sylow double cosets, Journal of Theoretical Probability, 39 (29) (2026)

    work page 2026

  31. [31]

    Holtzen, T

    S. Holtzen, T. Millstein, and G. Van den Broeck,Generating and sampling orbits for lifted probabilistic inference, In: Proceedings of the 35th Uncertainty in Artificial Intelligence Conference, PMLR 115 (2020), 985-994

    work page 2020

  32. [32]

    Jerrum,Uniform sampling modulo a group of symmetries using Markov chain simulation, In: DIMACS Series Discrete Math

    M. Jerrum,Uniform sampling modulo a group of symmetries using Markov chain simulation, In: DIMACS Series Discrete Math. Theoret. Comput. Sci., Vol. 10 (1993), 37-47

    work page 1993

  33. [33]

    Jerrum,Computational P´ olya theory, In: Surveys in Combinatorics, London Mathematical Society Lecture Note Series 218, Cambridge University Press, (1995)

    M. Jerrum,Computational P´ olya theory, In: Surveys in Combinatorics, London Mathematical Society Lecture Note Series 218, Cambridge University Press, (1995)

    work page 1995

  34. [34]

    A. G. Konheim and B. Weiss,An occupancy discipline and applications, SIAM Journal on Applied Mathematics, 14 (1966), 1266-1274

    work page 1966

  35. [35]

    D. A. Levin, Y. Peres, and E. L. Wilmer,Markov Chains and Mixing Times, American Mathematical Society, Providence, RI., (2009)

    work page 2009

  36. [36]

    Martin and D

    R. Martin and D. Randall,Sampling adsorbing staircase walks using a new Markov chain decomposition method, In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, (2000), 492-502

    work page 2000

  37. [37]

    McShine and P

    L. McShine and P. Tetali,On the mixing time of the triangulation walk and other Catalan structures, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 43 (1998), 147-160

    work page 1998

  38. [38]

    Molloy, B

    M. Molloy, B. Reed, and W. Steiger,On the mixing rate of the triangulation walk, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 43 (1998), 179-190

    work page 1998

  39. [39]

    J. E. Paguyo,Mixing times of a Burnside process Markov chain on set partitions, Advances in Applied Mathematics, 175 (2026), 103047

    work page 2026

  40. [40]

    Rahmani,Mixing times for the commuting chain on CA groups, Journal of Theoretical Probability, doi:10.1007/s10959- 020-01049-2, (2020)

    J. Rahmani,Mixing times for the commuting chain on CA groups, Journal of Theoretical Probability, doi:10.1007/s10959- 020-01049-2, (2020)

    work page doi:10.1007/s10959- 2020

  41. [41]

    D. D. Sleator, R. E. Tarjan, and W. P. Thurston,Rotation distance, triangulations, and hyperbolic geometry, Journal of the American Mathematical Society, 1 (3) (1988), 647-681

    work page 1988

  42. [42]

    R. P. Stanley,Parking Functions and Noncrossing Partitions, Electronic Journal of Combinatorics, 4 (2) (1997), R20

    work page 1997

  43. [43]

    R. P. Stanley,Catalan Numbers, Cambridge University Press, New York, (2015)

    work page 2015

  44. [44]

    R. H. Swendsen and J. S. Wang,Nonuniversal critical dynamics in Monte Carlo simulations, Physical Review Letters, 58 (1987), 86-88

    work page 1987

  45. [45]

    Tanner and W

    M. Tanner and W. Wong,The calculation of posterior distributions by data augmentation, Journal of the American Statistical Association, 82 (1987), 528-550. BURNSIDE PROCESS ON PARKING FUNCTIONS AND DYCK PATHS 17

    work page 1987

  46. [46]

    D. B. Wilson,Mixing times of lozenge tiling and card shuffling Markov chains, Annals of Applied Probability, 14 (1) (2004), 274-325

    work page 2004

  47. [47]

    C. H. Yan,Parking functions, In: Handbook of Enumerative Combinatorics, Discrete Math. Appl. CRC Press, Boca Raton, (2015), 835-893. Department of Mathematics, University of Southern California, Los Angeles, CA, 90089, USA E-mail address:ifeng@usc.edu Department of Mathematics & Statistics, McMaster University, Hamilton, ON, L8S 4K1, Canada E-mail address...

    work page 2015