Mixing times via super-fast coupling

2006/09/20 by Robert Burton, Burton, Robert, Yevgeniy Kovchegov +1
Computer Science · Mathematics · #37A25 #60C05 #Algorithms and Data Compression #Cellular Automata and Applications #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #math.PR #msc:37A25 #msc:60C05

paper · pdf · doi:10.48550/arxiv.math/0609568

openalex publication_date 2006/09/20 · arxiv created 2011/09/15 · arxiv updated 2011/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide a coupling proof that the transposition shuffle on a deck of n cards is mixing of rate Cn(logn) with a moderate constant, C. This rate was determined by Diaconis and Shahshahani, but the question of a natural probabilistic coupling proof has been missing, and questions of its existence have been raised. The proof, and indeed any proof, requires that we enlarge the methodology of coupling to include intuitive but non-adapted coupling rules, because a typical Markovian coupling is incapable of resolving finer questions of rates.

Citations

• Some Limit Theorems for Random Functions. II

Related

• Partial mixing of semi-random transposition shuffles
• Mixing time of the Card-Cyclic-to-Random shuffle
• A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck
• Mixing time of the torus shuffle
• Mixing times of the biased card shuffling and the asymmetric exclusion process