文章基本信息

标题：Mixing Time of the Rudvalis Shuffle
本地全文：下载
作者：Wilson, David Bruce
期刊名称：Electronic Communications in Probability
印刷版ISSN：1083-589X
出版年度：2003
卷号：8
页码：77-85
DOI：10.1214/ECP.v8-1071
出版社：Electronic Communications in Probability
摘要：We extend a technique for lower-bounding the mixing time of card-shuffling Markov chains, and use it to bound the mixing time of the Rudvalis Markov chain, as well as two variants considered by Diaconis and Saloff-Coste. We show that in each case $\Theta(n^3 \log n)$ shuffles are required for the permutation to randomize, which matches (up to constants) previously known upper bounds. In contrast, for the two variants, the mixing time of an individual card is only $\Theta(n^2)$ shuffles.
关键词：Markov chain, card shuffling, mixing time;60J10, 60C05