Mean and variance of the distance in the modified bubble-sort graph
We study the minimum number of cyclically adjacent swaps needed to sort a uniformly random permutation in $S_n$, equivalently its distance from the identity in the modified bubble-sort graph. We prove that the mean is $\frac{n^2-n+1}{6}$ for $n\ge2$, establishing the formula observed in computations by Kuznetsov and collaborators. We determine the variance as $\frac{n^3+2n^2+7n+21}{180}$ for $n\ge4$ and prove that the centred and scaled distance converges to a standard normal law, settling the CayleyPy project's Gaussian-limit conjecture for cyclic Coxeter generators. Finally, we show that the $r$-th moment is a polynomial in $n$ of degree $2r$ for $n\ge2r+1$.
Authors
- Vasco Schiavo
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.5281/zenodo.24311015
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- article
- Field-Weighted Citation Impact
- 0.00