The overhand shuffle mixes in $Θ(n^2\log n)$ steps

Abstract

The overhand shuffle is one of the ``real'' card shuffling methods in the sense that some people actually use it to mix a deck of cards. A mathematical model was constructed and analyzed by Pemantle [J. Theoret. Probab. 2 (1989) 37--49] who showed that the mixing time with respect to variation distance is at least of order $n^2$ and at most of order $n^2\log n$. In this paper we use an extension of a lemma of Wilson [Ann. Appl. Probab. 14 (2004) 274--325] to establish a lower bound of order $n^2\log n$, thereby showing that $n^2\log n$ is indeed the correct order of the mixing time. It is our hope that the extension of Wilson's lemma will prove useful also in other situations; it is demonstrated how it may be used to give a simplified proof of the $Θ(n^3\log n)$ lower bound of Wilson [Electron. Comm. Probab. 8 (2003) 77--85] for the Rudvalis shuffle.