The S_k Shuffle Block Dynamics

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 when k = o(N ^{3 2} ) the pre-cutoff phenomenon occurs. Furthermore, we show that for a suitable modification of the model, the S_k shuffle with boundaries, the cutoff phenomenon occurs when k = o(N ^{1 6} ).