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^{f r a c 16})

.

This page was built for publication: The $S_k$ shuffle block dynamics