Mixing Time of the Rudvalis Shuffle

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.

9 pages

References in corpus (2)

• Mixing times of lozenge tiling and card shuffling Markov chains
• A local limit theorem for a family of non-reversible Markov chains

Cited by in corpus (4)

• The overhand shuffle mixes in $\Theta (n^2\log n)$ steps
• Analysis of top to bottom-$k$ shuffles
• Biased random-to-top shuffling
• Card shuffling and diophantine approximation