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.
Publié le : 2006-02-14
Classification:
Mixing time,
coupling,
lower bound,
Rudvalis shuffle,
60G99,
60J99
@article{1141654286,
author = {Jonasson, Johan},
title = {The overhand shuffle mixes in $\Theta$(n<sup>2</sup>logn) steps},
journal = {Ann. Appl. Probab.},
volume = {16},
number = {1},
year = {2006},
pages = { 231-243},
language = {en},
url = {http://dml.mathdoc.fr/item/1141654286}
}
Jonasson, Johan. The overhand shuffle mixes in Θ(n2logn) steps. Ann. Appl. Probab., Tome 16 (2006) no. 1, pp. 231-243. http://gdmltest.u-ga.fr/item/1141654286/