The overhand shuffle mixes in $Θ(n^2\log n)$ steps
| dc.creator | Jonasson, Johan | |
| dc.date | 2005-01-24 | |
| dc.date | 2006-03-14 | |
| dc.date.accessioned | 2026-07-07T06:39:20Z | |
| dc.date.available | 2026-07-07T06:39:20Z | |
| dc.description | 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. | |
| dc.description | Published at http://dx.doi.org/10.1214/105051605000000692 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org) | |
| dc.identifier | https://arxiv.org/abs/math/0501401 | |
| dc.identifier | http://arxiv.org/abs/math/0501401 | |
| dc.identifier | Annals of Applied Probability 2006, Vol. 16, No. 1, 231-243 | |
| dc.identifier | doi:10.1214/105051605000000692 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/101040 | |
| dc.subject | Probability | |
| dc.subject | 60G99, 60J99 (Primary) | |
| dc.title | The overhand shuffle mixes in $Θ(n^2\log n)$ steps | |
| dc.type | text |