A RULE OF THUMB FOR RIFFLE SHUFFLING

• 成果类型: Article
• 署名作者: Assaf, Sami; Diaconis, Persi; Soundararajan, K.
• 署名单位: Massachusetts Institute of Technology (MIT); Stanford University; Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/10-AAP701
• 发表日期: 2011
• 页码: 843-875
• 关键词: amazing matrix; random-walks; descents; carries; times; cards

摘要

We study how many riffle shuffles are required to mix n cards if only certain features of the deck are of interest, for example, suits disregarded or only the colors of interest. For these features the number of shuffles drops from 3/2 log(2) n to log(2) n. We derive closed formulae and an asymptotic rule of thumb formula which is remarkably accurate.