CUTOFF FOR THE CYCLIC ADJACENT TRANSPOSITION SHUFFLE

• 成果类型: Article
• 署名作者: Nam, Danny; Nestoridi, Evita
• 署名单位: Princeton University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/19-AAP1495
• 发表日期: 2019
• 页码: 3861-3892
• 关键词: inhomogeneous markov-chains; mixing time

摘要

We study the cyclic adjacent transposition (CAT) shuffle of n cards, which is a systematic scan version of the random adjacent transposition (AT) card shuffle. In this paper, we prove that the CAT shuffle exhibits cutoff at n(3)/2 pi(2) log n, which concludes that it is twice as fast as the AT shuffle. This is the first verification of cutoff phenomenon for a time-inhomogeneous card shuffle.