Shuffling via Transpositions
Preprint
Abstract
We consider a family of card shuffles of $n$ cards, where the allowed moves involve transpositions corresponding to the Jucys--Murphy elements of $\{S_m\}_{m \leq n}$. We diagonalize the transition matrix of these shuffles. As a special case, we consider the $k$-star transpositions shuffle, a natural interpolation between random transpositions and star transpositions. We proved that the $k$-star transpositions shuffle exhibits total variation cutoff at time $\frac{2n-(k+1)}{2(n-1)}n\log n$ with a window of $\frac{2n-(k+1)}{2(n-1)}n$. Furthermore, we prove that for the case where $k/n \rightarrow 0$ or $1$, this shuffle has the same limit profile as random transpositions, which has been fully determined by Teyssier.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Cutoff for a one-sided transposition shuffleThe Annals of Applied Probability, 2021
- The interchange process on high-dimensional productsThe Annals of Applied Probability, 2021
- Limit profile for random transpositionsThe Annals of Probability, 2020
- Cutoff for random to random card shuffleThe Annals of Probability, 2019
- 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
- Proof of Aldous’ spectral gap conjectureJournal of the American Mathematical Society, 2010
- A phase transition in the random transposition random walkProbability Theory and Related Fields, 2005
- Applications of non-commutative fourier analysis to probability problems1988
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981