Shuffling by semi-random transpositions
| dc.creator | Mossel, Elchanan | |
| dc.creator | Peres, Yuval | |
| dc.creator | Sinclair, Alistair | |
| dc.date | 2004-04-23 | |
| dc.date.accessioned | 2026-07-07T05:07:41Z | |
| dc.date.available | 2026-07-07T05:07:41Z | |
| dc.description | 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 $Θ(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. | |
| dc.identifier | https://arxiv.org/abs/math/0404438 | |
| dc.identifier | http://arxiv.org/abs/math/0404438 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70957 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | Shuffling by semi-random transpositions | |
| dc.type | text |