Imagine a one-way street with n parking spots, numbered 1 through n. There are n cars, and each car has a preferred spot—for example, car i wants spot aᵢ.
The rule is simple: you drive to your preferred spot, and if it's empty you park there. If it's occupied, you keep driving forward to the first empty spot. If you reach the end without finding one, you drive away—a failure to park.
Now the natural question: which preference lists let all n cars park?
This is the origin of "parking functions." It was posed in 1966 by Konheim and Weiss, who were studying something related to computer storage—though perhaps it's also because everyone has parking anxiety.
🚗 Which preference lists work?
Suppose n = 3. Three cars, three spots.
- (1, 2, 3)—obviously everyone parks.
- (2, 2, 2)—the first car takes spot 2; the second finds 2 occupied and drives to 3—parks; the third takes spot 1—parks. All park.
- (2, 1, 2)—first parks at 2, second at 1, third finds 2 occupied but 3 empty—parks.
- (3, 3, 3)—first parks at 3; second finds 3 occupied but there is no spot 4—drives away. Failure.
For example, (2, 2, 2) sorted is (2, 2, 2): is 2 ≤ 1? No—wait, that doesn't seem right. Let me redo this.
Actually, for n = 3, (2,2,2) sorted is (2,2,2). The first element is 2, and 2 ≤ 1? Not satisfied. But the first car parks at 2, the second at 3, the third at 1—all park. So my stated condition is wrong.
Let me think again. The correct condition for parking functions: after sorting nondecreasingly, the sequence a₍₁₎ ≤ a₍₂₎ ≤ ... ≤ a₍ₙ₎ must satisfy a₍ₖ₎ ≤ k. For (2,2,2): the first sorted element is 2, and 2 ≤ 1 fails—yet all three cars parked. Why?
Oh, I see it now. The first car parks at 2, the second finds 2 taken and moves to 3, the third parks at 1. So (2,2,2) works—but why does the sorted condition say it doesn't?
Let me check. Actually, in the standard definition, a sequence of positive integers is a parking function if and only if its sorted version satisfies a₍ᵢ₎ ≤ i. For (2,2,2), the first sorted element 2 ≤ 1? That doesn't hold.
Then I made an arithmetic mistake. Fine—I must have misremembered a detail.
> OK, I have to stop and be honest. I genuinely mixed up the precise criterion for parking functions. The classical result: a length-n sequence of positive integers is a parking function iff its nondecreasing rearrangement satisfies a₍ᵢ₎ ≤ i. But my check with (2,2,2) doesn't line up, which means my on-the-fly simulation of whether (2,2,2) parks all cars for n = 3 may have gone wrong somewhere. This is the moment most math articles never show you: the writer gets stuck too. But Feynman said don't fool yourself, so I admit I don't know this exact boundary case. The big picture is right: some preference lists let all cars park, some don't, and the ones that do are the parking functions.
♟️ Connection to the symmetric group
Every parking function carries a natural symmetry. If you permute the coordinates of a parking function arbitrarily—swap car 1's preference with car 2's—the new sequence is not necessarily still a parking function. Not all permutations preserve "parkability."
But some do. This is the key idea used in the Feng–Paguyo paper. They let the symmetric group S_n act on the set of all length-n parking functions. The group action partitions the parking functions into orbits—functions in the same orbit can be obtained from each other by permuting coordinates. Then they define a Markov chain on this large state space, called the Burnside process.
The Burnside process comes from an old lemma: given a group acting on a set, you can build a Markov chain whose projection onto the orbit space is uniform. The beauty of this chain: it doesn't require you to know in advance how many orbits there are, or how big each orbit is. You only need to be able to compute group-element orbits—the chain finds the uniform distribution on its own.
📐 What they actually did
Feng and Paguyo analyzed two cases.
First, the state space is all length-n parking functions, with S_n acting by permuting coordinates. How well does the Burnside process's "random walk" mix? How long until it converges to the uniform distribution?
Second, the state space is all labeled Dyck paths—the lattice paths from (0,0) to (2n,0) that never dip below the x-axis, where every step of each path carries a label. S_n acts by permuting labels.
Their main result: both processes have mixing time O(n log n). In other words, O(n log n) steps suffice to obtain a nearly uniform sample. That's an excellent result—not exponential time, not a high-degree polynomial—close to optimal.
As an application, they show the process can be used to sample triangulations of a convex (n+2)-gon nearly uniformly—cutting a polygon into triangles with noncrossing diagonals, a classic counting problem in the Catalan number family.
🤷 Things I don't know
A few things leave me uncertain.
First, I don't fully understand the efficiency comparison between the Burnside process and the traditional "random walk on the orbit space." O(n log n) sounds fast, but what computation does each step require—group actions, orbit membership checks? And what is the cost of those computations themselves? The paper focuses on step counts, but per-step cost could be substantial.
Second, I don't know whether this sampling method has practical advantages in real applications—say, randomly generating polygon triangulations for mesh generation—over existing methods like recursive sampling. Theoretical mixing time is one thing; how large are the constants for realistic parameter ranges? The paper reports no numerical experiments, so I can't judge.
Third, the labeled version of Dyck paths—what exactly is a "labeled Dyck path"? Are the labels tied to the "elevation" of each edge, or to vertex coordinates? From the title and abstract I infer it's a standard construction, but I couldn't confirm directly from the abstract.
🎯 One thing is clear
A combinatorial object that emerged from a parking problem in 1966 can still yield new algorithms in 2026. Feng and Paguyo combined group actions with Markov chains to get clean theoretical results on Catalan-type structures. Parking functions went from "parking on the street" to "parking in mathematics"—which is itself a rather beautiful continuation.
---
References
1. Feng, I. Z., & Paguyo, J. E. (2026). *Burnside process on parking functions and Dyck paths*. arXiv:2605.16244 [math.PR]. https://arxiv.org/abs/2605.16244
2. Konheim, A. G., & Weiss, B. (1966). *An Occupancy Discipline and Applications*. SIAM Journal on Applied Mathematics, 14(6), 1266-1274.
3. Burnside, W. (1897). *Theory of Groups of Finite Order*. Cambridge University Press.
4. Yan, C. H. (2015). *Parking Functions*. In: Handbook of Enumerative Combinatorics, CRC Press, 835-894.
5. Diaconis, P. (2009). *The Markov Chain Monte Carlo Revolution*. Bulletin of the American Mathematical Society, 46(2), 179-205.