Least-Favorable Location for Binomial Top-$t$ Selection

Source abstract

Consider $k$ independent Bernoulli populations, each sampled $n$ times, and select the $t$ populations with the largest success counts, breaking ties uniformly. Classical monotonicity reduces the worst case over the preference zone with separation $δ$ to the slippage family with levels $p$ and $p+δ$, leaving only its absolute location $p\in[0,1-δ]$ undetermined. A Gaussian approximation suggests the symmetric center $p_{\mathrm c}=(1-δ)/2$, and the exact two-population problem is uniquely centered there for every $n\ge2$. For fixed $k,t$ and $δ\in(0,1)$, we prove that exact eventual centering holds precisely when $k=2t$. When $k\ne2t$, the least-favorable location $p_{n,k,t}^*$ satisfies $$p_{n,k,t}^*-p_{\mathrm c} =(k-2t)C_δn^{-1/2}e^{-nΓ_δ}\{1+o(1)\},$$ where $C_δ$ and $Γ_δ$ are explicit and positive. In either case, the least-favorable location is eventually unique. The proof writes incorrect selection as a union of pairwise misrankings and applies inclusion--exclusion, yielding a bipartite graph expansion. A single misranking has its exact maximum at the symmetric center and determines the central curvature; two-edge intersections sharing one population determine the central slope through their multiplicity imbalance; all remaining graphs have higher large-deviation rates.