Mixing Time of the Rudvalis Shuffle

Details Mixing Time of the Rudvalis Shuffle Mixing Time of the Rudvalis Shuffle

2002-10-30

arxiv.org/abs/math/0210469v1

Electronic Communications in Probability, 8:77--85, 2003

Mathematics

Probability

9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Mixing Time of the Rudvalis Shuffle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Mixing Time of the Rudvalis Shuffle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixing Time of the Rudvalis Shuffle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-578419