The overhand shuffle mixes in $Θ(n^2\log n)$ steps

Details The overhand shuffle mixes in $Θ(n^2\log n)$ steps The overhand shuffle mixes in $Θ(n^2\log n)$ steps

2005-01-24

arxiv.org/abs/math/0501401v2

Annals of Applied Probability 2006, Vol. 16, No. 1, 231-243

Mathematics

Probability

Published at http://dx.doi.org/10.1214/105051605000000692 in the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051605000000692

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 $\Theta(n^3\log n)$ lower bound of Wilson [Electron. Comm. Probab. 8 (2003) 77--85] for the Rudvalis shuffle.

Affiliated with

Also associated with

No associations

Rating

The overhand shuffle mixes in $Θ(n^2\log n)$ steps does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The overhand shuffle mixes in $Θ(n^2\log n)$ steps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The overhand shuffle mixes in $Θ(n^2\log n)$ steps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312812