No-feedback card guessing for dovetail shuffles

• 成果类型: Article
• 署名作者: Ciucu, M
• 署名单位: Institute for Advanced Study - USA
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1998
• 页码: 1251-1269
• 关键词: riffle shuffles

摘要

We consider the following problem. A deck of 2n cards labeled consecutively from 1 on top to 2n on bottom is face down on the table. The deck is given k dovetail shuffles and placed back on the table, face down. A guesser tries to guess at the cards one at a time, starting from top. The identity of the card guessed at is not revealed, nor is the guesser told whether a particular guess was correct or not. The goal is to maximize the number of correct guesses. We show that, for k greater than or equal to 2 log(2)(2n) + 1, the best strategy is to guess card 1 for the first half of the deck and card 2n for the second half. This result can be interpreted as indicating that it suffices to perform the order of log(2)(2n) shuffles to obtain a well-mixed deck, a fact proved by Bayer and Diaconis. We also show that if k = c log(2)(2n) with 1 < c < 2, then the above guessing strategy is not the best.