Hostname: page-component-848d4c4894-2pzkn Total loading time: 0 Render date: 2024-06-02T13:27:08.369Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic behaviour of the first positions of uniform parking functions

Part of: Stochastic processes Probability theory on algebraic and topological structures Combinatorial probability

Published online by Cambridge University Press:  20 April 2023

Etienne Bellin
Etienne Bellin*
Affiliation:
Ecole Polytechnique
*
*Postal address: Centre de Mathématiques Appliquées, Ecole Polytechnique, Palaiseau, France. Email address: etienne.bellin@polytechnique.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study the asymptotic behaviour of a random uniform parking function $\pi_n$ of size n. We show that the first $k_n$ places $\pi_n(1),\ldots,\pi_n(k_n)$ of $\pi_n$ are asymptotically independent and identically distributed (i.i.d.) and uniform on $\{1,2,\ldots,n\}$, for the total variation distance when $k_n = {\rm{o}}(\sqrt{n})$, and for the Kolmogorov distance when $k_n={\rm{o}}(n)$, improving results of Diaconis and Hicks. Moreover, we give bounds for the rate of convergence, as well as limit theorems for certain statistics such as the sum or the maximum of the first $k_n$ parking places. The main tool is a reformulation using conditioned random walks.

Keywords

Random walkstotal variation distanceCayley trees

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60G50: Sums of independent random variables; random walks 60B10: Convergence of probability measures
Type
Original Article
Information
Journal of Applied Probability , Volume 60 , Issue 4 , December 2023 , pp. 1201 - 1218
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abraham, R. and Delmas, J.-F. (2020). An introduction to Galton–Watson trees and their local limits. Available at arXiv:1506.05571.Google Scholar
Addario-Berry, L., Devroye, L. and Janson, S. (2013). Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees. Ann. Prob. 41, 1072–1087.CrossRefGoogle Scholar
Biane, P. (2002). Parking functions of types A and B. Electron. J. Combin. 9, N7.CrossRefGoogle Scholar
Billingsley, P. (2012). Probability and Measure (Wiley Series in Probability and Statistics). Wiley.Google Scholar
Bobkov, S. G. (2005). Generalized symmetric polynomials and an approximate de Finetti representation. J. Theoret. Prob. 18, 399–412.CrossRefGoogle Scholar
Broutin, N. and Marckert, J.-F. (2016). A new encoding of coalescent processes: applications to the additive and multiplicative cases. Prob. Theory Relat. Fields 166, 515–552.Google Scholar
Chassaing, P. and Louchard, G. (2002). Phase transition for parking blocks, Brownian excursion and coalescence. Random Structures Algorithms 21, 76–119.CrossRefGoogle Scholar
Chassaing, P. and Marckert, J.-F. (2001). Parking functions, empirical processes, and the width of rooted labeled trees. Electron. J. Combin. 8, R14.CrossRefGoogle Scholar
Chebikin, D. and Postnikov, A. (2010). Generalized parking functions, descent numbers, and chain polytopes of ribbon posets. Adv. Appl. Math. 44, 145–154.Google Scholar
Cori, R. and Rossin, D. (2000). On the sandpile group of dual graphs. European J. Combinatorics 21, 447–459.CrossRefGoogle Scholar
Diaconis, P. and Hicks, A. (2017). Probabilizing parking functions. Adv. Appl. Math. 89, 125–155.CrossRefGoogle Scholar
Ibragimov, I. A. and Linnik, Y. V. (1971). Independent and Stationary Sequences of Random Variables. Wolters-Noordhoff, Groningen.Google Scholar
Janson, S. (2006). Random cutting and records in deterministic and random trees. Random Structures Algorithms 29, 139–179.CrossRefGoogle Scholar
Janson, S. (2012). Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. Prob. Surveys 9, 103–252.CrossRefGoogle Scholar
Kenyon, R. and Yin, M. (2023). Parking functions: from combinatorics to probability. Methodology Comput. Appl. Prob. 25, 32.Google Scholar
Konheim, A. G. and Weiss, B. (1966). An occupancy discipline and applications. SIAM J. Appl. Math. 14, 1266–1274.CrossRefGoogle Scholar
Le Gall, J.-F. (2005). Random trees and applications. Prob. Surveys 2, 245–311.CrossRefGoogle Scholar
Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, New York.Google Scholar
Shi, J. Y. (1986). The Kazhdan–Lusztig Cells in Certain Affine Weyl Groups (Lecture Notes Math. 1179). Springer, Berlin.Google Scholar
Stanley, R. P. (1997). Parking functions and noncrossing partitions. Electron. J. Combin. 4, R20.CrossRefGoogle Scholar
Stanley, R. P. (1998). Hyperplane arrangements, parking functions and tree inversions. In Mathematical Essays in Honor of Gian-Carlo Rota (Progress Math. 161), ed. B. E. Sagan and R. P. Stanley, pp. 359–375. Birkhäuser, Boston.Google Scholar
Stanley, R. P. and Pitman, J. (2002). A polytope related to empirical distributions, plane trees, parking functions, and the associahedron. Discrete Comput. Geom. 27, 603–634.CrossRefGoogle Scholar
Wellner, J. A. (2018). The Cramér–Chernoff method and some exponential bounds. Available at https://sites.stat.washington.edu/jaw/COURSES/580s/581/HO/Chernoff-Cramer.pdf Google Scholar
Yan, C. H. (2015). Parking functions. In Handbook of Enumerative Combinatorics (Discrete Math. Appl.), ed. M. Bóna, pp. 835–893. CRC Press, Boca Raton, FL.Google Scholar
Yin, M. (2023). Parking functions: interdisciplinary connections. Adv. Appl. Prob. Available at doi:10.1017/apr.2022.49.CrossRefGoogle Scholar