CUTOFF FOR THE ASYMMETRIC RIFFLE SHUFFLE

• 成果类型: Article
• 署名作者: Sellke, Mark
• 署名单位: Stanford University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/22-AOP1582
• 发表日期: 2022
• 页码: 2244-2287
• 关键词: mixing time-bounds; random-walks

摘要

In the Gilbert-Shannon-Reeds shuffle, a deck of N cards is cut into two approximately equal parts which are riffled together uniformly at random. Bayer and Diaconis (Ann. Appl. Probab. 2 294-313) famously showed that this Markov chain undergoes cutoff in total variation after 3 log(N) 2log(2) shuffles. We establish cutoff for the more general asymmetric riffle shuffles in which one cuts the deck into differently sized parts. The value of the cutoff point confirms a conjecture of Lalley from 2000 (Ann. Appl. Probab. 10 1302- 1321). Some appealing consequences are that asymmetry always slows mix-ing and that total variation mixing is strictly faster than separation and L degrees O mixing.