No-feedback card guessing for dovetail shuffles
Ciucu, Mihai
Ann. Appl. Probab., Tome 8 (1998) no. 1, p. 1251-1269 / Harvested from Project Euclid
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 \geq 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.
Publié le : 1998-11-14
Classification:  Card guessing,  dovetail shuffle,  riffle shuffle,  60C05,  60J10
@article{1028903379,
     author = {Ciucu, Mihai},
     title = {No-feedback card guessing for dovetail shuffles},
     journal = {Ann. Appl. Probab.},
     volume = {8},
     number = {1},
     year = {1998},
     pages = { 1251-1269},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1028903379}
}
Ciucu, Mihai. No-feedback card guessing for dovetail shuffles. Ann. Appl. Probab., Tome 8 (1998) no. 1, pp.  1251-1269. http://gdmltest.u-ga.fr/item/1028903379/