The overhand shuffle mixes in .(n2logn) steps

Authors
Citation
Jonasson, Johan, The overhand shuffle mixes in .(n2logn) steps, Annals of applied probability , 16(1), 2006, pp. 231-243
ISSN journal
10505164
Volume
16
Issue
1
Year of publication
2006
Pages
231 - 243
Database
ACNP
SICI code
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 n2 and at most of order n2logn. 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 n2logn, thereby showing that n2logn 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 .(n3logn) lower bound of Wilson [Electron. Comm. Probab. 8 (2003) 77.85] for the Rudvalis shuffle.