Cutoff for a One-sided Transposition Shuffle

Abstract

We introduce a new type of card shuffle called one-sided transpositions. At each step a card is chosen uniformly from the pack and then transposed with another card chosen uniformly from below it. This defines a random walk on the symmetric group generated by a distribution which is non-constant on the conjugacy class of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided transposition shuffle at time $n\log n$. We also study a weighted generalisation of the shuffle which, in particular, allows us to recover the well known mixing time of the classical random transposition shuffle.

24 pages. In this revised paper we prove the existence of a total variation cutoff for the biased one-sided transposition shuffles with bias $\alpha \ge 1$. This completes the proof of the existence of a cutoff for any biased one-sided transposition shuffle with bias $\alpha \in \mathbb{R}$