Analysis of top to bottom-k shuffles

• 成果类型: Article
• 署名作者: Goel, S
• 署名单位: Cornell University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/10505160500000062
• 发表日期: 2006
• 页码: 30-55
• 关键词: markov-chains; finite-groups; random-walks

摘要

A deck of n cards is shuffled by repeatedly moving the top card to one of the bottom k(n) positions uniformly at random, We give tipper and lower bounds on the total variation mixing time for this shuffle as k(n) ranges from a constant to n. We also consider a symmetric variant of this shuffle in which at each step either the top card is randomly inserted into the bottom k(n) positions or a random card from the bottom k(n) positions is moved to the top. For this reversible shuffle we derive bounds on the L-2 mixing time. Finally, we transfer mixing time estimates for the above shuffles to the lazy top to bottom-k walks that move with probability 1/2 at each step.