Mixing Time of the Rudvalis Shuffle

David Bruce Wilson (Microsoft Research)

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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 77-85

Publication Date: June 24, 2003

DOI: 10.1214/ECP.v8-1071

References

  1. David J. Aldous and James A. Fill. Reversible Markov Chains and Random Walks on Graphs. Book in preparation, http://www.stat.berkeley.edu/~aldous/RWG/book.html, 2005.
  2. Persi Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988. MR 90a:60001
  3. Persi Diaconis. The cutoff phenomenon in finite Markov chains. Proceedings of the National Academy of Sciences, USA, 93:1659--1664, 1996. MR 97b:60112
  4. Persi Diaconis and Laurent Saloff-Coste. Comparison techniques for random walk on finite groups. The Annals of Probability, 21(4):2131--2156, 1993. MR 95a:60009
  5. Persi Diaconis and Laurent Saloff-Coste. Random walks on finite groups: a survey of analytic techniques. In Probability measures on groups and related structures, XI (Oberwolfach, 1994), pages 44--75. World Sci. Publishing, 1995. MR 97k:60013
  6. Martin V. Hildebrand. Rates of Convergence of Some Random Processes on Finite Groups. PhD thesis, Harvard University, 1990.
  7. Laurent Saloff-Coste. Lower bound in total variation for finite Markov chains: Wilson's lemma, 2002. Manuscript.
  8. Elizabeth L. Wilmer. Exact Rates of Convergence for Some Simple Non-Reversible Markov Chains. PhD thesis, Harvard University, 1999.
  9. Elizabeth L. Wilmer. A local limit theorem for a family of non-reversible Markov chains, 2002. arXiv:math.PR/0205189.
  10. David B. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains, 2001. To appear in The Annals of Applied Probability. arXiv:math.PR/0102193.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.