Shuffling by semi-random transpositions

In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the kth 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. 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 "semirandom 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.