The overhand shuffle mixes in Θ(n2log n) steps

• 成果类型: Article
• 署名作者: Jonasson, J
• 署名单位: Chalmers University of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051605000000692
• 发表日期: 2006
• 页码: 231-243
• 关键词: markov-chains

摘要

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.