Cutoff in total variation for the shelf shuffle

Abstract

We analyze the mixing time of a popular shuffling machine known as the shelf shuffler. It is a modified version of a $2m$-handed riffle shuffle ($m=10$ in casinos) in which a deck of $n$ cards is split multinomially into $2m$ piles, the even-numbered piles are reversed, and then cards are dropped from piles proportionally to their sizes. We prove that $\frac{5}{4}{\log }_{2m}n$ shuffles are necessary and sufficient to mix in total variation, and a cutoff occurs with constant window size. We also determine the cutoff profile in terms of the total variation distance between two shifted normal random variables.

1 figure