arXiv · Oct 22, 2026
Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
By Ivan Viakhirev, Kirill Borodin, Grach Mkrtchian
Reporting the best of M noisy, unbiased scores overstates the winner's value by up to c√V, where V is the total noise variance and the sharp constant c depends on how the noise is dependent. It was known only at the two extremes, arbitrary dependence (√(M-1)/M) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is √(M-1)/(2M), and for pairwise nonnegatively correlated noise it is (M-1)/M; for uncorrelated noise this answers the maximum version of an open question about the expected range. Explicit finite constructions attain both. As a corollary, the bias of the cross-validation estimator is bounded sharply within each class. All theorems are formally verified in Lean 4. Across 448 language-model and classifier selection pipelines, designs with per-candidate items realize a median 0.75 of the independent-class ceiling. At a fixed item budget, scoring all candidates on shared items is markedly less optimistic than giving each candidate its own items.