CUTOFF FOR RANDOM TO RANDOM CARD SHUFFLE

• 成果类型: Article
• 署名作者: Bernstein, Megan; Nestoridi, Evita
• 署名单位: University System of Georgia; Georgia Institute of Technology; Princeton University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/19-AOP1340
• 发表日期: 2019
• 页码: 3303-3320
• 关键词: inhomogeneous markov-chains; time

摘要

In this paper, we use the eigenvalues of the random to random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4 n log n - 1/4 n log log n with window of order n, answering a conjecture of Diaconis.