Adding one permutation to a transposition and a long cycle
For odd $n$, the random walk on the symmetric group $S_n$ generated by the transposition $(1,2)$ and the $n$-cycle $(1,2,\dots,n)$ needs order $n^3\log n$ steps to mix. Diaconis asked whether adding one more permutation to this generating set can speed up the walk appreciably. We show that adding the doubling map $x\mapsto 2x \bmod n$ of $\mathbb{Z}/n\mathbb{Z}$ reduces the mixing time to $O(n\log^3 n)$. Every transposition is then a word of length $O(\log n)$ in the five moves, and a comparison with the random transposition walk that keeps track of the whole spectrum gives the bound. In the other direction, whatever permutation is added, the walk needs order $n\log n$ steps. So the best added permutation brings the mixing time from order $n^3\log n$ to $n^{1+o(1)}$; its exact order, and which permutation attains it, remain open.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24200517
- Primary Topic
- Probability and Statistical Research
- Type
- preprint