The random (n-k)-cycle to transpositions walk on the symmetric group

Abstract

We study the rate of convergence of the Markov chain on $S_n$ which starts with a random $(n-k)$-cycle for a fixed $k\ge 1$, followed by random transpositions. The convergence to the stationary distribution turns out to be of order $n$. We show that after $cn+\frac{\ln k}{2}n$ steps for $c>0$, the law of the Markov chain is close to the uniform distribution. The character of the defining representation is used as test function to obtain a lower bound for the total variation distance. We identify the asymptotic distribution of the test function given the law of the Markov chain for the $(n-1)$-cycle case. The upper bound relies on estimates for the difference of normalized characters.

23 pages, 3 figures; to appear in Journal of Theoretical Probability

References in corpus (2)

• Mixing times for random k-cycles and coalescence-fragmentation chains
• A Coupling Argument for the Random Transposition Walk