The $S_k$ shuffle block dynamics
Preprint
Abstract
We introduce and analyze the $S_k$ shuffle on $N$ cards, a natural generalization of the celebrated random adjacent transposition shuffle. In the $S_k$ shuffle, we choose uniformly at random a block of $k$ consecutive cards, and shuffle these cards according to a permutation chosen uniformly at random from the symmetric group on $k$ elements. We study the total-variation mixing time of the $S_k$ shuffle when the number of cards $N$ goes to infinity, allowing also $k=k(N)$ to grow with $N$. In particular, we show that the cutoff phenomenon occurs when $k=o(N^{\frac{1}{6}})$.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Cutoff and Dynamical Phase Transition for the General Multi-component Ising ModelJournal of Statistical Physics, 2023
- Information percolation and cutoff for the random‐cluster modelRandom Structures & Algorithms, 2020
- Fluctuation Results for General Block Spin Ising ModelsJournal of Statistical Physics, 2020
- Can Extra Updates Delay Mixing?Communications in Mathematical Physics, 2013
- Mixing times for random k-cycles and coalescence-fragmentation chainsThe Annals of Probability, 2011
- Negative dependence and the geometry of polynomialsJournal of the American Mathematical Society, 2008
- Mixing times of the biased card shuffling and the asymmetric exclusion processTransactions of the American Mathematical Society, 2005
- Lectures on Glauber Dynamics for Discrete Spin Models1999
- Time to Reach Stationarity in the Bernoulli–Laplace Diffusion ModelSIAM Journal on Mathematical Analysis, 1987
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981