Limit Theorems for the Complete Feedback Card Guessing Game

Source abstract

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})\leq C((\log\log n)^2+m/\log n)$, uniformly in $m$ for large $n$. This bound yields a central limit theorem for every sequence $m=m_n\geq1$ as $n\to\infty$. The score variance is asymptotic to its mean. We also give uniform Kolmogorov bounds using the conditional Bernoulli moments. For $m,n\to\infty$, the excess mean is asymptotic to $(\log n)\log\min\{m,\log n\}+(π/\sqrt2)\sqrt{m\log n}$. The two contributions balance at $m\asymp(\log n)(\log\log 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\to\infty$.