  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.
