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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Adding one permutation to a transposition and a long cycle

Yitzchak Shmalo
Zenodo (CERN European Organization for Nuclear Research)
Probability and Statistical Research
preprint

Adding one permutation to a transposition and a long cycle

Yitzchak Shmalo
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Probability and Statistical Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon