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

DOI10.1214/10-AOP634MaRDI QIDQ651005zbMATH OpenFDO

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

coalescencecutoff phenomenamixing timesrandom cyclesrandom transpositions

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$.

Review text

Let \(\mathcal{S}_n\) be the permutation group on \(n\) elements, and consider a random walk on \(\mathcal{S}_n\), with step distribution uniform on \(k\)-cycles. The paper proves a well-known conjecture that the mixing time of this process is \((1/k)n\log n\), with threshold of width linear in \(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

• Asymptotic theory of characters of the symmetric group
• Compositions of random transpositions
• Generating a random permutation with random transpositions
• 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?)
• 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

(24)

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

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)