| The overhand shuffle mixes in Θ(n 2 log n) steps, http://www.math.chalmers.se/∼jonasson/recent.html (2008) | |||||||||||||||
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 [5] 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 [7] 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 [6] for the Rudvalis shuffle. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||