View PDF HTML (experimental)

Abstract:We study the last-success problem for sequential Bernoulli trials in the homogeneous setting where $X_1,\ldots,X_n$ are i.i.d. Bernoulli$(p)$, with unknown $p\in(0,1)$. For known $p$, Bruss' sum-the-odds theorem gives an optimal threshold rule with win probability $V_n(p)$; for unknown $p$, the odds driving this threshold must be learned online from the same sequence on which one is trying to stop. We analyze the resulting statistical decision problem over all $p$-blind rules, and write $W_n(p)$ for the win probability of the natural plug-in odds rule. Our main result is an exact asymptotic minimax theorem: for any $p_0\in(0,\tfrac12)$, the limit of $\sqrt n\,\inf_\pi\sup_{p\in[p_0,1)}\{V_n(p)-W_n^\pi(p)\}$, where the infimum is over all possibly randomized $p$-blind rules, is $C_\star=\tfrac12\sup_{u>0}u\Phi(-u)=0.08498\ldots$, with $\Phi$ denoting the standard normal distribution function. The same constant is attained by the plug-in rule, which is therefore asymptotically minimax optimal. The result is local in nature: at each transition point $p=1/k$, where the oracle threshold jumps, the deficit has an exact local minimax constant proportional to $\gamma_k=(1-\tfrac1k)^{k-2}\{k^{-1}(1-k^{-1})\}^{1/2}$, and the global least favourable point is $k=2$. Thus the root-$n$ barrier is caused not by estimating $p$ itself, but by the discontinuity of the oracle action. We also quantify the price of sample splitting: estimating $p$ on an initial fraction $a$ of the horizon and then freezing the estimate is rate-optimal but inflates the sharp constant by $1/\sqrt a$. Finally, in sparse regimes $p=p_n\to0$ with $np_n\to\infty$, the plug-in rule is asymptotically oracle-optimal, and the critical window $p\asymp1/n$ is a genuine barrier: no $p$-blind rule can converge uniformly to the oracle win probability over all $p\in(0,1)$.

Submission history

From: Davy Paindaveine [view email]
[v1] Wed, 8 Apr 2026 15:12:14 UTC (155 KB)
[v2] Thu, 6 Aug 2026 11:01:46 UTC (233 KB)