The overhand shuffle mixes in \(\Theta(n^2\log n)\) steps (Q2494578)

The overhand shuffle is the shuffling technique where you gradually transfer the deck from, say, your right hand to your left hand by sliding off small packets from the top of the deck. \textit{R. Pemantle} [J. Theor. Probab. 2, No. 1, 37--49 (1989; Zbl 0668.60060)] introduced and analyzed a probabilistic model for the overhand shuffle and established upper and lower bounds of order \(n^{2}\log n\) and \(n^{2}\), respectively, for the mixing time on a deck of \(n\) cards. In this paper the author uses an extension of a lemma of \textit{D. B. Wilson} [Ann. Appl. Probab. 14, No.~1, 274--325 (2004; Zbl 1040.60063)] to establish a lower bound of order \(n^{2}\log n\), thereby showing that \(n^{2}\log n\) is indeed the correct order of mixing time.