Mixing Time of the Rudvalis Shuffle
Author:
Open Access
- 1 January 2003
- journal article
- Published by Institute of Mathematical Statistics in Electronic Communications in Probability
- Vol. 8 (none) , 77-85
Abstract
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.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- A Local Limit Theorem for a Family of Non-Reversible Markov ChainsJournal of Theoretical Probability, 2003
- The cutoff phenomenon in finite Markov chains.Proceedings of the National Academy of Sciences, 1996
- Comparison Techniques for Random Walk on Finite GroupsThe Annals of Probability, 1993
- Group representations in probability and statistics1988