Limit Theorems for the Complete Feedback Card Guessing Game
Abstract
We study the optimal score Tn,m in a complete feedback card guessing game. The deck has n types and m cards of each type. Its predictable compensator Sn,m is the sum of the conditional success probabilities. We prove that Var(Sn,m)≤ C((loglog n)2+m/log n), uniformly in m for large n. This bound yields a central limit theorem for every sequence m=mn≥1 as n→∞. The score variance is asymptotic to its mean. We also give uniform Kolmogorov bounds using the conditional Bernoulli moments. For m,n→∞, the excess mean is asymptotic to (log n)logmin{m,log n}+(π/√2)√(mlog n). The two contributions balance at masymp(log n)(loglog n)2. The variance proof uses reversed occupancy hitting times. Discrete hypergeometric tail estimates control their fluctuations in the large-deviation, Gaussian, and saturation regimes. For fixed n, we also show that the compensator has a Brownian-bridge functional limit as m→∞.
Related
- Optimal complete-feedback card guessing under nonincreasing valley weights: A proof of the Diaconis-Fulman-Holmes shelf-shuffling conjecture
- Optimal no-feedback card guessing after a fixed number of riffle shuffles
- Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro
- PERSISTENCE OF THE WIENER SAUSAGE: SAMPLING STABILITY AND LIMIT THEOREMS FOR BETTI-CURVE FUNCTIONALS OF DRIFTED PLANAR BROWNIAN MOTION
- Global central limit theorems for Markov chains
BibTeX
@misc{dey2026limit,
title = {{Limit Theorems for the Complete Feedback Card Guessing Game}},
author = {Partha S. Dey and Jaya M. Manthripragada},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17479},
eprint = {2610.17479},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17479},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Limit Theorems for the Complete Feedback Card Guessing Game
AU - Partha S. Dey
AU - Jaya M. Manthripragada
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17479
UR - https://arxiv.org/abs/2610.17479
AB - We study the optimal score T_n,m in a complete feedback card guessing game. The deck has n types and m cards of each type. Its predictable compensator S_n,m is the sum of the conditional success probabilities. We prove that Var(S_n,m)≤ C((loglog n)^2+m/log n), uniformly in m for large n. This bound yields a central limit theorem for every sequence m=m_n≥1 as n→∞. The score variance is asymptotic to its mean. We also give uniform Kolmogorov bounds using the conditional Bernoulli moments. For m,n→∞, the excess mean is asymptotic to (log n)logmin{m,log n}+(π/√2)√(mlog n). The two contributions balance at masymp(log n)(loglog n)^2. The variance proof uses reversed occupancy hitting times. Discrete hypergeometric tail estimates control their fluctuations in the large-deviation, Gaussian, and saturation regimes. For fixed n, we also show that the compensator has a Brownian-bridge functional limit as m→∞.
ER -