Asymptotic behaviour of the first positions of uniform parking functions

Abstract

In this paper we study the asymptotic behavior of a random uniform parking function ${\pi }_n$ of size $n$. We show that the first $k_n$ places ${\pi }_n(1),\dots ,{\pi }_n(k_n)$ of ${\pi }_n$ are asymptotically i.i.d. and uniform on $\{1,2,\dots ,n\}$, for the total variation distance when $k_n=o(\sqrt{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.

13 pages, 1 figure