Perfect shuffling with fewer lazy transpositions

Abstract

A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)\in S_n$ with probability $p$. How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length $\frac{2}{3}\left(\genfrac{}{}{0ex}{}{n}{2}\right)+O(n\log n)$, and consider some related questions.

23 pages, 5 figures, 1 table