Mixing times for random k-cycles and coalescence-fragmentation chains

Abstract

Let ${\mathcal{S}}_n$ be the permutation group on $n$ elements, and consider a random walk on ${\mathcal{S}}_n$ whose step distribution is uniform on $k$-cycles. We prove a well-known conjecture that the mixing time of this process is $(1/k)n\log n$, with threshold of width linear in $n$. Our proofs are elementary and purely probabilistic, and do not appeal to the representation theory of ${\mathcal{S}}_n$.

Published in at http://dx.doi.org/10.1214/10-AOP634 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Refined estimates for some basic random walks on the symmetric and alternating groups

Cited by in corpus (14)

• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Some things we've learned (about Markov chain Monte Carlo)
• Limit Profiles for Reversible Markov Chains
• Cutoff phenomenon for the simple exclusion process on the complete graph
• A phase transition for repeated averages
• Random Walks on the Symmetric Group: Cutoff for One-sided Transposition Shuffles
• Partial mixing of semi-random transposition shuffles
• The $S_k$ shuffle block dynamics
• Cutoff for Rewiring Dynamics on Perfect Matchings
• Emergence of giant cycles and slowdown transition in random transpositions and $k$-cycles
• Mixing time and cutoff phenomenon for the interchange process on dumbbell graphs and the labelled exclusion process on the complete graph
• The random (n-k)-cycle to transpositions walk on the symmetric group
• Limit profile for random transpositions
• Mixing of fast random walks on dynamic random permutations