MIXING TIME AND CUTOFF FOR THE ADJACENT TRANSPOSITION SHUFFLE AND THE SIMPLE EXCLUSION

• 成果类型: Article
• 署名作者: Lacoin, Hubert
• 署名单位: Instituto Nacional de Matematica Pura e Aplicada (IMPA)
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/15-AOP1004
• 发表日期: 2016
• 页码: 1426-1487
• 关键词: markov-chains; inequalities

摘要

In this paper, we investigate the mixing time of the adjacent transposition shuffle for a deck of N cards. We prove that around time N-2 logN/(2 pi(2)), the total variation distance to equilibrium of the deck distribution drops abruptly from 1 to 0, and that the separation distance has a similar behavior but with a transition occurring at time (N-2 logN)/pi(2). This solves a conjecture formulated by David Wilson. We present also similar results for the exclusion process on a segment of length N with k particles.