Probabilistic parking functions

DOI10.37236/11649MaRDI QIDQ6133160zbMATH OpenFDO

Authors Irfan Durmić, Alex Han, Pamela E. Harris, Rodrigo Ribeiro, Mei Yin

Publication date 18 August 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2211.00536

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Combinatorial probability (60C05) Transportation, logistics and supply chain management (90B06)

Abstract: We consider the notion of classical parking functions by introducing randomness and a new parking protocol, as inspired by the work presented in the paper ``Parking Functions: Choose your own adventure, (arXiv:2001.04817) by Carlson, Christensen, Harris, Jones, and Rodr'iguez. Among our results, we prove that the probability of obtaining a parking function, from a length $n$ preference vector, is independent of the probabilistic parameter $p$. We also explore the properties of a preference vector given that it is a parking function and discuss the effect of the probabilistic parameter $p$. Of special interest is when $p=1/2$, where we demonstrate a sharp transition in some parking statistics. We also present several interesting combinatorial consequences of the parking protocol. In particular, we provide a combinatorial interpretation for the array described in OEIS A220884 as the expected number of preference sequences with a particular property related to occupied parking spots, which solves an open problem of Novelli and Thibon posed in 2020 (arXiv:1209.5959). Lastly, we connect our results to other weighted phenomena in combinatorics and provide further directions for research.

Review text

Summary: We consider the notion of classical parking functions by introducing randomness and a new parking protocol, as inspired by the work presented in the paper [Coll. Math. J. 52, No. 4, 254--264 (2021; Zbl 1505.97055)] by \textit{J. Carlson} et al. Among our results, we prove that the probability of obtaining a parking function, from a length \(n\) preference vector, is independent of the probabilistic parameter \(p\). We also explore the properties of a preference vector given that it is a parking function and discuss the effect of the probabilistic parameter \(p\). Of special interest is when \(p=1/2\), where we demonstrate a sharp transition in some parking statistics. We also present several interesting combinatorial consequences of the parking protocol. In particular, we provide a combinatorial interpretation for the array described in OEIS A220884 as the expected number of preference sequences with a particular property related to occupied parking spots. Lastly, we connect our results to other weighted phenomena in combinatorics and provide further directions for research.

Recommendations

• Probabilizing parking functions
• A generalization of parking functions allowing backward movement
• Parking functions: from combinatorics to probability
• Generalizing parking functions with randomness
• Parking functions

Cites work

• A refinement of Cayley's formula for trees
• A symmetric sum involving the Stirling numbers of the first kind
• An Occupancy Discipline and Applications
• Duplicial algebras, parking functions, and Lagrange inversion
• Edgeworth series for lattice distributions
• Forest volume decompositions and Abel-Cayley-Hurwitz multinomial expansions
• Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
• Generalizing parking functions with randomness
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• Mappings of acyclic and parking functions
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Parking Functions: Choose Your Own Adventure
• Parking functions: from combinatorics to probability
• Probabilizing parking functions

Cited in

(6)

• Generalizing parking functions with randomness
• Probabilizing parking functions
• Some enumerative properties of parking functions
• Probabilistic (m, n)-parking functions
• The golf model on \(\mathbb{Z}/n \mathbb{Z}\) and on \(\mathbb{Z}\)
• A Pollak proof for the number of weakly increasing parking functions

This page was built for publication: Probabilistic parking functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133160)