CUTOFF FOR A ONE-SIDED TRANSPOSITION SHUFFLE

• 成果类型: Article
• 署名作者: Bate, Michael E.; Connor, Stephen B.; Matheau-Raven, Oliver
• 署名单位: University of York - UK
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1632
• 发表日期: 2021
• 页码: 1746-1773
• 关键词: permutation

摘要

We introduce a new type of card shuffle called one-sided transpositions. At each step a card is chosen uniformly from the pack and then transposed with another card chosen uniformly from below it. This defines a random walk on the symmetric group generated by a distribution which is nonconstant on the conjugacy class of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided transposition shuffle at time n log n. We also study a weighted generalisation of the shuffle which, in particular, allows us to recover the well-known mixing time of the classical random transposition shuffle.