Shuffling by semi-random transpositions

Details Shuffling by semi-random transpositions Shuffling by semi-random transpositions

2004-04-23

arxiv.org/abs/math/0404438v1

Mathematics

Probability

Scientific paper

In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the k'th card along the circle with a uniformly chosen random card. The problem of determining the mixing time of the cyclic-to-random shuffle was raised by Aldous and Diaconis in 1986. Recently, Mironov used this shuffle as a model for the cryptographic system known as ``RC4'' and proved an upper bound of O(n log n) for the mixing time. We prove a matching lower bound, thus establishing that the mixing time is indeed of order $\Theta(n \log n)$. We also prove an upper bound of O(n log n) for the mixing time of any ``semi-random transposition shuffle'', i.e., any shuffle in which a random card is exchanged with another card chosen according to an arbitrary (deterministic or random) rule. To prove our lower bound, we exhibit an explicit complex-valued test function which typically takes very different values for permutations arising from the cyclic-to-random-shuffle and for uniform random permutations; we expect that this test function may be useful in future analysis of RC4. Perhaps surprisingly, the proof hinges on the fact that the function exp(z)-1 has nonzero fixed points in the complex plane. A key insight from our work is the importance of complex analysis tools for uncovering structure in nonreversible Markov chains.

Affiliated with

Also associated with

No associations

Rating

Shuffling by semi-random transpositions 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 Shuffling by semi-random transpositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shuffling by semi-random transpositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-1860