MIXING TIME OF THE CARD-CYCLIC-TO-RANDOM SHUFFLE

• 成果类型: Article
• 署名作者: Morris, Ben; Ning, Weiyang; Peres, Yuval
• 署名单位: University of California System; University of California Davis; University of Washington; University of Washington Seattle; Microsoft
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP964
• 发表日期: 2014
• 页码: 1835-1849
• 关键词: random transpositions; markov-chains

摘要

The card-cyclic-to-random shuffle on n cards is defined as follows: at time t remove the card with label t mod n and randomly reinsert it back into the deck. Pinsky [Probabilistic and combinatorial aspects of the card-cyclic-to-random shuffle (2011). Unpublished manuscript] Introduced this shuffle and asked how many steps are needed to mix the deck. He showed n steps do not suffice. Here we show that the mixing time is on the order of Theta (n log n).