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

DOI10.1214/10-AOP634zbMATH Open1245.60006arXiv1001.1894MaRDI QIDQ651005FDOQ651005

Authors: Nathanaël Berestycki, Oded Schramm, Ofer Zeitouni 

Publication date: 8 December 2011

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

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

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

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

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)

Cites Work

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

Cited In (20)

• Cutoff for a one-sided transposition shuffle
• The random \((n-k)\)-cycle to transpositions walk on the symmetric group
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• The random \(k\) cycle walk on the symmetric group
• Double coset Markov chains
• Cutoff profiles for quantum Lévy processes and quantum random transpositions
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Random generators of the symmetric group: diameter, mixing time and spectral gap.
• The \(S_k\) shuffle block dynamics
• Rapidly mixing random walks and bounds on characters of the symmetric group
• Title not available (Why is that?)
• Mixing times for the mean-field Blume-Capel model via aggregate path coupling
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Cutoff for rewiring dynamics on perfect matchings
• Limit profiles for reversible Markov chains
• Some things we've learned (about Markov chain Monte Carlo)
• Cutoff for conjugacy-invariant random walks on the permutation group
• Limit profile for random transpositions
• Elementary bounds on mixing times for decomposable Markov chains
• A phase transition for repeated averages

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)