2005/01/31 by Johan Jonasson · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Extension (predicate logic) #Lemma (botany) #Markov Chains and Monte Carlo Methods #Mixing (physics) #Shuffling #Upper and lower bounds #math.PR #msc:60G99 #msc:60J99
paper · pdf · doi:10.1214/105051605000000692
published as Annals of Applied Probability 2006, Vol. 16, No. 1, 231-243 · 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)
openalex publication_date 2006/02/01 · arxiv created 2006/03/14 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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.