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
    0 references
    0 references
    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

    Identifiers