Mixing times for random \(k\)-cycles and coalescence-fragmentation chains (Q651005)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Mixing times for random \(k\)-cycles and coalescence-fragmentation chains |
scientific article |
Statements
Mixing times for random \(k\)-cycles and coalescence-fragmentation chains (English)
0 references
8 December 2011
0 references
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\).
0 references
mixing times
0 references
coalescence
0 references
cutoff phenomena
0 references
random cycles
0 references
random transpositions
0 references
