No-feedback card guessing for dovetail shuffles

Authors
Citation
Ciucu, Mihai, No-feedback card guessing for dovetail shuffles, Annals of applied probability , 8(4), 1998, pp. 1251-1269
ISSN journal
10505164
Volume
8
Issue
4
Year of publication
1998
Pages
1251 - 1269
Database
ACNP
SICI code
Abstract
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.2log2(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 log2(2n) shuffles to obtain a well-mixed deck, a fact proved by Bayer and Diaconis. We also show that if k=clog2(2n) with 1<c<2, then the above guessing strategy is not the best.