Cutoff for a one-sided transposition shuffle
Authors:
- 1 August 2021
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 31 (4) , 1746-1773
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 nonconstant 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 nlogn. 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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Cutoff for random to random card shuffleThe Annals of Probability, 2019
- Cutoff for conjugacy-invariant random walks on the permutation groupProbability Theory and Related Fields, 2018
- Spectral analysis of random-to-random Markov chainsAdvances in Mathematics, 2018
- Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusionThe Annals of Probability, 2016
- Effect of scale on long-range random graphs and chromosomal inversionsThe Annals of Applied Probability, 2012
- Mixing times for random k-cycles and coalescence-fragmentation chainsThe Annals of Probability, 2011
- Markov Chains and Mixing Times2008
- Shuffling by Semi-Random Transpositions2004
- Random Walks on Finite Groups2004
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981