Answers are grounded in this paper and cite their sources.
For odd n, the random walk on the symmetric group Sₙ generated by the transposition $(1,2)$ and the n-cycle (1,2,,n) needs order n³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↦ 2x n of Z/nZ reduces the mixing time to O(nlog³ 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 nlog n steps. So the best added permutation brings the mixing time from order n³log n to n¹⁺ᵒ⁽¹⁾; its exact order, and which permutation attains it, remain open.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: