Probabilistic \((m, n)\)-parking functions

Pamela Harris¹ ; Rodrigo Ribeiro² ; Mei Yin²

¹University of Wisconsin - Milwaukee
²University of Denver

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

In this article, we establish new results on the probabilistic parking model (introduced by Durmić, Han, Harris, Ribeiro, and Yin) with $m$ cars and $n$ parking spots and probability parameter $p \in [0,1]$. For any $m \leq n$ and $p \in [0,1]$, we study the parking preference of the last car, denoted $a_m$, and determine the conditional distribution of $a_m$ and compute its expected value. We show that both formulas depict explicit dependence on the probability parameter $p$. We study the case where $m=cn$ for some $0<c<1$ and investigate the asymptotic behavior and show that the presence of ``extra spots'' on the street significantly affects the rate at which the conditional distribution of $a_m$ converges to the uniform distribution on $[n]$. Even for small $\varepsilon=1-c$, an $\varepsilon$-proportion of extra spots reduces the convergence rate from $1/\sqrt{n}$ to $1/n$ when $p\neq 1/2$. Additionally, we examine how the convergence rate depends on $c$, while keeping $n$ and $p$ fixed. We establish that as $c$ approaches zero, the total variation distance between the conditional distribution of $a_m$ and the uniform distribution on $[n]$ decreases at least linearly in $c$.

Détail

DOI : 10.37236/13864

Classification : 90B06, 05A19, 05A15, 60C05, 05A16