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

DOI10.1214/10-AOP634MaRDI QIDQ651005zbMATHFDO

Authors Nathanaël Berestycki, Oded Schramm, Ofer Zeitouni

Publication date 8 December 2011

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.1894

zbMATH Keywords

mixing timescoalescencecutoff phenomenarandom transpositionsrandom cycles

Mathematics Subject Classification ID

Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Continuous-time Markov processes on discrete state spaces (60J27)

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)nlogn$, 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$.

Recommendations

• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Rapidly mixing random walks and bounds on characters of the symmetric group
• The random k cycle walk on the symmetric group
• Cutoff for conjugacy-invariant random walks on the permutation group
• The random \((n-k)\)-cycle to transpositions walk on the symmetric group

Cites work

• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• scientific article; zbMATH DE number 1552119 (Why is no real title available?)
• Asymptotic theory of characters of the symmetric group
• Compositions of random transpositions
• Generating a random permutation with random transpositions
• Logarithmic combinatorial structures: A probabilistic approach
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique
• Probability. Theory and examples.
• Random shuffles and group representations
• Rapidly mixing random walks and bounds on characters of the symmetric group
• Refined estimates for some basic random walks on the symmetric and alternating groups
• The cycle structure of random permutations
• The number of connected sparsely edged uniform hypergraphs
• Upper bound on the characters of the symmetric groups

Cited in

(23)

• Mixing times for the mean-field Blume-Capel model via aggregate path coupling
• Random generators of the symmetric group: diameter, mixing time and spectral gap.
• Mixing times for the commuting chain on CA groups
• The random \(k\) cycle walk on the symmetric group
• Random walks generated by the Ewens distribution on the symmetric group
• A phase transition for repeated averages
• Cutoff for conjugacy-invariant random walks on the permutation group
• Double coset Markov chains
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• scientific article; zbMATH DE number 2046051 (Why is no real title available?)
• Limit profile for random transpositions
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Cutoff for rewiring dynamics on perfect matchings
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Cutoff for a one-sided transposition shuffle
• Some things we've learned (about Markov chain Monte Carlo)
• Elementary bounds on mixing times for decomposable Markov chains
• Rapidly mixing random walks and bounds on characters of the symmetric group
• Limit profiles for reversible Markov chains
• Cutoff profiles for quantum Lévy processes and quantum random transpositions
• An analogue of Aldous's theorem on mixing times of a random walk for complex reflection groups
• The random \((n-k)\)-cycle to transpositions walk on the symmetric group
• The \(S_k\) shuffle block dynamics

This page was built for publication: Mixing times for random \(k\)-cycles and coalescence-fragmentation chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651005)