EUVIMEDEUVIMED entdecken
Crossref

The Distribution on Permutations Induced by a Random Parking Function

Ross Pinsky

The Electronic Journal of Combinatorics · 13.03.2026 · 33 (1)

DOI: 10.37236/13842 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 13.03.2026. Verfasst von Ross Pinsky.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A parking function on $[n]$ creates a permutation in $S_n$ via the order in which the $n$ cars appear in the $n$ parking spaces. Placing the uniform probability measure on the set of parking functions on $[n]$ induces a probability measure on $S_n$. We initiate a study of some properties of this distribution. Let $P_n^{\text{park}}$ denote this distribution on $S_n$ and let $P_n$ denote the uniform distribution on $S_n$. In particular, we obtain an explicit formula for $P_n^{\text{park}}(\sigma)$ for all $\sigma\in S_n$. Then we show that for all but an asymptotically $P_n$-negligible set of permutations, one has $P_n^{\text{park}}(\sigma)\in\left(\frac{(2-\epsilon)^n}{(n+1)^{n-1}},\frac{(2+\epsilon)^n}{(n+1)^{n-1}}\right)$. However, this accounts for only an exponentially small part of the $P_n^{\text{park}}$-probability. We also obtain an explicit formula for $P_n^{\text{park}}(\sigma^{-1}_{n-j+1}=i_1,\sigma^{-1}_{n-j+2}=i_2,\cdots, \sigma^{-1}_n=i_j)$, the probability that the last $j$ cars park in positions $i_1,\cdots, i_j$ respectively, and show that the $j$-dimensional random vector $(n+1-\sigma^{-1}_{n-j+l}, n+1-\sigma^{-1}_{n-j+2},\cdots, n+1-\sigma^{-1}_{n})$ under $P_n^{\text{park}}$ converges in distribution to a random vector $(\sum_{r=1}^jX_r,\sum_{r=2}^j X_r,\cdots, X_{j-1}+X_j,X_j)$, where $\{X_r\}_{r=1}^j$ are IID with the Borel distribution. We then show that in fact for $j_n=o(n^\frac16)$, the final $j_n$ cars will park in increasing order with probability approaching 1 as $n\to\infty$. We also obtain an explicit formula for the expected value of the left-to-right maximum statistic $X_n^{\text{LR-max}}$, the statistic that counts the total number of lleft-to-right maxima in a permutation, and show that $E_n^{\text{park}}X_n^{\text{LR-max}}$ grows approximately on the order $n^\frac12$. In terms of car parking, the left-to-right maximum statistic counts the number of cars that park in the first available space.

Zitieren

APA

Pinsky, R. (2026). The Distribution on Permutations Induced by a Random Parking Function. The Electronic Journal of Combinatorics, 33(1). https://doi.org/10.37236/13842

Vancouver

Pinsky R. The Distribution on Permutations Induced by a Random Parking Function. The Electronic Journal of Combinatorics. 2026;33(1). doi:10.37236/13842

BibTeX
@article{Pinsky2026,
  author = {Pinsky, Ross},
  title = {The Distribution on Permutations Induced by a Random Parking Function},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {1},
  doi = {10.37236/13842}
}
Kostenlos starten →