A strong stationary time for random transpositions

2019/10/02 by Graham White, White, Graham
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1910.00770

openalex publication_date 2019/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the random transposition walk on the symmetric group S_n has cutoff in separation distance at (1)/(2)n log n, by constructing a strong stationary time. The construction involves working with cycle types of permutations and some partition combinatorics.

Related

• A Coupling Argument for the Random Transposition Walk
• The random (n-k)-cycle to transpositions walk on the symmetric group
• Random Walks on the Generalized Symmetric Group: Cutoff for the One-sided Transposition Shuffle
• Refined estimates for some basic random walks on the symmetric and alternating groups
• A variation of strong stationary times for random walks with partial symmetries