Mixing Time of the Overlapping Cycles Shuffle

Abstract

In each step of the overlapping cycles shuffle on $n$ cards, a fair coin is flipped which determines whether the $m$th card or the $n$th card is moved to the top of the deck. Angel, Peres, and Wilson showed the following interesting fact: If $m=\lfloor \alpha n\rfloor$ where $\alpha$ is rational, then the relaxation time of a single card in the overlapping cycles shuffle is $\theta (n^2)$. However if $\alpha$ is the golden ratio, then the relaxation time of a single card is $\theta (n^{\frac{3}{2}})$. We show that the mixing time of the entire deck under the overlapping cycles shuffle matches these bounds up to a factor of $\log (n{)}^3$. That is, the mixing time of the entire deck is $O(n^2\log (n{)}^3)$ if $\alpha$ is rational and $O(n^{\frac{3}{2}}\log (n{)}^3)$ if $\alpha$ is the golden ratio.