The $S_k$ shuffle block dynamics

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}})$.

arXiv comment21 pages, 1 figure

References in corpus (7)

• Mixing times of lozenge tiling and card shuffling Markov chains
• Glauber dynamics on trees:Boundary conditions and mixing time
• The Lee-Yang and Pólya-Schur Programs. I. Linear Operators Preserving Stability
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Mixing times for random k-cycles and coalescence-fragmentation chains
• Fluctuation results for general block spin Ising models
• Cutoff profile of the Metropolis biased card shuffling