Asymptotic behaviour of the first positions of uniform parking functions

2021/08/19 by Étienne Bellin, Bellin, Etienne · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2108.08661

openalex publication_date 2021/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we study the asymptotic behavior of a random uniform parking function π_n of size n. We show that the first k_n places π_n(1),…,π_n(k_n) of π_n are asymptotically i.i.d. and uniform on \1,2,…,n\, for the total variation distance when k_n = o(√(n)), and for the Kolmogorov distance when k_n=o(n), improving results of Diaconis & Hicks. Moreover we give bounds for the rate of convergence, as well as limit theorems for some statistics like the sum or the maximum of the first k_n parking places. The main tool is a reformulation using conditioned random walks.

Cited by

• A family of non-uniform distributions on the set of parking functions generated by random permutations

Related

• Limit theorems for random walks that avoid bounded sets, with\n applications to the largest gap problem
• Asymptotics of returns to the coordinate hyperplanes for conditioned simple random walks
• On the first positive position of a random walker
• Convergence Rate for The Number of Crossing in a Random Labelled Tree
• On The Number of Times where a Simple Random Walk reaches a Nonnegative Height