Mixing times via super-fast coupling
Mixing times via super-fast coupling
复制标题
通过超快速耦合实现混合时间
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Yevgeniy Kovchegov
中科院分区：
文献类型：
--
作者：
R. Burton;Yevgeniy Kovchegov
我们提供了一个耦合证明，在一副n张牌上的换位洗牌是速率Cn（log{n}）与一个中等常数C的混合。这个比率是由Diaconis和Shahshahani确定的，但是自然概率耦合证明的问题一直没有得到解决，并且它的存在性问题已经提出。证明，实际上任何证明，需要我们扩大耦合的方法，包括直观的，但不适应的耦合规则，因为一个典型的马尔可夫耦合是无法解决更精细的问题率。
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.