Mixing times via super-fast coupling
From MaRDI portal
Publication:6477889
arXivmath/0609568MaRDI QIDQ6477889FDOQ6477889
Authors: Robert Burton, Yevgeniy Kovchegov 
Publication date: 20 September 2006
Abstract: We provide a coupling proof that the transposition shuffle on a deck of n cards is mixing of rate Cn(log{n}) 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.
This page was built for publication: Mixing times via super-fast coupling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6477889)
