The distribution on permutations induced by a random parking function

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 (\frac{(2-\epsilon {)}^n}{(n+1{)}^{n-1}},\frac{(2+\epsilon {)}^n}{(n+1{)}^{n-1}})$. 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 }_{n-j+1}^{-1}=i_1,{\sigma }_{n-j+2}^{-1}=i_2,\cdots ,{\sigma }_n^{-1}=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 }_{n-j+l}^{-1},n+1-{\sigma }_{n-j+2}^{-1},\cdots ,n+1-{\sigma }_n^{-1})$ under $P_n^{\text{park}}$ converges in distribution to a random vector $({\sum }_{r=1}^j{X}_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^{\frac{1}{6}})$, the final $j_n$ cars will park in increasing order with probability approaching 1 as $n\to \mathrm{\infty }$. We also obtain an explicit formula for the expected value of the left-to-right maximum statistic $X_n^{\text{LR-max}}$, which counts the total number of left-to-right maxima in a permutation, and show that $E_n^{\text{park}}{X}_n^{\text{LR-max}}$ grows approximately on the order $n^{\frac{1}{2}}$.