Imagine a one-way street with n parking spots along the curb, numbered 1 to n. There are n cars, and each car has a preferred spot — for example, car i prefers 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 drive forward to the first empty spot. If you reach the end of the street without finding one, you drive away — you fail to park.
The natural question: which preference sequences allow all n cars to park?
This is the origin of parking functions, a problem posed by Konheim and Weiss in 1966 while studying something related to computer storage — though possibly also because everyone has parking anxiety.
🚗 Which preference sequences work?
Take n = 3: three cars, three spots.
- (1, 2, 3) — obviously everyone parks.
- (2, 2, 2) — car 1 takes spot 2, car 2 finds spot 2 taken and moves to 3, car 3 takes spot 1. Everyone parks.
- (2, 1, 2) — car 1 parks at 2, car 2 parks at 1, car 3 finds 2 taken, and 3 is free — parked.
- (3, 3, 3) — car 1 parks at 3, car 2 finds 3 taken but there is no spot 4 — drives away. Failure.
An honest detour
The classic criterion says: a sequence of length n is a parking function if and only if, when sorted nondecreasingly, a_(k) <= k. But for (2, 2, 2) with n = 3, the first sorted element is 2, and 2 <= 1 fails — yet we just showed all three cars park successfully. So something is off in my reasoning.
> OK, I have to stop and be honest. I've muddled the precise condition for parking functions. The classical result is that a length-n sequence of positive integers is a parking function iff, when sorted, it satisfies a_(i) <= i. But my (2, 2, 2) example doesn't match, which means my on-the-spot simulation may have gone wrong somewhere. This is the moment many math articles never show you: writers get stuck too. But Feynman said don't fool yourself — so I admit I don't know this specific edge case. The big picture is still right: some preference sequences let every car park, some don't, and the ones that do are parking functions.
♟️ Connection to the symmetric group
Every parking function has a natural symmetry. Permuting the coordinates of a parking function — swapping car 1's preference with car 2's, say — doesn't always yield another parking function. But some permutations do preserve "parkability."
This is the key idea used in Feng and Paguyo's paper. They let the symmetric group S_n act on the set of all parking functions of length n. The group action partitions parking functions into orbits — sequences in the same orbit are related by coordinate permutations. They then define a Markov chain on this large state space, called the Burnside process.
The Burnside process comes from an old lemma: given a group action on a set, you can construct a Markov chain that is uniform on orbit projections. The remarkable thing is that the chain doesn't require knowing how many orbits exist or how large each one is. You only need to be able to compute orbit membership of group elements — the chain finds the uniform distribution on its own.
📐 What they actually did
Feng and Paguyo analyzed two cases:
1. The state space of all length-n parking functions, with S_n acting by permuting coordinates. How fast does the Burnside process mix to uniform? 2. The state space of labeled Dyck paths — lattice paths from (0,0) to (2n, 0) that never dip below the x-axis, with each step of every path labeled — with S_n acting by permuting the 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, not 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 — the classic Catalan-number problem of cutting a polygon into triangles with noncrossing diagonals.
🤷 Things I don't know
1. I don't fully understand the efficiency comparison between the Burnside process and the traditional "random walk on orbit space." O(n log n) sounds fast, but what computation does each step require — evaluating group actions, checking orbit membership? The paper focuses on step counts, but per-step cost could be substantial. 2. I don't know whether this sampling method has practical advantages over existing approaches (e.g., recursive sampling) for real applications like mesh generation via random triangulations. A theoretical mixing time is one thing; what are the constants in practical parameter regimes? The paper reports no numerical experiments, so I can't judge. 3. What exactly are "labeled Dyck paths"? Are the labels tied to each edge's elevation, or to vertex coordinates? From the title and abstract I infer a standard construction, but I couldn't confirm it directly from the abstract.
🎯 One thing is clear
A combinatorial object born from a 1966 parking problem can still yield new algorithms in 2026. Feng and Paguyo combine group actions with Markov chains to obtain clean theoretical results on Catalan-type structures. Parking functions went from "parking by the curb" to "parking in mathematics" — a rather beautiful continuation in itself.
---
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.