Probabilistic Parking Functions

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íguez. 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.

22 pages, 3 figures, 4 tables