Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro
Abstract
We study the minimum and maximum expected scores over all adaptive strategies in sequential card guessing with yes/no feedback. A deck contains n labels, each appearing m times, and is shuffled uniformly. The cards are guessed one at a time, and after each guess the player is told only whether it was correct. Always guessing the same label gives exactly m points. How far can the expected score depart from m if all previous feedback is used either to seek or to avoid correct guesses? Diaconis, Graham, and Spiro conjectured that the minimum expectation is m−o(m) as m→∞ with n sufficiently large in terms of m, and that, for each fixed m, the limit superior of the maximum expectation as n→∞ is at most (e−1)m. Writing these extrema as P-m,n and P+m,n, we prove 0≤ m−P-m,n≤3m3/4 (n≥ m≥1), and the finite-parameter bound (P+m,n)/m≤∑k=1n1/k!<e−1 for all positive integers m,n. The first bound gives a first-order asymptotic uniform in n≥ m; the universal constant e−1 in the second cannot be reduced. Thus both conjectures follow. The lower bound combines a switching comparison for restricted permutations with martingale second-moment estimates. For the upper bound, we represent the repeated cards as a random interleaving of independent decks of distinct cards and prove that the optimal expectation is additive when the component-deck labels are revealed.
Related
- 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
- Optimal no-feedback card guessing after a fixed number of riffle shuffles
- Maximal Projection Constants and Extremal Vector Configurations: Some Conjectures and Examples
- Proportional-limit asymptotics for Diaconis-Ylvisaker-penalised logistic regression with fitted intercept
BibTeX
@misc{luo2026extremal,
title = {{Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro}},
author = {Congyi Luo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25062},
eprint = {2609.25062},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25062},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro
AU - Congyi Luo
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.25062
UR - https://arxiv.org/abs/2609.25062
AB - We study the minimum and maximum expected scores over all adaptive strategies in sequential card guessing with yes/no feedback. A deck contains n labels, each appearing m times, and is shuffled uniformly. The cards are guessed one at a time, and after each guess the player is told only whether it was correct. Always guessing the same label gives exactly m points. How far can the expected score depart from m if all previous feedback is used either to seek or to avoid correct guesses? Diaconis, Graham, and Spiro conjectured that the minimum expectation is m−o(m) as m→∞ with n sufficiently large in terms of m, and that, for each fixed m, the limit superior of the maximum expectation as n→∞ is at most (e−1)m. Writing these extrema as P^-_m,n and P^+_m,n, we prove 0≤ m−P^-_m,n≤3m^3/4 (n≥ m≥1), and the finite-parameter bound (P^+_m,n)/m≤∑_k=1^n1/k!<e−1 for all positive integers m,n. The first bound gives a first-order asymptotic uniform in n≥ m; the universal constant e−1 in the second cannot be reduced. Thus both conjectures follow. The lower bound combines a switching comparison for restricted permutations with martingale second-moment estimates. For the upper bound, we represent the repeated cards as a random interleaving of independent decks of distinct cards and prove that the optimal expectation is additive when the component-deck labels are revealed.
ER -