A strong stationary time for random transpositions

Abstract

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

Cited by in corpus (1)

• Random Walks on the Symmetric Group: Cutoff for One-sided Transposition Shuffles