Total variation threshold for uniform parking functions

A parking function is a list of preferences that lets every car park. Each car tries its preferred space and then moves forward to the next available one. For a uniformly chosen valid list of length n, how many initial preferences can be treated as independent uniform choices?

Why it matters and what counts as progress

Why it matters: Total variation measures how well the two laws agree on every event. The first entries can look independent while the effect of conditioning on successful parking still changes the joint law of a longer prefix.

What counts as progress: Find matching total-variation bounds for growing prefixes or determine the limit at the transition scale. Specify the comparison law, since independent uniform entries and independent entries with the actual marginal law give different estimates.

How the problem developed

  1. 19 Aug 2021 · Growing-prefix approximation [1]

    Etienne Bellin Proved total-variation convergence to independent uniform choices for prefixes of length o(n)o(\sqrt{n}).

  2. 29 Oct 2026 · Threshold and critical profile [2][3]

    Igor Kortchemski with ChatGPT 6 Pro Gave matching finite bounds and determined the Gaussian limit profile when k is of order n/log⁡nn/\log n.

AI contribution

A total variation threshold for the first coordinates of uniform parking functions via Lorentzian polynomials

Igor Kortchemski

For the first k entries of a uniform parking function of length n, the total variation distance from k independent uniform choices is of order min⁡(1,(klog⁡(k+1)/n))\min (1, \sqrt{(k \log (k+1)/n)}). If k log⁡n/n\log n/n tends to λ\lambda , the distance tends to 2Φ((λ/π))−12\Phi (\sqrt{(\lambda /\pi )})-1, where Φ\Phi is the standard normal distribution function. The paper also bounds relative entropy for the comparison with independent entries drawn from the actual marginal law.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean + human)
Human understandingFew
Paper date:

Sources

  1. Asymptotic behaviour of the first positions of uniform parking functions
  2. A total variation threshold for the first coordinates of uniform parking functions via Lorentzian polynomials
  3. Lean verification and manuscript correspondence
Publication history