Name
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 cyclicto- 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 驴(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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/FOCS.2004.60 | FOCS |
Keywords | Field | DocType |
Markov processes,computational complexity,cryptography,random processes,theorem proving,complex analysis tools,complex-valued test function,cryptographic system,cyclic-to-random shuffle,mixing time,nonreversible Markov chains,semirandom transposition shuffle,uniform random permutations | Discrete mathematics,Combinatorics,Upper and lower bounds,Permutation,Stochastic process,Complex plane,Random permutation,Shuffling,Time complexity,Mathematics,Random function | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-7695-2228-9 | 3 |
PageRank | References | Authors |
0.59 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elchanan Mossel | 1 | 1725 | 145.16 |
| Yuval Peres | 2 | 523 | 53.68 |
| Alistair Sinclair | 3 | 1506 | 308.40 |