A Coupling Argument for the Random Transposition Walk

Abstract

This paper explores the mixing time of the random transposition walk on the symmetric group. While it has long been known that this walk mixes in order n*log(n) time, this result has not previously been attained using coupling. A coupling argument showing the correct order mixing time is presented. This is accomplished by first projecting to conjugacy classes, and then using the Bubley-Dyer path coupling construction. In order to obtain appropriate bounds on the time it takes the path coupling to meet, ideas from Schramm's paper "Compositions of Random Transpositions" are used.

Cited by in corpus (7)

• Some things we've learned (about Markov chain Monte Carlo)
• The bead process for beta ensembles
• Partial mixing of semi-random transposition shuffles
• Cutoff for Rewiring Dynamics on Perfect Matchings
• A simple Markov chain for independent Bernoulli variables conditioned on their sum
• The random (n-k)-cycle to transpositions walk on the symmetric group
• Coupling for features of random walks