Shuffling by semi-random transpositions
Markov Chains in Algorithms and Statistical Physics
January 31, 2005 04:30 PM to 05:00 PM
Speakers:
|
 |
Abstract: |
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
few iterations of the cyclic-to-random-shuffle and for uniform random
permutations. Perhaps surprisingly, the proof hinges on the fact that
the function $e^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.
Joint work with Yuval Peres and Alistair Sinclair.
|
|
|
