Optimal no-feedback card guessing after a fixed number of riffle shuffles
Abstract
An ordered deck of n cards is subjected to k independent Gilbert--Shannon--Reeds riffle shuffles. A player then guesses each card without feedback, with repeated guesses allowed. For every fixed k≥1, we prove that, once n is sufficiently large, an optimal guess at position i in the top half of the deck is ⌊ i/2k⌋+1; the bottom-half strategy is obtained by reflection. We also show that the optimal expected number of correct guesses is 2√(n/((2k−1)π))+Ok(1). Our starting point is the result of our earlier work that the label at each position is distributed as an equally weighted mixture of 2k components, each a shifted sum of two independent binomial random variables (a Poisson-binomial distribution). The proof of the optimal strategy combines three ingredients: a uniform concentration estimate that separates the mixture components, exact binomial inequalities that control the gaps between competing peaks, and a coefficient comparison that resolves modal ties. The expected-score asymptotic is proved independently of the strategy, using only the peak heights of the mixture components.
Related
- Adhesive riffle shuffles: one-parameter models and mixing bounds
- Optimal complete-feedback card guessing under nonincreasing valley weights: A proof of the Diaconis-Fulman-Holmes shelf-shuffling conjecture
- Limit Theorems for the Complete Feedback Card Guessing Game
- Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro
- An upper bound on the proper hat guessing number of graphs
BibTeX
@misc{krityakierne2026optimal,
title = {{Optimal no-feedback card guessing after a fixed number of riffle shuffles}},
author = {Tipaluck Krityakierne and Thotsaporn Aek Thanatipanonda},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04339},
eprint = {2611.04339},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04339},
}
RIS
TY - UNPB
TI - Optimal no-feedback card guessing after a fixed number of riffle shuffles
AU - Tipaluck Krityakierne
AU - Thotsaporn Aek Thanatipanonda
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04339
UR - https://arxiv.org/abs/2611.04339
AB - An ordered deck of n cards is subjected to k independent Gilbert--Shannon--Reeds riffle shuffles. A player then guesses each card without feedback, with repeated guesses allowed. For every fixed k≥1, we prove that, once n is sufficiently large, an optimal guess at position i in the top half of the deck is ⌊ i/2^k⌋+1; the bottom-half strategy is obtained by reflection. We also show that the optimal expected number of correct guesses is 2√(n/((2^k−1)π))+O_k(1). Our starting point is the result of our earlier work that the label at each position is distributed as an equally weighted mixture of 2^k components, each a shifted sum of two independent binomial random variables (a Poisson-binomial distribution). The proof of the optimal strategy combines three ingredients: a uniform concentration estimate that separates the mixture components, exact binomial inequalities that control the gaps between competing peaks, and a coefficient comparison that resolves modal ties. The expected-score asymptotic is proved independently of the strategy, using only the peak heights of the mixture components.
ER -