Cutoff for a One-sided Transposition Shuffle

Michael Bate, Stephen Connor, Oliver Matheau-Raven

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)1746-1773
Number of pages28
JournalThe Annals of Applied Probability
Issue number4
Publication statusPublished - 1 Aug 2021

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Cite this