 |
|
|
| | | | | |
|
|
|
|
|
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 Θ(n3 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
Θ(n2) shuffles.
|
Full text: PDF
Pages: 77-85
Published on: June 24, 2003
|
Bibliography
-
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.
-
Persi Diaconis.
Group Representations in Probability and Statistics.
Institute of Mathematical Statistics, 1988.
MR 90a:60001
-
Persi Diaconis.
The cutoff phenomenon in finite Markov chains.
Proceedings of the National Academy of Sciences, USA,
93:1659--1664, 1996.
MR 97b:60112
-
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
-
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
-
Martin V. Hildebrand.
Rates of Convergence of Some Random Processes on Finite Groups.
PhD thesis, Harvard University, 1990.
-
Laurent Saloff-Coste.
Lower bound in total variation for finite Markov chains: Wilson's
lemma, 2002.
Manuscript.
-
Elizabeth L. Wilmer.
Exact Rates of Convergence for Some Simple Non-Reversible Markov Chains.
PhD thesis, Harvard University, 1999.
-
Elizabeth L. Wilmer.
A local limit theorem for a family of non-reversible Markov chains,
2002.
arXiv:math.PR/0205189.
-
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.
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context