独立及非负相关噪声下赢家偏差的紧界

# Sharp Bounds on the Winner’s Bias under Independent and Nonnegatively Correlated Noise
Source: [https://arxiv.org/html/2610.31948](https://arxiv.org/html/2610.31948)
###### Abstract

Reporting the best ofMMnoisy, unbiased scores overstates the winner’s value by up toc​Vc\\sqrt\{V\}, whereVVis the total noise variance and the sharp constantccdepends on how the noise is dependent\. It was known only at the two extremes, arbitrary dependence \(\(M−1\)/M\\sqrt\{\(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\)/\(2​M\)\\sqrt\{\(M\-1\)/\(2M\)\}, and for pairwise nonnegatively correlated noise it is\(M−1\)/M\(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\.

## 1Introduction

#### The Problem\.

Selecting the best ofMMalternatives by noisy scores and reporting the winner’s score is a basic statistical operation\. If the selection scores are unbiased with total varianceVV, the reported maximum is optimistically biased, and the worst case of that bias over noise laws is governed by

cM=sup𝔼⁡\[maxi≤M⁡Zi\]∑iVar⁡Ziover mean\-zero​Z\.c\_\{M\}\\;=\\;\\sup\\frac\{\\mathbb\{E\}\\bigl\[\\max\_\{i\\leq M\}Z\_\{i\}\\bigr\]\}\{\\sqrt\{\\sum\_\{i\}\\operatorname\{Var\}Z\_\{i\}\}\}\\qquad\\text\{over mean\-zero \}Z\.

#### What Is Known\.

Under arbitrary dependence the sharp constant is\(M−1\)/M\\sqrt\{\(M\-1\)/M\}\([Aven, 1985](https://arxiv.org/html/2610.31948#bib.bib5)\), with tightness in the equal\-moments case due to[Arnold and Groeneveld \(1979\)](https://arxiv.org/html/2610.31948#bib.bib4)\. For i\.i\.d\. noise the sharp constant is\(M−1\)/M⁡\(2​M−1\)\(M\-1\)/\\sqrt\{M\(2M\-1\)\}\([Gumbel, 1954](https://arxiv.org/html/2610.31948#bib.bib18);[Hartley and David, 1954](https://arxiv.org/html/2610.31948#bib.bib19)\)\. Between these poles,[Bertsimas et al\. \(2006\)](https://arxiv.org/html/2610.31948#bib.bib8)compute tight bounds under covariance information as a per\-instance semidefinite program, and[Papadatos \(2016\)](https://arxiv.org/html/2610.31948#bib.bib26)proves the tight covariance\-informed bound atM=2M=2, stating the general\-MMclosed\-form problem as open\. The independent, non\-identically distributed case has, to our knowledge, no published sharp constant\.

#### The Gap\.

Neither pole describes how a selection is usually evaluated\. Candidates of different accuracy have different score variances, so their noise is not identically distributed and the i\.i\.d\. constant does not apply\. The arbitrary\-dependence constant does apply, but it ignores the structure that the evaluation design fixes\. Giving each candidate its own test items makes the noise independent, and scoring all candidates on the same items typically makes it positively correlated\. Both classes sit between the poles, and for neither is a closed\-form sharp constant known\. This paper supplies both\.

#### Contributions\.

1. 1\.Independent noise\(main result, Theorem 3\)\. The sharp constant is\(M−1\)/\(2​M\)\\sqrt\{\(M\-1\)/\(2M\)\}, attained exactly by one deterministic alternative plus an explicit two\-point cascade\. The proof reduces general laws to two\-point laws per arm, splits the problem intoMMconvex problems, and closes each with a factored cubic\.
2. 2\.Nonnegative correlation\(Corollary 1b\)\. The sharp constant is\(M−1\)/M\(M\-1\)/M, attained at finite parameters\. For uncorrelated noise this settles the maximum analogue of an open question of[Papadatos \(2016, Sec\. 7\)](https://arxiv.org/html/2610.31948#bib.bib26)\. With the two poles, the constants form a graded family, strictly ordered forM≥3M\\geq 3\(Table[1](https://arxiv.org/html/2610.31948#S3.T1)\)\.
3. 3\.Consequences\.The bias of the cross\-validation estimator is bounded sharply in each class \(Corollary 2\)\. With constant one this bound is Conjecture 1 of[van Hasselt \(2013\)](https://arxiv.org/html/2610.31948#bib.bib34), which already follows from[Aven \(1985\)](https://arxiv.org/html/2610.31948#bib.bib5); our constants sharpen it\. Against Gaussian noise the worst case is close at smallMM\(19% above for the independent class atM=4M=4\) and conservative by a factor of orderM/log⁡M\\sqrt\{M/\\log M\}at largeMM\(Table[2](https://arxiv.org/html/2610.31948#S3.T2)\)\.
4. 4\.Selection pipelines\(Sec\.[5](https://arxiv.org/html/2610.31948#S5)\)\. Over 448 configurations of language\-model and classifier selection, per\-candidate designs realize a median 0\.75 of the independent constant, and theCov≥0\\operatorname\{Cov\}\\geq 0hypothesis fails in one of nine populations, so it must be checked on the data\. At a fixed item budget, shared items incur a median 4\.9 times less optimism than per\-candidate items, against the factor 2\.1 the ceilings predict\.

#### Method Summary\.

Both dependent classes follow from one master inequality: Aven’s bound applied to deviations from the mean, proved by Samuelson’s inequality pointwise and then Cauchy–Schwarz\([Samuelson, 1968](https://arxiv.org/html/2610.31948#bib.bib31)\)\. Its covariance term is what separates the classes\. The independent case needs different machinery and occupies most of the appendix\.

#### Formal Verification\.

Every theorem, corollary and lemma in the paper is machine\-checked in Lean 4 with Mathlib, in about 7,900 lines with nosorryand no axioms beyond Lean’s standard three\. The statements are formalized for random variables on an arbitrary probability space, with independence, square integrability and zero mean as explicit hypotheses, so the formal theorems are those stated here and not special cases\. Attainment and the suprema are formalized too, so sharpness is checked as well as the bounds\. Appendix[E](https://arxiv.org/html/2610.31948#A5)maps each result to its Lean name\. The formalization will be released together with the code and the score matrices of the numerical study\.

## 2Setup and the Transfer Lemma

Alternatives \(arms\)i=1,…,Mi=1,\\dots,Mhave true meansμi\\mu\_\{i\},μ∗=maxi⁡μi\\mu^\{\*\}=\\max\_\{i\}\\mu\_\{i\}, gapsgi=μ∗−μi≥0g\_\{i\}=\\mu^\{\*\}\-\\mu\_\{i\}\\geq 0\. Selection scores area^i=μi\+Zi\\hat\{a\}\_\{i\}=\\mu\_\{i\}\+Z\_\{i\}with𝔼⁡\[Zi\]=0\\mathbb\{E\}\[Z\_\{i\}\]=0,Var⁡Zi=vi\\operatorname\{Var\}Z\_\{i\}=v\_\{i\},V=∑iviV=\\sum\_\{i\}v\_\{i\}\. The winner isI=arg​maxi⁡a^iI=\\argmax\_\{i\}\\hat\{a\}\_\{i\}\(ties broken uniformly\)\. Two estimators ofμ∗\\mu^\{\*\}:

- •the*max\-estimator*reportsa^I\\hat\{a\}\_\{I\}, withBias⁡\(ME\)=𝔼⁡\[a^I\]−μ∗∈\[0,𝔼⁡\[maxi⁡Zi\]\]\\operatorname\{Bias\}\(\\mathrm\{ME\}\)=\\mathbb\{E\}\[\\hat\{a\}\_\{I\}\]\-\\mu^\{\*\}\\in\[0,\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]\];
- •the*cross\-validation*\(double\)*estimator*evaluates an independent unbiased estimate atII, withBias⁡\(CV\)=−𝔼⁡\[gI\]∈\[−𝔼⁡\[maxi⁡Zi\],0\]\\operatorname\{Bias\}\(\\mathrm\{CV\}\)=\-\\mathbb\{E\}\[g\_\{I\}\]\\in\[\-\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\],0\]\.

###### Lemma 1\(transfer\)\.

𝔼⁡\[gI\]≤𝔼⁡\[maxj⁡Zj\]\\mathbb\{E\}\[g\_\{I\}\]\\leq\\mathbb\{E\}\[\\max\_\{j\}Z\_\{j\}\]\.

The max\-estimator side needs no lemma:a^I−μ∗≤ZI≤maxj⁡Zj\\hat\{a\}\_\{I\}\-\\mu^\{\*\}\\leq Z\_\{I\}\\leq\\max\_\{j\}Z\_\{j\}becauseμI≤μ∗\\mu\_\{I\}\\leq\\mu^\{\*\}\. So every upper bound on𝔼⁡\[maxi⁡Zi\]/V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}boundsBias⁡\(ME\)\\operatorname\{Bias\}\(\\mathrm\{ME\}\)and\|Bias⁡\(CV\)\|\|\\operatorname\{Bias\}\(\\mathrm\{CV\}\)\|alike, and the extremal constructions below approach their constants in the𝔼⁡\[gI\]\\mathbb\{E\}\[g\_\{I\}\]form as well, in the limit where each alternative’s deficit rises to its largest noise lead over the best alternative \(Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\)\. ForKK\-fold cross\-validation the bound applies fold\-wise and averages \(Appendix[A](https://arxiv.org/html/2610.31948#A1)\)\.

## 3Main Results

###### Theorem 1\(master bound\)\.

For any mean\-zeroZZ, withZ¯=\(1/M\)​∑iZi\\bar\{Z\}=\(1/M\)\\sum\_\{i\}Z\_\{i\}:

𝔼⁡\[maxi⁡Zi\]≤\(M−1\)/M⋅V−M​𝔼​\[Z¯2\]\.\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]\\;\\leq\\;\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\}\.

This is Aven’s \(1985\) bound applied to the deviationsZi−Z¯Z\_\{i\}\-\\bar\{Z\}; we record it with a short self\-contained proof \(Samuelson’s inequality pointwise, then Cauchy–Schwarz; Appendix[B](https://arxiv.org/html/2610.31948#A2)\) because the covariance correction termM​𝔼​\[Z¯2\]M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]is what separates the dependence classes below\. AtM=2M=2the bound is known to be tight under covariance information\([Papadatos, 2016](https://arxiv.org/html/2610.31948#bib.bib26), Cor\. 7\.1\)\. A quantitative comparison with Aven’s displayed covariance\-aware bounds, which run through a fixed reference arm, is given in Appendix[B](https://arxiv.org/html/2610.31948#A2): the centered form is tighter by a factor between 1 and2\\sqrt\{2\}, both ends attained\.

###### Corollary 1a\(arbitrary dependence\)\.

𝔼⁡\[maxi⁡Zi\]≤\(M−1\)/M⋅V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]\\leq\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\}, sharp\([Aven, 1985](https://arxiv.org/html/2610.31948#bib.bib5)\); the attaining law is the uniform\-index one\-up construction of[Arnold and Groeneveld \(1979\)](https://arxiv.org/html/2610.31948#bib.bib4)\.

###### Corollary 1b\(pairwise nonnegative correlation; new\)\.

IfCov⁡\(Zi,Zj\)≥0\\operatorname\{Cov\}\(Z\_\{i\},Z\_\{j\}\)\\geq 0for alli≠ji\\neq j, then

𝔼⁡\[maxi⁡Zi\]≤M−1M⋅V,\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]\\;\\leq\\;\\frac\{M\-1\}\{M\}\\cdot\\sqrt\{V\},and the constant is sharp already in the uncorrelated subclassCov=0\\operatorname\{Cov\}=0, attained there exactly at finite parameters by an explicit law \(uniform\-index one\-up plus an independent common shock whose variance cancels the one\-up covariances; Appendix[B\.3](https://arxiv.org/html/2610.31948#A2.SS3)\)\. With every covariance strictly positive the bound is not attained, so the constant is the sharp one for the class and not for each configuration in it\.

[Bertsimas et al\. \(2006, Sec\. 2\.4\)](https://arxiv.org/html/2610.31948#bib.bib8)compute the tight covariance\-informed bound as a per\-instance semidefinite program; Corollary 1b is the closed form of its value on the uncorrelated class, and answers the uncorrelated case of the question posed by[Papadatos \(2016, Sec\. 7\)](https://arxiv.org/html/2610.31948#bib.bib26)\.

###### Theorem 2\(independent noise, deterministic best alternative; new\)\.

For independent mean\-zeroZ1,…,ZmZ\_\{1\},\\dots,Z\_\{m\}, withV=∑i=1mVar⁡ZiV=\\sum\_\{i=1\}^\{m\}\\operatorname\{Var\}Z\_\{i\}over thesemmarms:

𝔼⁡\[max⁡\(0,Z1,…,Zm\)\]≤m/\(2​\(m\+1\)\)⋅V,\\mathbb\{E\}\\bigl\[\\max\(0,Z\_\{1\},\\dots,Z\_\{m\}\)\\bigr\]\\;\\leq\\;\\sqrt\{m/\(2\(m\+1\)\)\}\\cdot\\sqrt\{V\},sharp, attained exactly by the cascade law in which alternativekktakes valuek/mk/mwith probability1/\(k\+1\)1/\(k\+1\)and value−1/m\-1/motherwise \(Appendix[C](https://arxiv.org/html/2610.31948#A3)\)\.

###### Theorem 3\(independent noise; main result\)\.

For independent mean\-zeroZ1,…,ZMZ\_\{1\},\\dots,Z\_\{M\}:

sup𝔼⁡\[maxi⁡Zi\]/V=\(M−1\)/\(2​M\),\\sup\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]/\\sqrt\{V\}\\;=\\;\\sqrt\{\(M\-1\)/\(2M\)\},and the supremum is attained exactly by the\(M−1\)\(M\-1\)\-arm cascade of Theorem 2 together with one deterministic arm\. The optimal role of one alternative is to be a deterministic floor; atM=2M=2a deterministic arm is necessary for equality \(Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\)\.

*Proof structure*\(Appendix[D](https://arxiv.org/html/2610.31948#A4)\): \(i\) a Dinkelbach\-type conjugation shows the supremum is determined by laws with at most two atoms per arm; the measure\-theoretic step is Corollary 2 of[Bayer and Teichmann \(2006\)](https://arxiv.org/html/2610.31948#bib.bib6), applied to the moment mapμ↦\(∫𝑑μ,∫z​𝑑μ,∫\(g−λ​z2\)​𝑑μ\)\\mu\\mapsto\(\\int d\\mu,\\int z\\,d\\mu,\\int\(g\-\\lambda z^\{2\}\)\\,d\\mu\), followed by a rank\-2 linear program whose optimal vertices have at most two atoms; \(ii\) in two\-point form the objective is a maximum ofMMlinear functionals of the reweighted atomswi=xi​uiw\_\{i\}=x\_\{i\}u\_\{i\}, so the constrained supremum is a maximum ofMMexplicit values; \(iii\) each value is bounded by a recursion whose fixed points areGm=m/\(2​\(m\+1\)\)G\_\{m\}=m/\(2\(m\+1\)\); the one nontrivial branch reduces to the positivity of a factored cubic on an interval, with equality exactly at the attaining configuration\.

Table 1:The graded family of sharp constantssup𝔼⁡\[maxi⁡Zi\]/V\\sup\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}by dependence class\. “Exact” means the supremum is attained at finite parameters\.Table 2:Worst\-case constants against the Gaussian value: the last column is𝔼⁡\[maxi⁡Zi\]/V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}for i\.i\.d\. standard Gaussian noise, the same comparator in every row; the other columns are the sharp constants of Table[1](https://arxiv.org/html/2610.31948#S3.T1)\. Entries are rounded to three decimals, and the percentages quoted in the text are computed from the exact values\.Table[1](https://arxiv.org/html/2610.31948#S3.T1)collects the graded family\. The family is strictly decreasing down the table for everyM≥3M\\geq 3\. Two identities: theCov≥0\\operatorname\{Cov\}\\geq 0constant is the square of the arbitrary one, and the arbitrary\-to\-independent ratio is2\\sqrt\{2\}for everyMM\. TheCov≥0\\operatorname\{Cov\}\\geq 0and independent constants coincide only atM=2M=2; the arbitrary constant coincides with neither\.

Table[2](https://arxiv.org/html/2610.31948#S3.T2)compares the worst case with the Gaussian value of the same ratio\. How far a constant sits above that value depends on which class it belongs to\. The i\.i\.d\. constant exceeds it by 2\.3%, 5\.7%, 10\.2% and 14\.6% atM=2,…,5M=2,\\dots,5, so in small comparisons the extremal i\.i\.d\. law is barely worse than a Gaussian one\. The independent constant, which is the one Theorem[3](https://arxiv.org/html/2610.31948#Thmtheorem3)supplies and which drops the identical\-distribution requirement, sits further above, and not monotonically: 25\.3%, 18\.2%, 19\.0% and 21\.6% at the sameMM, a minimum atM=3M=3and growth after it\.

The comparator is i\.i\.d\. Gaussian noise in every row; the supremum over*independent*Gaussian laws of the same total variance is at least that value, so these percentages bound the independent class’s distance from its own Gaussian worst case from above\. For largeMMthe Gaussian ratio decays like2​log⁡M/M\\sqrt\{2\\log M/M\}while the worst\-case constants approach their limits, so both are conservative by a factor of orderM/log⁡M\\sqrt\{M/\\log M\}; conclusions that depend on the difference between dependence classes at largeMMshould not be drawn from worst\-case constants alone\.

Figure 1:Configuration cells of Sec\.[5](https://arxiv.org/html/2610.31948#S5): one marker per population, pool sizeMM, item budget and design; scores in accuracy points\.\(a\)Measured𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]against the class ceilingc​Vc\\sqrt\{V\}, log–log\. Solid: the ceiling, which no marker exceeds; dotted: half of it\.\(b\)Optimism against total item budgetnnatM=8M=8on MMLU\-Pro, log–log; colour is the design, dashed lines are the matching ceilings\. Per\-candidate items \(n/8n/8each\) lie above shared items throughout\.\(c\)Measured optimism over that of a Gaussian model with matched covariance, against items per candidate \(nnshared,n/Mn/Mper\-candidate; log scale\); below 1, the Gaussian model overstates\. Only cells resolved to three standard errors are shown\.
## 4The Bias of the Cross\-Validation Estimator

###### Corollary 2\.

For theKK\-fold cross\-validation estimator of Sec\.[2](https://arxiv.org/html/2610.31948#S2),

\|Bias\(CV\)\|≤c⋅1K∑k∑iVar⁡a^ik,\|\\operatorname\{Bias\}\(\\mathrm\{CV\}\)\|\\;\\leq\\;c\\cdot\\frac\{1\}\{K\}\\sum\_\{k\}\\sqrt\{\\textstyle\\sum\_\{i\}\\operatorname\{Var\}\\hat\{a\}\_\{i\}^\{k\}\},wherec=\(M−1\)/Mc=\\sqrt\{\(M\-1\)/M\}in general,c=\(M−1\)/Mc=\(M\-1\)/Munder pairwise nonnegative correlation of the fold’s selection scores, andc=\(M−1\)/\(2​M\)c=\\sqrt\{\(M\-1\)/\(2M\)\}under independence; each constant is sharp within its class as the supremum of𝔼⁡\[maxi⁡Zi\]/V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}; in theBias⁡\(CV\)\\operatorname\{Bias\}\(\\mathrm\{CV\}\)form it is approached along the limiting configurations of Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)rather than attained\. The same three constants boundBias⁡\(ME\)\\operatorname\{Bias\}\(\\mathrm\{ME\}\)fold\-wise, Lemma 1 covering the cross\-validation side andμI≤μ∗\\mu\_\{I\}\\leq\\mu^\{\*\}the other\.

The general case follows from Lemma 1 and Corollary 1a applied fold\-wise\. Since\(M−1\)/M<1\\sqrt\{\(M\-1\)/M\}<1, this settles Conjecture 1 of[van Hasselt \(2013\)](https://arxiv.org/html/2610.31948#bib.bib34), which asserts the bound withc=1c=1; Corollary 1a is Aven’s bound, which appears there as equation \(7\)\. The strict form of the inequality fails only when every fold variance vanishes, and there both sides are zero\.

TheM=2M=2case proved in that paper substitutesVar⁡a^1\+Var⁡a^2\\operatorname\{Var\}\\hat\{a\}\_\{1\}\+\\operatorname\{Var\}\\hat\{a\}\_\{2\}forVar⁡\(a^2−a^1\)\\operatorname\{Var\}\(\\hat\{a\}\_\{2\}\-\\hat\{a\}\_\{1\}\)inside a Cantelli bound\. That substitution is valid underCov≥0\\operatorname\{Cov\}\\geq 0, so the constant1/21/2obtained there is theCov≥0\\operatorname\{Cov\}\\geq 0value atM=2M=2, where the two classes coincide\. They separate for everyM≥3M\\geq 3, which is where the graded constants of Table[1](https://arxiv.org/html/2610.31948#S3.T1)matter\.

Which of the three constants applies is decided by the fold, and for standardKK\-fold cross\-validation it is usually not the independent one: within a fold every candidate is scored on the same held\-out block, so the selection scores are dependent and typically positively correlated, which puts the fold in theCov≥0\\operatorname\{Cov\}\\geq 0class withc=\(M−1\)/Mc=\(M\-1\)/M\. The independent constant governs the case where each candidate gets its own evaluation data, which is the per\-candidate design of Sec\.[5](https://arxiv.org/html/2610.31948#S5)\.

A remark in the same paper suggests that i\.i\.d\. noise is the worst case within the independent class\. Table[1](https://arxiv.org/html/2610.31948#S3.T1)shows otherwise: the i\.i\.d\. constant lies strictly below the independent one for everyM≥2M\\geq 2, so the i\.i\.d\. configuration does not govern the independent class\.

## 5Numerical Study: Selection Pipelines

Table 3:Optimism and regret of best\-of\-MMselection atM=8M=8with a fixed budget of 64 items, under both evaluation designs: shared items \(Cov≥0\\operatorname\{Cov\}\\geq 0class, 64 items per candidate\) and per\-candidate items \(independent class, 8 items each; “per\-cand\.” in the table\)\. Scores are percentage points of accuracy; 20,000 replications per cell\. Optimism is𝔼⁡\[a^I\]−μ∗\\mathbb\{E\}\[\\hat\{a\}\_\{I\}\]\-\\mu^\{\*\}, regret isμ∗−𝔼⁡\[μI\]\\mu^\{\*\}\-\\mathbb\{E\}\[\\mu\_\{I\}\], the ceiling isc​Vc\\sqrt\{V\}for the design’s class,ρ\\rhois the fraction of that ceiling realized by the measured𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\], and the last column is the optimism a Gaussian model with the matched covariance predicts\.#### Data and Pipelines\.

Two families of selection problems\. The first is language\-model configuration selection: one instruction\-tuned 7B model \(Qwen2\.5\-7B\-Instruct;[Yang et al\., 2024](https://arxiv.org/html/2610.31948#bib.bib38)\) crossed with decoding temperature00and0\.70\.7, zero\-shot and five\-shot prompting, and chain\-of\-thought on and off, givingM=8M=8candidates evaluated item by item on four benchmarks — MMLU\-Pro\([Wang et al\., 2024](https://arxiv.org/html/2610.31948#bib.bib36), a 4000\-item uniform subsample of 12032;\), GSM8K\([Cobbe et al\., 2021](https://arxiv.org/html/2610.31948#bib.bib12), 1319 items;\), ARC\-Challenge\([Clark et al\., 2018](https://arxiv.org/html/2610.31948#bib.bib11), 1172 items;\)and MATH\-500\([Hendrycks et al\., 2021](https://arxiv.org/html/2610.31948#bib.bib20);[Lightman et al\., 2024](https://arxiv.org/html/2610.31948#bib.bib23), 500 items;\)\. An answer\-extraction grader marks each generation right or wrong, so an item score is in\{0,1\}\\\{0,1\\\}for the greedy candidates and in\{0,12,1\}\\\{0,\\tfrac\{1\}\{2\},1\\\}for the temperature\-0\.7 candidates, which are drawn twice per item and averaged\. The averaging halves those candidates’ per\-item variance and is part of the variance heterogeneity measured below\.

The second is classifier selection: four model families \(regularized logistic regression,kk\-nearest neighbours, decision trees, small multilayer perceptrons\) at four capacities each, givingM=16M=16candidates on handwritten digits\([Alpaydin and Kaynak, 1998](https://arxiv.org/html/2610.31948#bib.bib2)\)at two difficulty levels, breast cancer\([Wolberg et al\., 1993](https://arxiv.org/html/2610.31948#bib.bib37)\)and wine\([Aeberhard and Forina, 1992](https://arxiv.org/html/2610.31948#bib.bib1)\), plus a pool of 16 seeds of one fixed configuration\. All three datasets are the copies shipped with scikit\-learn\([Pedregosa et al\., 2011](https://arxiv.org/html/2610.31948#bib.bib27)\)\.

#### Designs and Definitions\.

Each candidate is scored once on every item of its population, so the item mean of rowiiis that candidate’s population scoreμi\\mu\_\{i\}and no candidate is ever retrained\. Evaluation designs are then realized by resampling items: the*shared*design scores every candidate on the samennitems, the*per\-candidate*design draws an independent set ofn/Mn/Mitems for each candidate\. Both draw i\.i\.d\. with replacement from the population, so the scoring noise has exactly zero mean; the per\-candidate sets are drawn independently of one another rather than partitioned, so they may overlap in content, and it is the independence of the draws, not disjointness, that makes the per\-candidate noise exactly independent across candidates\.

We report the*optimism*of the reported best,𝔼⁡\[a^I\]−μ∗\\mathbb\{E\}\[\\hat\{a\}\_\{I\}\]\-\\mu^\{\*\}, which isBias⁡\(ME\)\\operatorname\{Bias\}\(\\mathrm\{ME\}\)of Sec\.[2](https://arxiv.org/html/2610.31948#S2)on the accuracy scale, and its*regret*μ∗−𝔼⁡\[μI\]\\mu^\{\*\}\-\\mathbb\{E\}\[\\mu\_\{I\}\]\. The*ceiling*of a configuration isc​Vc\\sqrt\{V\}for the constantccof its class, and which class that is follows from the design: the per\-candidate design is in the independent class by construction, whatever the population’s covariances, so theCov≥0\\operatorname\{Cov\}\\geq 0test below is applied to the shared design alone\.

#### Grid\.

One*cell*is one population, pool size, budget and design\. A pool of sizeMMis the firstMMcandidates of its population, so the pools are nested inMM\. Candidates are ordered by the sweep that generates them, so the small pools vary only the fastest axis and are correspondingly homogeneous: atM=2M=2a language\-model pool is one prompting scheme at two temperatures and a classifier pool is two capacities of one model family\. Results atM=2M=2and44should be read with that in mind\.

The language\-model populations have eight candidates and the classifier populations sixteen, so pool sizes run overM∈\{2,4,8\}M\\in\\\{2,4,8\\\}andM∈\{2,4,8,16\}M\\in\\\{2,4,8,16\\\}respectively\. Budgets double,n∈\{16,32,…,1024\}n\\in\\\{16,32,\\dots,1024\\\}, and each cell is replicated 20,000 times, giving\(4⋅3\+5⋅4\)⋅7⋅2=448\(4\\cdot 3\+5\\cdot 4\)\\cdot 7\\cdot 2=448cells\. Scores below are percentage points\.

#### Validity of the Ceiling\.

In every cell the measured𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]lies on or below the ceiling of its class \(Figure[1](https://arxiv.org/html/2610.31948#S3.F1)\(a\)\)\. Since each design’s class is fixed by construction, a violation would mean a fault in the measurement rather than a counterexample, and we report the check in that spirit\. It does exercise the extremes: cells in which the per\-candidate design leaves one item per candidate, and the per\-candidate cells of the pool that fails the covariance test, which are held to the independent constant rather than to the looser one its population would suggest\.

#### Realized Fraction\.

The realized fractionρ=𝔼⁡\[maxi⁡Zi\]/\(c​V\)\\rho=\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\(c\\sqrt\{V\}\)separates the two classes: with per\-candidate items \(independent class, Theorem 3\)ρ\\rhohas median 0\.75 and reaches 0\.84, and with shared items it has median 0\.37 and reaches 0\.62, each cell divided by the constant of its own class\. These medians run over all pool sizes and budgets; Table[3](https://arxiv.org/html/2610.31948#S5.T3)is one budget, and its nine per\-candidate rows have a median of 0\.53, becauseρ\\rhorises with the budget\.

The ceiling of Theorem 3 is therefore about a third above the𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]an independent\-evaluation pipeline actually incurs\. The optimism of the reported best is smaller again, so the ceiling exceeds it by more; the reporting recipe below quotes both distances\.

TheCov≥0\\operatorname\{Cov\}\\geq 0ceiling is the looser of the two because positive correlation across candidates cancels in the score differences that decide the selection without cancelling inV\\sqrt\{V\}, so the denominator grows while the numerator does not\.

Where a pool falls inside its class depends on how close its candidates are to the top of the accuracy scale\. AtM=8M=8with eight items per candidate \(Table[3](https://arxiv.org/html/2610.31948#S5.T3)\) the independent\-class fraction is 0\.71 to 0\.76 on the four pools that still contain a candidate below 0\.75 — MMLU\-Pro, GSM8K, MATH\-500 and the hardest classifier pool — and falls as the weakest candidate rises: 0\.53 on ARC\-Challenge \(0\.895 to 0\.917\), 0\.47 on wine \(0\.924 to 0\.966\), and 0\.27 to 0\.36 on the three pools whose candidates all exceed 0\.95\.

Near the top of the scale the per\-item variance, at mostp⁡\(1−p\)p\(1\-p\), collapses, and a mean of eight bounded items is far from the two\-point law that attains the constant\. This ordering is a regularity of nine pools at one budget, not a law; which feature of a pool predictsρ\\rhois open \(Sec\.[7](https://arxiv.org/html/2610.31948#S7)\)\.

#### Verifying the Class Hypothesis\.

All four language\-model populations and four of the five classifier pools have every pairwise covariance of per\-item scores positive, so Corollary 1b applies and the constant is\(M−1\)/M\(M\-1\)/M\. The 16\-candidate wine pool contains a negatively correlated pair \(minimum covariance−0\.031\-0\.031\), which places it in the arbitrary\-dependence class and raises its ceiling from\(M−1\)/M=0\.938\(M\-1\)/M=0\.938to\(M−1\)/M=0\.968\\sqrt\{\(M\-1\)/M\}=0\.968; its eight\-candidate shortlist has all covariances positive\. The graded family is applied by checking the covariances and reading off the constant\.

#### Design Effect at a Fixed Budget\.

Splitting a fixed budget intoMMblocks multiplies each candidate’s variance byMM, so the2\\sqrt\{2\}that independence buys in the constant is a statement per unit of variance rather than design advice\. At equal budget the ceilings predict a ratioM/2​\(M−1\)M/\\sqrt\{2\(M\-1\)\}of per\-candidate to shared optimism, between 1\.41 and 2\.92 over our pool sizes; the measured ratio has median 4\.85 with interquartile range 3\.14 to 8\.63, and the shared design incurs less optimism in every one of the 220 pairs in which both quantities are resolved to three standard errors \(Figure[1](https://arxiv.org/html/2610.31948#S3.F1)\(b\)\)\. The measured effect exceeds the predicted one because the shared design also realizes a smaller fraction of its own ceiling\.

In the MMLU\-Pro cell of Table[3](https://arxiv.org/html/2610.31948#S5.T3)the same 64 items cost 3\.09 points of optimism when shared and 18\.87 points when split into eight blocks of eight, a factor 6\.1\. Shared evaluation dominates at a fixed budget, and by more than the constants alone suggest\.

#### Comparison with a Gaussian Model\.

A Gaussian model with the matched covariance is not a substitute for the ceiling\. Replacing the resampled scores by Gaussian ones changes the optimism by a factor whose median is 0\.89 \(interquartile range 0\.74 to 0\.97 over 444 resolved cells\), and the error is systematic in the budget, the median rising monotonically from 0\.60 atn=16n=16to 0\.96 atn=1024n=1024\.

At small budgets the Gaussian model*overstates*the optimism, by up to sixteenfold, because an average of a few bounded discrete item scores has much lighter tails than its Gaussian counterpart: on the three pools whose eight candidates all exceed 0\.95 — the two digit sweeps and breast cancer — it predicts 7\.6 to 7\.9 points where 2\.1 to 2\.4 are incurred \(Table[3](https://arxiv.org/html/2610.31948#S5.T3)\)\.

The direction reverses in 24 of 444 cells, by up to 1\.5\-fold at the largest budgets and extreme pass rates, where skewness dominates \(Figure[1](https://arxiv.org/html/2610.31948#S3.F1)\(c\)\); a handful of further cells cross the line by a margin of no consequence once the ratio is already near one, as the shared MMLU\-Pro row does at a budget of 64 with 3\.09 against 3\.05\.

#### Variance Heterogeneity\.

The extremal laws that attain Theorem 3 carry variances spanning a factor of orderMMacross arms\. Real pools do not: the ratio of largest to smallest per\-candidate item variance stays between 1\.15 and 1\.81 across our nine populations, and within that bandρ\\rhodoes not track it, the Spearman rank correlation being 0\.25\. The accuracy level does track it, at−0\.95\-0\.95over the same nine populations\. Nine points are few either way, and the contrast is what we report rather than a predictor: one ordering is monotone up to an adjacent swap and spans a threefold range inρ\\rho, the other moves without order inside a narrow band\.

Attainment needs a variance profile no selection pool we measured comes close to, which is why the constants are best read as ceilings computable from data, not as predictions of the optimism\.

#### A Worked Cell\.

Selecting among the eight configurations by MMLU\-Pro accuracy measured on 64 shared items, the accuracy of the reported winner overstates its population accuracy by3\.09±0\.043\.09\\pm 0\.04points against a ceiling of14\.8614\.86points, while the winner’s population accuracy is0\.440\.44points below the best available\. The first number is what a leaderboard reports; the second is what the selection costs\.

The seed pool of Table[3](https://arxiv.org/html/2610.31948#S5.T3)is the closest thing here to a null case: sixteen seeds of one configuration, whose population accuracies still differ, by 2\.4 points over the sixteen and 1\.1 over the eight in the table, so most but not all of the reported gain of the best seed is winner’s bias\. Its measured quantities behave as in the other pools, as the theory implies, since the constants do not depend on the means\.

#### Reporting Recipe\.

The optimism of a leaderboard\-style best\-of\-MMnumber admits a ceiling computable from quantities already in hand: the per\-candidate score variances giveV\\sqrt\{V\}, and the class constant follows from the evaluation design, after checking the pairwise covariances if the design is shared\. No distributional assumption and no additional model runs are required\.

Against𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\], the quantity the theorem bounds, that ceiling is too large by a factor between 1\.3 and 1\.7 over the interquartile range of cells with per\-candidate items, and between 2\.4 and 3\.2 with a shared evaluation set; against the optimism of the reported best, which is smaller again, the same ranges are 1\.5 to 3\.3 and 4\.5 to 11\.7\. A recipe must say which of the two it bounds, since the optimism of the reported best is smaller than𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]whenever the candidates are not tied\.

#### Exclusions\.

A 60\-item competition benchmark \(AIME 2024 and 2025\) was evaluated and excluded: at this model scale four of the eight candidates score exactly zero, so the pool has four identical rows with no variance and selection has nothing to select between\. On MATH\-500 and MMLU\-Pro between 5% and 20% of chain\-of\-thought generations reach the token cap, which lowers the population accuracies of the affected candidates; since the population is defined by the measured scores and the optimism is measured against that same population, this does not affect any statement above, but it does mean the absolute accuracies are not comparable with published leaderboard numbers\.

## 6Related Work

#### Classical Moment Bounds\.

[Aven \(1985\)](https://arxiv.org/html/2610.31948#bib.bib5)proves

𝔼⁡\[maxi⁡Xi\]≤maxi⁡𝔼​Xi\+\(n−1\)/n⋅∑iVar⁡Xi,\\mathbb\{E\}\[\\max\_\{i\}X\_\{i\}\]\\leq\\max\_\{i\}\\mathbb\{E\}X\_\{i\}\+\\sqrt\{\(n\-1\)/n\\cdot\\textstyle\\sum\_\{i\}\\operatorname\{Var\}X\_\{i\}\},in whichnnis the number of variables,MMin our notation, and gives covariance\-aware variants through a fixed reference arm\.[Arnold and Groeneveld \(1979\)](https://arxiv.org/html/2610.31948#bib.bib4)prove tightness in the equal\-moments case with an explicit dependent construction\. These are the arbitrary\-dependence pole of Table[1](https://arxiv.org/html/2610.31948#S3.T1); the i\.i\.d\. pole is[Gumbel \(1954\)](https://arxiv.org/html/2610.31948#bib.bib18)and[Hartley and David \(1954\)](https://arxiv.org/html/2610.31948#bib.bib19)\.

#### Convex\-Optimization Bounds\.

[Bertsimas et al\. \(2006\)](https://arxiv.org/html/2610.31948#bib.bib8)treat the moment problem for order statistics under arbitrary dependence \(“no other assumptions on independence or the type of distribution are made”\) and compute the covariance\-informed tight bound as a semidefinite program; the only independence\-adjacent result they cite is the i\.i\.d\. bound above\.

In the marginal\-moment\-problem line that follows them, expectations of maxima and ranges are bounded by convex optimization under marginal or partial dependence information, and[Natarajan and Teo \(2017\)](https://arxiv.org/html/2610.31948#bib.bib24)reduce the semidefinite programs involved and apply them to the expected range\. Those bounds are optimal values computed per instance, and they require the covariance information that the independent class replaces by a structural assumption\.

#### Bounds for Samples from a Common Distribution\.

The projection method of[Gajek and Rychlik \(1996\)](https://arxiv.org/html/2610.31948#bib.bib16);[Gajek and Rychlik \(1998\)](https://arxiv.org/html/2610.31948#bib.bib17)and the monograph of[Rychlik \(2001\)](https://arxiv.org/html/2610.31948#bib.bib30)derive sharp expectation bounds for order statistics of samples from a common distribution, possibly restricted in shape \(decreasing density, decreasing failure rate, symmetric unimodal\)\. The independent case treated there\([Gajek and Rychlik, 1998](https://arxiv.org/html/2610.31948#bib.bib17)\)concerns independent samples from one such distribution, so the variables are identically distributed and the bounds are in units of the common mean and standard deviation, which is a different problem from ours\.

[Rychlik \(1995\)](https://arxiv.org/html/2610.31948#bib.bib29)bounds order statistics of dependent variables with given non\-identical marginals, and[Kałuszka et al\. \(2005\)](https://arxiv.org/html/2610.31948#bib.bib21)bound L\-statistics from dependent samples of random length\. None of this work treats independent, non\-identically distributed variables under per\-variable variance information, which is the setting of Theorems 2 and 3\.

#### The Open Covariance\-Informed Problem\.

[Papadatos \(2016\)](https://arxiv.org/html/2610.31948#bib.bib26)derives the tight mean\-variance bound for the expected range under arbitrary dependence, proves the tight covariance\-informed bound atM=2M=2\(Corollary 7\.1, crediting[Papadatos, 2001](https://arxiv.org/html/2610.31948#bib.bib25)\), and poses tight covariance\-informed bounds at generalMMas open, listing the bounds of[Aven \(1985\)](https://arxiv.org/html/2610.31948#bib.bib5)and[Papadatos \(2001\)](https://arxiv.org/html/2610.31948#bib.bib25)as non\-tight\. Corollary 1b answers the uncorrelated case of that question in closed form\.

#### Estimating the Maximum of Means\.

[van Hasselt \(2010\)](https://arxiv.org/html/2610.31948#bib.bib33);[van Hasselt \(2013\)](https://arxiv.org/html/2610.31948#bib.bib34)introduced the double estimator and the conjecture resolved in Sec\.[4](https://arxiv.org/html/2610.31948#S4)\.[D’Eramo et al\. \(2016\)](https://arxiv.org/html/2610.31948#bib.bib13)propose a Gaussian approximation estimator for the same quantity\. This line studies estimators; our results bound the worst case of any selection\-based report\.

#### Selection Bias in Model Evaluation\.

The minimum cross\-validated error of a tuned model is optimistic:[Varma and Simon \(2006\)](https://arxiv.org/html/2610.31948#bib.bib35)show the bias on simulated data and remove it by nested cross\-validation,[Cawley and Talbot \(2010\)](https://arxiv.org/html/2610.31948#bib.bib10)find its effect comparable to the differences between learning algorithms, and[Tibshirani and Tibshirani \(2009\)](https://arxiv.org/html/2610.31948#bib.bib32)estimate it from the cross\-validation run itself\. These works measure or estimate the bias in a given problem; the constants here bound it in advance\. Reusing one holdout set or leaderboard for repeated selection raises the same issue, which[Dwork et al\. \(2015\)](https://arxiv.org/html/2610.31948#bib.bib14)and[Blum and Hardt \(2015\)](https://arxiv.org/html/2610.31948#bib.bib9)control algorithmically;[Recht et al\. \(2019\)](https://arxiv.org/html/2610.31948#bib.bib28)find that the accuracy drops on new CIFAR\-10 and ImageNet test sets are not explained by such adaptive overfitting\.

#### Post\-Selection Inference\.

Post\-selection inference corrects selection effects either simultaneously over all possible selections\([Berk et al\., 2013](https://arxiv.org/html/2610.31948#bib.bib7)\)or by conditioning on the selection event\([Lee et al\., 2016](https://arxiv.org/html/2610.31948#bib.bib22);[Fithian et al\., 2014](https://arxiv.org/html/2610.31948#bib.bib15)\), and[Andrews et al\. \(2024\)](https://arxiv.org/html/2610.31948#bib.bib3)build estimators and confidence intervals for the winner among several estimates\. This work is complementary: it requires distributional assumptions and yields valid inference, whereas the constants here are distribution\-free bounds on unconditional bias\.

## 7Limitations

The constants are worst\-case over noise laws within each dependence class; Table[2](https://arxiv.org/html/2610.31948#S3.T2)quantifies the gap to Gaussian noise, which grows withMM\. The attainment analysis leaves one open question: whether every attaining configuration in Theorem 3 must contain a deterministic arm is proved atM=2M=2and conjectured for generalMM\(the conjecture is used nowhere\)\.

The numerical study of Sec\.[5](https://arxiv.org/html/2610.31948#S5)has a narrow scope\. The language\-model pools vary the decoding and prompting configuration of a single 7B model, so pools that mix model scales — the case whose variance profile could come closest to the extremal one — are untested, and the classifier pools are small models on datasets that ship with a standard library\.

All scores are single\-item correctness, and both designs are idealizations: the resampling of Sec\.[5](https://arxiv.org/html/2610.31948#S5)is what makes the scoring noise exactly mean\-zero and the per\-candidate design exactly independent\. It is also the only source of randomness, since each candidate is scored once and its population score is treated as fixed, so the measurements say nothing about noise from retraining, from data splits, or from distribution shift between the evaluation pool and deployment\.

The realized fractions of Sec\.[5](https://arxiv.org/html/2610.31948#S5)describe these pools at these budgets and are not typical\-case guarantees; outside them we make no claim about magnitudes beyond Table[2](https://arxiv.org/html/2610.31948#S3.T2)\. Finally, the gap between the ceilings and the measurements is explained only qualitatively: the variance heterogeneity the extremal laws require is absent from these pools, andρ\\rhotracks the accuracy level instead, but nine populations do not yield a quantitative predictor ofρ\\rho\.

## AI Use Statement

In this work, we used generative AI tools to assist in writing the Lean 4 formalization of our proofs \(Appendix[E](https://arxiv.org/html/2610.31948#A5)\)\. We have not used generative AI tools to develop the theory, formulate the mathematical claims, provide ingredients for or write the proofs of Appendices[A](https://arxiv.org/html/2610.31948#A1)to[D](https://arxiv.org/html/2610.31948#A4), propose hypotheses, design the experiments, implement the methods, generate or clean data, or interpret the results; translation and qualitative or thematic data analysis are not applicable to this work\. Additionally, we used generative AI tools to edit the text for readability, to create or modify figures, and to brainstorm the title\. We have reviewed all AI\-assisted work: the authors checked every statement of the Lean formalization manually against the paper after it was implemented, the formal proofs are checked by Lean’s kernel, and the authors checked all proofs in the paper line by line\. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI\.

## References

- Aeberhard and Forina \(1992\)Aeberhard, S\. and Forina, M\. \(1992\)\. Wine\. UCI Machine Learning Repository, doi:10\.24432/C5PC7J\.
- Alpaydin and Kaynak \(1998\)Alpaydin, E\. and Kaynak, C\. \(1998\)\. Optical recognition of handwritten digits\. UCI Machine Learning Repository, doi:10\.24432/C50P49\.
- Andrews et al\. \(2024\)Andrews, I\., Kitagawa, T\., and McCloskey, A\. \(2024\)\. Inference on winners\.*The Quarterly Journal of Economics*, 139\(1\):305–358\.
- Arnold and Groeneveld \(1979\)Arnold, B\. C\. and Groeneveld, R\. A\. \(1979\)\. Bounds on expectations of linear systematic statistics based on dependent samples\.*The Annals of Statistics*, 7\(1\):220–223\.
- Aven \(1985\)Aven, T\. \(1985\)\. Upper \(lower\) bounds on the mean of the maximum \(minimum\) of a number of random variables\.*Journal of Applied Probability*, 22\(3\):723–728\.
- Bayer and Teichmann \(2006\)Bayer, C\. and Teichmann, J\. \(2006\)\. The proof of Tchakaloff’s theorem\.*Proceedings of the American Mathematical Society*, 134\(10\):3035–3040\.
- Berk et al\. \(2013\)Berk, R\., Brown, L\., Buja, A\., Zhang, K\., and Zhao, L\. \(2013\)\. Valid post\-selection inference\.*The Annals of Statistics*, 41\(2\):802–837\.
- Bertsimas et al\. \(2006\)Bertsimas, D\., Natarajan, K\., and Teo, C\.\-P\. \(2006\)\. Tight bounds on expected order statistics\.*Probability in the Engineering and Informational Sciences*, 20\(4\):667–686\.
- Blum and Hardt \(2015\)Blum, A\. and Hardt, M\. \(2015\)\. The Ladder: A reliable leaderboard for machine learning competitions\. In*Proceedings of the 32nd International Conference on Machine Learning*, PMLR 37:1006–1014\.
- Cawley and Talbot \(2010\)Cawley, G\. C\. and Talbot, N\. L\. C\. \(2010\)\. On over\-fitting in model selection and subsequent selection bias in performance evaluation\.*Journal of Machine Learning Research*, 11\(70\):2079–2107\.
- Clark et al\. \(2018\)Clark, P\., Cowhey, I\., Etzioni, O\., Khot, T\., Sabharwal, A\., Schoenick, C\., and Tafjord, O\. \(2018\)\. Think you have solved question answering? Try ARC, the AI2 reasoning challenge\. arXiv:1803\.05457\.
- Cobbe et al\. \(2021\)Cobbe, K\., Kosaraju, V\., Bavarian, M\., Chen, M\., Jun, H\., Kaiser, L\., Plappert, M\., Tworek, J\., Hilton, J\., Nakano, R\., Hesse, C\., and Schulman, J\. \(2021\)\. Training verifiers to solve math word problems\. arXiv:2110\.14168\.
- D’Eramo et al\. \(2016\)D’Eramo, C\., Restelli, M\., and Nuara, A\. \(2016\)\. Estimating maximum expected value through Gaussian approximation\. In*Proceedings of the 33rd International Conference on Machine Learning*, PMLR 48:1032–1040\.
- Dwork et al\. \(2015\)Dwork, C\., Feldman, V\., Hardt, M\., Pitassi, T\., Reingold, O\., and Roth, A\. \(2015\)\. The reusable holdout: Preserving validity in adaptive data analysis\.*Science*, 349\(6248\):636–638\.
- Fithian et al\. \(2014\)Fithian, W\., Sun, D\., and Taylor, J\. \(2014\)\. Optimal inference after model selection\. arXiv:1410\.2597\.
- Gajek and Rychlik \(1996\)Gajek, L\. and Rychlik, T\. \(1996\)\. Projection method for moment bounds on order statistics from restricted families\. I\. Dependent case\.*Journal of Multivariate Analysis*, 57\(1\):156–174\.
- Gajek and Rychlik \(1998\)Gajek, L\. and Rychlik, T\. \(1998\)\. Projection method for moment bounds on order statistics from restricted families\. II\. Independent case\.*Journal of Multivariate Analysis*, 64\(2\):156–182\.
- Gumbel \(1954\)Gumbel, E\. J\. \(1954\)\. The maxima of the mean largest value and of the range\.*The Annals of Mathematical Statistics*, 25\(1\):76–84\.
- Hartley and David \(1954\)Hartley, H\. O\. and David, H\. A\. \(1954\)\. Universal bounds for mean range and extreme observation\.*The Annals of Mathematical Statistics*, 25\(1\):85–99\.
- Hendrycks et al\. \(2021\)Hendrycks, D\., Burns, C\., Kadavath, S\., Arora, A\., Basart, S\., Tang, E\., Song, D\., and Steinhardt, J\. \(2021\)\. Measuring mathematical problem solving with the MATH dataset\. In*Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks*, volume 1\.
- Kałuszka et al\. \(2005\)Kałuszka, M\., Okolewski, A\., and Szymańska, K\. \(2005\)\. Sharp bounds for L\-statistics from dependent samples of random length\.*Journal of Statistical Planning and Inference*, 127\(1–2\):71–89\.
- Lee et al\. \(2016\)Lee, J\. D\., Sun, D\. L\., Sun, Y\., and Taylor, J\. E\. \(2016\)\. Exact post\-selection inference, with application to the lasso\.*The Annals of Statistics*, 44\(3\):907–927\.
- Lightman et al\. \(2024\)Lightman, H\., Kosaraju, V\., Burda, Y\., Edwards, H\., Baker, B\., Lee, T\., Leike, J\., Schulman, J\., Sutskever, I\., and Cobbe, K\. \(2024\)\. Let’s verify step by step\. In*The Twelfth International Conference on Learning Representations*\.
- Natarajan and Teo \(2017\)Natarajan, K\. and Teo, C\.\-P\. \(2017\)\. On reduced semidefinite programs for second order moment bounds with applications\.*Mathematical Programming*, 161\(1–2\):487–518\.
- Papadatos \(2001\)Papadatos, N\. \(2001\)\. Expectation bounds on linear estimators from dependent samples\.*Journal of Statistical Planning and Inference*, 93\(1–2\):17–27\.
- Papadatos \(2016\)Papadatos, N\. \(2016\)\. Maximizing the expected range from dependent observations under mean\-variance information\.*Statistics*, 50\(3\):596–629\.
- Pedregosa et al\. \(2011\)Pedregosa, F\., Varoquaux, G\., Gramfort, A\., Michel, V\., Thirion, B\., Grisel, O\., Blondel, M\., Prettenhofer, P\., Weiss, R\., Dubourg, V\., Vanderplas, J\., Passos, A\., Cournapeau, D\., Brucher, M\., Perrot, M\., and Duchesnay, É\. \(2011\)\. Scikit\-learn: Machine learning in Python\.*Journal of Machine Learning Research*, 12\(85\):2825–2830\.
- Recht et al\. \(2019\)Recht, B\., Roelofs, R\., Schmidt, L\., and Shankar, V\. \(2019\)\. Do ImageNet classifiers generalize to ImageNet? In*Proceedings of the 36th International Conference on Machine Learning*, PMLR 97:5389–5400\.
- Rychlik \(1995\)Rychlik, T\. \(1995\)\. Bounds for order statistics based on dependent variables with given nonidentical distributions\.*Statistics & Probability Letters*, 23\(4\):351–358\.
- Rychlik \(2001\)Rychlik, T\. \(2001\)\.*Projecting Statistical Functionals*\. Lecture Notes in Statistics 160, Springer, New York\.
- Samuelson \(1968\)Samuelson, P\. A\. \(1968\)\. How deviant can you be?*Journal of the American Statistical Association*, 63\(324\):1522–1525\.
- Tibshirani and Tibshirani \(2009\)Tibshirani, R\. J\. and Tibshirani, R\. \(2009\)\. A bias correction for the minimum error rate in cross\-validation\.*The Annals of Applied Statistics*, 3\(2\):822–829\.
- van Hasselt \(2010\)van Hasselt, H\. \(2010\)\. Double Q\-learning\. In*Advances in Neural Information Processing Systems 23*, pages 2613–2621\.
- van Hasselt \(2013\)van Hasselt, H\. \(2013\)\. Estimating the maximum expected value: an analysis of \(nested\) cross validation and the maximum sample average\. arXiv:1302\.7175\.
- Varma and Simon \(2006\)Varma, S\. and Simon, R\. \(2006\)\. Bias in error estimation when using cross\-validation for model selection\.*BMC Bioinformatics*, 7:91\.
- Wang et al\. \(2024\)Wang, Y\., Ma, X\., Zhang, G\., Ni, Y\., Chandra, A\., Guo, S\., Ren, W\., Arulraj, A\., He, X\., Jiang, Z\., Li, T\., Ku, M\., Wang, K\., Zhuang, A\., Fan, R\., Yue, X\., and Chen, W\. \(2024\)\. MMLU\-Pro: A more robust and challenging multi\-task language understanding benchmark\. In*Advances in Neural Information Processing Systems 37 \(Datasets and Benchmarks Track\)*, pages 95266–95290\.
- Wolberg et al\. \(1993\)Wolberg, W\., Mangasarian, O\., and Street, W\. N\. \(1993\)\. Breast cancer Wisconsin \(diagnostic\)\. UCI Machine Learning Repository, doi:10\.24432/C5DW2B\.
- Yang et al\. \(2024\)Yang, A\., Yang, B\., Zhang, B\., Hui, B\., Zheng, B\., Yu, B\., et al\. \(2024\)\. Qwen2\.5 technical report\. arXiv:2412\.15115\.

Appendix

Numbering matches the main text: Lemma 1 \(transfer\), Theorem 1 with Corollaries 1a/1b, Theorem 2, Theorem 3, and the Attainment Lemma\. Every identity and attainment claim below was additionally verified in exact rational and symbolic arithmetic; the verification script will be released with the code\. All theorems and lemmas below are also formally verified in Lean 4 with Mathlib; the formalization is described in Appendix[E](https://arxiv.org/html/2610.31948#A5)\.

## Appendix ANotation and the Transfer Lemma

### A\.1Setup and Notation

Alternatives \(arms\)i=1,…,Mi=1,\\dots,M, true meansμi\\mu\_\{i\},μ∗=maxi⁡μi\\mu^\{\*\}=\\max\_\{i\}\\mu\_\{i\}, gapsgi=μ∗−μi≥0g\_\{i\}=\\mu^\{\*\}\-\\mu\_\{i\}\\geq 0\. Selection estimatesa^i=μi\+Zi\\hat\{a\}\_\{i\}=\\mu\_\{i\}\+Z\_\{i\}with𝔼⁡\[Zi\]=0\\mathbb\{E\}\[Z\_\{i\}\]=0,Var⁡Zi=vi\\operatorname\{Var\}Z\_\{i\}=v\_\{i\},V=∑iviV=\\sum\_\{i\}v\_\{i\},Z¯=\(1/M\)​∑iZi\\bar\{Z\}=\(1/M\)\\sum\_\{i\}Z\_\{i\}\. The winner isI=arg​maxi⁡a^iI=\\argmax\_\{i\}\\hat\{a\}\_\{i\}\. Two estimators ofμ∗\\mu^\{\*\}:

- •Max\-estimator \(ME\):reporta^I=maxi⁡a^i\\hat\{a\}\_\{I\}=\\max\_\{i\}\\hat\{a\}\_\{i\};Bias⁡\(ME\)=𝔼⁡\[maxi⁡a^i\]−μ∗∈\[0,𝔼⁡\[maxi⁡Zi\]\]\\operatorname\{Bias\}\(\\mathrm\{ME\}\)=\\mathbb\{E\}\[\\max\_\{i\}\\hat\{a\}\_\{i\}\]\-\\mu^\{\*\}\\in\[0,\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]\]\.
- •CV / double estimator:evaluate an independent unbiased estimate atII;Bias⁡\(CV\)=−𝔼⁡\[gI\]∈\[−𝔼⁡\[maxi⁡Zi\],0\]\\operatorname\{Bias\}\(\\mathrm\{CV\}\)=\-\\mathbb\{E\}\[g\_\{I\}\]\\in\[\-\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\],0\]\.

#### Tie Convention\.

Ties inarg​max\\argmaxare broken by uniform choice; none of the extremal laws in this appendix produce ties\. The transfer below also holds under the tie convention of[van Hasselt \(2013\)](https://arxiv.org/html/2610.31948#bib.bib34), which averages the gap over the tied set; no ties occur in the constructions\.

#### Two\-Point Notation

\(used throughout Appendices[C](https://arxiv.org/html/2610.31948#A3)and[D](https://arxiv.org/html/2610.31948#A4)\)\. A two\-point mean\-zero armiitakes the up valueui\>0u\_\{i\}\>0with probabilityxix\_\{i\}and the down valuedi=−xiui/qid\_\{i\}=\-x\_\{i\}u\_\{i\}/q\_\{i\}with probabilityqi=1−xiq\_\{i\}=1\-x\_\{i\}; its variance isvi=xi​ui2/qiv\_\{i\}=x\_\{i\}u\_\{i\}^\{2\}/q\_\{i\}\. With arms sorted so thatu1≥⋯≥umu\_\{1\}\\geq\\dots\\geq u\_\{m\}:

si\\displaystyle s\_\{i\}=∏j<iqj\(head survival;s1=1\),\\displaystyle=\\prod\_\{j<i\}q\_\{j\}\\quad\\text\{\(head survival; $s\_\{1\}=1$\),\}Q\\displaystyle Q=∏jqj\(all\-down probability\),\\displaystyle=\\prod\_\{j\}q\_\{j\}\\quad\\text\{\(all\-down probability\),\}Pk\\displaystyle P\_\{k\}=∏j\>kqj\(tail survival;PM=1\),\\displaystyle=\\prod\_\{j\>k\}q\_\{j\}\\quad\\text\{\(tail survival; $P\_\{M\}=1$\),\}wi\\displaystyle w\_\{i\}=xi​ui,\\displaystyle=x\_\{i\}u\_\{i\},f⁡\(x\)\\displaystyle f\(x\)=fm​\(x\)=∑ixi​qi​si2,\\displaystyle=f\_\{m\}\(x\)=\\sum\_\{i\}x\_\{i\}q\_\{i\}s\_\{i\}^\{2\},Gm\\displaystyle G\_\{m\}=m2​\(m\+1\),G0=0,\\displaystyle=\\frac\{m\}\{2\(m\+1\)\},\\quad G\_\{0\}=0,R⁡\(c\)\\displaystyle R\(c\)=maxx∈\[0,1\]⁡\[x⁡\(1−x\)\+\(1−x\)2​c\]\.\\displaystyle=\\max\_\{x\\in\[0,1\]\}\\bigl\[\\,x\(1\-x\)\+\(1\-x\)^\{2\}c\\,\\bigr\]\.

### A\.2Lemma 1 \(Transfer\)

###### Lemma 1\.

𝔼⁡\[gI\]≤𝔼⁡\[maxj⁡Zj\]\\mathbb\{E\}\[g\_\{I\}\]\\leq\\mathbb\{E\}\[\\max\_\{j\}Z\_\{j\}\]\.

###### Proof\.

SinceI=arg​maxi⁡a^iI=\\argmax\_\{i\}\\hat\{a\}\_\{i\}, for a fixed optimal armi∘i^\{\\circ\}\(one withμi∘=μ∗\\mu\_\{i^\{\\circ\}\}=\\mu^\{\*\}\) we haveμI\+ZI≥μ∗\+Zi∘\\mu\_\{I\}\+Z\_\{I\}\\geq\\mu^\{\*\}\+Z\_\{i^\{\\circ\}\}, i\.e\.gI≤ZI−Zi∘≤maxj⁡Zj−Zi∘g\_\{I\}\\leq Z\_\{I\}\-Z\_\{i^\{\\circ\}\}\\leq\\max\_\{j\}Z\_\{j\}\-Z\_\{i^\{\\circ\}\}\. Take expectations and use𝔼⁡\[Zi∘\]=0\\mathbb\{E\}\[Z\_\{i^\{\\circ\}\}\]=0\. ∎

Consequently every upper bound on𝔼⁡\[maxi⁡Zi\]/V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}in this appendix bounds both\|Bias⁡\(CV\)\|\|\\operatorname\{Bias\}\(\\mathrm\{CV\}\)\|andBias⁡\(ME\)\\operatorname\{Bias\}\(\\mathrm\{ME\}\), and all three extremal constructions approach their constants in the𝔼⁡\[gI\]\\mathbb\{E\}\[g\_\{I\}\]form as well, along the limiting configurations of Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5): each gap rises to\(1−ε\)\(1\-\\varepsilon\)times the largest lead its arm’s noise can take over the optimal arm,ε→0\+\\varepsilon\\to 0^\{\+\}\. That lead is the up\-value of the arm for the cascade, whose best arm is deterministic, butM​dMd, not the up\-value\(M−1\)​d\(M\-1\)d, for the one\-up laws of Corollaries 1a and 1b\.

## Appendix BTheorem 1 and Corollaries 1a/1b

### B\.1Theorem 1 \(Master Bound\)

###### Theorem 1\.

For any mean\-zeroZZ\(no independence assumed\),

𝔼⁡\[maxi⁡Zi\]≤\(M−1\)/M⋅V−M​𝔼​\[Z¯2\]\.\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]\\;\\leq\\;\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\}\.

###### Proof\.

Samuelson’s inequality\([Samuelson, 1968](https://arxiv.org/html/2610.31948#bib.bib31)\), applied pointwise: for any realsa1,…,aMa\_\{1\},\\dots,a\_\{M\}with meana¯\\bar\{a\},

maxi⁡\(ai−a¯\)≤M−1M⋅∑j\(aj−a¯\)2\.\\max\_\{i\}\(a\_\{i\}\-\\bar\{a\}\)\\;\\leq\\;\\sqrt\{\\frac\{M\-1\}\{M\}\\cdot\\sum\_\{j\}\(a\_\{j\}\-\\bar\{a\}\)^\{2\}\}\.Apply ata=Za=Z, so thatmaxi⁡Zi=maxi⁡\(Zi−Z¯\)\+Z¯\\max\_\{i\}Z\_\{i\}=\\max\_\{i\}\(Z\_\{i\}\-\\bar\{Z\}\)\+\\bar\{Z\}\. Take expectations, use𝔼⁡\[Z¯\]=0\\mathbb\{E\}\[\\bar\{Z\}\]=0, and apply Cauchy–Schwarz to𝔼​∑j\(Zj−Z¯\)2\\mathbb\{E\}\\sqrt\{\\sum\_\{j\}\(Z\_\{j\}\-\\bar\{Z\}\)^\{2\}\}:

𝔼⁡\[maxi⁡Zi\]\\displaystyle\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]=𝔼⁡\[maxi⁡\(Zi−Z¯\)\]\+𝔼⁡\[Z¯\]\\displaystyle=\\mathbb\{E\}\\bigl\[\\max\_\{i\}\(Z\_\{i\}\-\\bar\{Z\}\)\\bigr\]\+\\mathbb\{E\}\[\\bar\{Z\}\]≤\(M−1\)/M⋅𝔼​∑j\(Zj−Z¯\)2\\displaystyle\\leq\\sqrt\{\(M\-1\)/M\}\\cdot\\mathbb\{E\}\\sqrt\{\\textstyle\\sum\_\{j\}\(Z\_\{j\}\-\\bar\{Z\}\)^\{2\}\}≤\(M−1\)/M⋅𝔼​∑j\(Zj−Z¯\)2,\\displaystyle\\leq\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{\\mathbb\{E\}\\textstyle\\sum\_\{j\}\(Z\_\{j\}\-\\bar\{Z\}\)^\{2\}\},and the variance identity

𝔼​∑j\(Zj−Z¯\)2=V−M​𝔼​\[Z¯2\]\\mathbb\{E\}\\sum\_\{j\}\(Z\_\{j\}\-\\bar\{Z\}\)^\{2\}=V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]completes the proof\. ∎

#### Difference Form\.

Via the identity

∑i<j𝔼​\(Zi−Zj\)2=M⋅\(V−M​𝔼​\[Z¯2\]\),\\sum\_\{i<j\}\\mathbb\{E\}\(Z\_\{i\}\-Z\_\{j\}\)^\{2\}=M\\cdot\(V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\),Theorem 1 is equivalent to a bound in the variances of pairwise differences\.

#### Provenance\.

Theorem 1 is Aven’s \(1985\)u20u\_\{20\}bound applied to the deviationsYi=Zi−Z¯Y\_\{i\}=Z\_\{i\}\-\\bar\{Z\}:𝔼​max⁡Z=𝔼​max⁡Y\+𝔼​Z¯=𝔼​max⁡Y\\mathbb\{E\}\\max Z=\\mathbb\{E\}\\max Y\+\\mathbb\{E\}\\bar\{Z\}=\\mathbb\{E\}\\max Y,𝔼⁡\[Yi\]=0\\mathbb\{E\}\[Y\_\{i\}\]=0, and∑iVar⁡Yi=𝔼​∑i\(Zi−Z¯\)2=V−M​𝔼​\[Z¯2\]\\sum\_\{i\}\\operatorname\{Var\}Y\_\{i\}=\\mathbb\{E\}\\sum\_\{i\}\(Z\_\{i\}\-\\bar\{Z\}\)^\{2\}=V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\], sou20​\(Y\)u\_\{20\}\(Y\)is exactly the master bound\. We therefore claim no novelty for Theorem 1 itself; the Samuelson proof above is kept as self\-contained exposition\. AtM=2M=2the bound is published with tightness:[Papadatos \(2016, Cor\. 7\.1\)](https://arxiv.org/html/2610.31948#bib.bib26), crediting[Papadatos \(2001\)](https://arxiv.org/html/2610.31948#bib.bib25)\.

###### Lemma\(gap to Aven’s fixed\-arm family\)\.

Aven’s covariance\-aware bounds are \(centered\)u2​j=\(M−1\)/M⋅Sju\_\{2j\}=\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{S\_\{j\}\}withSj=∑i𝔼​\(Zi−Zj\)2S\_\{j\}=\\sum\_\{i\}\\mathbb\{E\}\(Z\_\{i\}\-Z\_\{j\}\)^\{2\}, for each fixed reference armjj\. WithD=V−M​𝔼​\[Z¯2\]D=V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]:

1. 1\.D≤SjD\\leq S\_\{j\}for everyjj, with exact slackSj−D=M​𝔼​\[\(Z¯−Zj\)2\]S\_\{j\}\-D=M\\,\\mathbb\{E\}\[\(\\bar\{Z\}\-Z\_\{j\}\)^\{2\}\];
2. 2\.∑j=1MSj=2​M⋅D\\sum\_\{j=1\}^\{M\}S\_\{j\}=2M\\cdot D, henceminj⁡Sj≤2​D\\min\_\{j\}S\_\{j\}\\leq 2D;
3. 3\.somin1≤j≤M⁡u2​j/master=min1≤j≤M⁡Sj/D∈\[1,2\]\\min\_\{1\\leq j\\leq M\}u\_\{2j\}/\\mathrm\{master\}=\\sqrt\{\\min\_\{1\\leq j\\leq M\}S\_\{j\}/D\}\\in\[1,\\sqrt\{2\}\]\(assumingD\>0D\>0\); over this reference\-arm subfamily the ratio equals11iff someZj=Z¯Z\_\{j\}=\\bar\{Z\}a\.s\. \(by the slack in 1; a deterministic arm is neither necessary nor sufficient\), and2\\sqrt\{2\}is attained, for any non\-degenerate exchangeable law \(𝔼​\(Zi−Zj\)2≡e\>0\\mathbb\{E\}\(Z\_\{i\}\-Z\_\{j\}\)^\{2\}\\equiv e\>0, e\.g\. i\.i\.d\.\), where everySj=\(M−1\)​e=2​DS\_\{j\}=\(M\-1\)e=2D\. Aven’sj=0j=0memberu20=\(M−1\)/M⋅Vu\_\{20\}=\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\}is excluded from this min; including it keeps the ratio in\[1,2\]\[1,\\sqrt\{2\}\]\(sinceD≤VD\\leq V\) but changes the equality case to “Z¯≡0\\bar\{Z\}\\equiv 0a\.s\. or someZj=Z¯Z\_\{j\}=\\bar\{Z\}a\.s\.”: e\.g\. theM=2M=2anti\-correlated pair of Corollary 1a hasu20=masteru\_\{20\}=\\mathrm\{master\}with noZj=Z¯Z\_\{j\}=\\bar\{Z\}\.

###### Proof\.

\(1\) Fixjj, setai=Zi−Zja\_\{i\}=Z\_\{i\}\-Z\_\{j\}; thena¯=Z¯−Zj\\bar\{a\}=\\bar\{Z\}\-Z\_\{j\},Zi−Z¯=ai−a¯Z\_\{i\}\-\\bar\{Z\}=a\_\{i\}\-\\bar\{a\}, and pointwise∑i\(ai−a¯\)2=∑iai2−M​a¯2\\sum\_\{i\}\(a\_\{i\}\-\\bar\{a\}\)^\{2\}=\\sum\_\{i\}a\_\{i\}^\{2\}\-M\\bar\{a\}^\{2\}; take expectations\. \(2\) Expand∑i,j\(zi−zj\)2=2​M​∑izi2−2​\(∑izi\)2\\sum\_\{i,j\}\(z\_\{i\}\-z\_\{j\}\)^\{2\}=2M\\sum\_\{i\}z\_\{i\}^\{2\}\-2\(\\sum\_\{i\}z\_\{i\}\)^\{2\}and take expectations\. \(3\) Immediate from \(1\)–\(2\)\. ∎

### B\.2Corollary 1a \(Arbitrary Dependence\)

###### Corollary 1a\.

𝔼⁡\[Z¯2\]≥0\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\\geq 0in Theorem 1 gives

𝔼⁡\[maxi⁡Zi\]≤\(M−1\)/M⋅V\.\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]\\;\\leq\\;\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\}\.This is Aven’su20u\_\{20\}bound \(displayed as bound \(3\) in Bertsimas–Natarajan–Teo’s restatement\), cited by van Hasselt as his equation \(7\)\. It is sharp\.

#### Equality Characterization\.

Equality in the chain of the proof of Theorem 1 requires all three of:

1. 1\.Z¯≡0\\bar\{Z\}\\equiv 0a\.s\. \(to drop theM​𝔼​\[Z¯2\]M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]term\),
2. 2\.the Samuelson equality pattern pointwise \(one value up, the remainingM−1M\-1values equal\), and
3. 3\.∑j\(Zj−Z¯\)2\\sum\_\{j\}\(Z\_\{j\}\-\\bar\{Z\}\)^\{2\}a\.s\. constant \(the Jensen/Cauchy–Schwarz condition\)\.

#### Attainment\.

AtM=2M=2: the anti\-correlated pairZ1=−Z2=±s/2Z\_\{1\}=\-Z\_\{2\}=\\pm s/2\(each sign with probability1/21/2\) hasZ¯≡0\\bar\{Z\}\\equiv 0and satisfies the Samuelson equality pattern, attaining1/2\\sqrt\{1/2\}\. The anti\-correlated pair attains the constant atM=2M=2only; at generalMMthe attaining law is theuniform\-index one\-up law\(Arnold–Groeneveld’s dependent construction; tightness in the equal\-moments case is theirs, as restated by Bertsimas–Natarajan–Teo\): letJJbe uniform on\{1,…,M\}\\\{1,\\dots,M\\\}and

Yi=\(M−1\)⋅d​if​i=J,Yi=−d​otherwise\(d\>0\)\.\\begin\{gathered\}Y\_\{i\}=\(M\-1\)\\cdot d\\ \\text\{ if \}i=J,\\\\ Y\_\{i\}=\-d\\ \\text\{ otherwise\}\\qquad\(d\>0\)\.\\end\{gathered\}Then𝔼⁡\[Yi\]=0\\mathbb\{E\}\[Y\_\{i\}\]=0,Z¯≡0\\bar\{Z\}\\equiv 0pointwise, each realization has one value up and the rest equal,Var⁡Yi=\(M−1\)​d2\\operatorname\{Var\}Y\_\{i\}=\(M\-1\)d^\{2\},V=M⁡\(M−1\)​d2V=M\(M\-1\)d^\{2\}, andmaxi⁡Yi=\(M−1\)​d\\max\_\{i\}Y\_\{i\}=\(M\-1\)da\.s\., so

𝔼⁡\[maxi⁡Yi\]/V=\(M−1\)​dM⁡\(M−1\)​d=\(M−1\)/M,\\mathbb\{E\}\\bigl\[\\max\_\{i\}Y\_\{i\}\\bigr\]/\\sqrt\{V\}=\\frac\{\(M\-1\)d\}\{\\sqrt\{M\(M\-1\)\}\\,d\}=\\sqrt\{\(M\-1\)/M\},exactly, at finite parameters\.

### B\.3Corollary 1b \(Pairwise Nonnegative Correlation; Sharp\)

###### Corollary 1b\.

IfCov⁡\(Zi,Zj\)≥0\\operatorname\{Cov\}\(Z\_\{i\},Z\_\{j\}\)\\geq 0for alli≠ji\\neq j, then

𝔼⁡\[maxi⁡Zi\]≤M−1M⋅V,\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]\\;\\leq\\;\\frac\{M\-1\}\{M\}\\cdot\\sqrt\{V\},and this is sharp already in the uncorrelated subclass \(Cov=0\\operatorname\{Cov\}=0\), attained exactly at finite parameters\.

###### Proof of the bound\.

𝔼⁡\[Z¯2\]=\(1/M2\)⋅\(V\+∑i≠jCov⁡\(Zi,Zj\)\)\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]=\(1/M^\{2\}\)\\cdot\\bigl\(V\+\\sum\_\{i\\neq j\}\\operatorname\{Cov\}\(Z\_\{i\},Z\_\{j\}\)\\bigr\)\. Under pairwiseCov≥0\\operatorname\{Cov\}\\geq 0this gives𝔼⁡\[Z¯2\]≥V/M2\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\\geq V/M^\{2\}\(with equality iff all pairwise covariances vanish\)\. Then Theorem 1 gives

𝔼⁡\[maxi⁡Zi\]\\displaystyle\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]≤M−1M​V−VM\\displaystyle\\leq\\sqrt\{\\tfrac\{M\-1\}\{M\}\}\\sqrt\{V\-\\tfrac\{V\}\{M\}\}=M−1M​V⋅M−1M=M−1M​V\.∎\\displaystyle=\\sqrt\{\\tfrac\{M\-1\}\{M\}\}\\sqrt\{V\\cdot\\tfrac\{M\-1\}\{M\}\}=\\tfrac\{M\-1\}\{M\}\\sqrt\{V\}\.\\qed

#### Attainment: The One\-Up\-plus\-Common\-Shock Law \(Exact at Finite Parameters, Not Asymptotic\)\.

Fixd\>0d\>0\. LetJJbe uniform on\{1,…,M\}\\\{1,\\dots,M\\\}, letYYbe the one\-up law of Corollary 1a \(YJ=\(M−1\)​dY\_\{J\}=\(M\-1\)dup,Yi=−dY\_\{i\}=\-ddown fori≠Ji\\neq J\), and letWWbe an independent mean\-zero common shock with variance exactlyd2d^\{2\}\. Set

Then:

- •Mean zero:𝔼⁡\[Zi\]=0\\mathbb\{E\}\[Z\_\{i\}\]=0\.
- •Covariances:fori≠ji\\neq j,Cov⁡\(Yi,Yj\)=𝔼⁡\[Yi​Yj\]=\(2/M\)⋅\(\(M−1\)​d\)​\(−d\)\+\(\(M−2\)/M\)⋅d2=−d2\\operatorname\{Cov\}\(Y\_\{i\},Y\_\{j\}\)=\\mathbb\{E\}\[Y\_\{i\}Y\_\{j\}\]=\(2/M\)\\cdot\(\(M\-1\)d\)\(\-d\)\+\(\(M\-2\)/M\)\\cdot d^\{2\}=\-d^\{2\}, soCov⁡\(Zi,Zj\)=Cov⁡\(Yi,Yj\)\+Var⁡W=−d2\+d2=0\\operatorname\{Cov\}\(Z\_\{i\},Z\_\{j\}\)=\\operatorname\{Cov\}\(Y\_\{i\},Y\_\{j\}\)\+\\operatorname\{Var\}W=\-d^\{2\}\+d^\{2\}=0and the arms are pairwise uncorrelated, which fixes the shock variance atd2d^\{2\}\.
- •Variance and maximum:Var⁡Zi=\(M−1\)​d2\+d2=M​d2\\operatorname\{Var\}Z\_\{i\}=\(M\-1\)d^\{2\}\+d^\{2\}=Md^\{2\}, soV=M2​d2V=M^\{2\}d^\{2\}; andmaxi⁡Zi=\(M−1\)​d\+W\\max\_\{i\}Z\_\{i\}=\(M\-1\)d\+W, so𝔼⁡\[maxi⁡Zi\]=\(M−1\)​d\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]=\(M\-1\)d\. The shock addsM​d2Md^\{2\}to the denominator and nothing to the numerator: 𝔼⁡\[maxi⁡Zi\]/V=\(M−1\)​dM​d=M−1M,\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]/\\sqrt\{V\}=\\frac\{\(M\-1\)d\}\{Md\}=\\frac\{M\-1\}\{M\},exactly, at every finitedd\. Equality also holds term\-by\-term in the master bound:Z¯=W\\bar\{Z\}=W,𝔼⁡\[Z¯2\]=d2=V/M2\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]=d^\{2\}=V/M^\{2\}, and\(M−1\)/M⋅V−M​𝔼​\[Z¯2\]=\(M−1\)/M⋅M⁡\(M−1\)⋅d=\(M−1\)​d\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\-M\\,\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\}=\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{M\(M\-1\)\}\\cdot d=\(M\-1\)d\.

#### TheCov≥0\\operatorname\{Cov\}\\geq 0Extension\.

Since𝔼⁡\[Z¯2\]≥V/M2\\mathbb\{E\}\[\\bar\{Z\}^\{2\}\]\\geq V/M^\{2\}holds under pairwiseCov≥0\\operatorname\{Cov\}\\geq 0\(not only underCov=0\\operatorname\{Cov\}=0\), Corollary 1b extends verbatim to the pairwise nonnegatively\-correlated class, and is sharp on its boundary \(the uncorrelated subclass\)\. This wider class is also the realistic one: shared evaluation data induces positive correlation\. It is likewise the class in which van Hasselt’sM=2M=2appendix proof lives: Cantelli’s right\-hand side is increasing in the variance, so his substitution ofVar⁡a^1\+Var⁡a^2\\operatorname\{Var\}\\hat\{a\}\_\{1\}\+\\operatorname\{Var\}\\hat\{a\}\_\{2\}forVar⁡\(a^2−a^1\)\\operatorname\{Var\}\(\\hat\{a\}\_\{2\}\-\\hat\{a\}\_\{1\}\)is valid iffCov≥0\\operatorname\{Cov\}\\geq 0, and his provedM=2M=2constant1/21/2is\(M−1\)/M\(M\-1\)/MatM=2M=2\.

## Appendix CTheorem 2 \(Independent Noise, Deterministic Best Arm\)

###### Theorem 2\.

For independent mean\-zeroZ1,…,ZmZ\_\{1\},\\dots,Z\_\{m\}:

𝔼⁡\[max⁡\(0,Z1,…,Zm\)\]≤m/\(2​\(m\+1\)\)⋅V,sharp\.\\mathbb\{E\}\\bigl\[\\max\(0,Z\_\{1\},\\dots,Z\_\{m\}\)\\bigr\]\\leq\\sqrt\{m/\(2\(m\+1\)\)\}\\cdot\\sqrt\{V\},\\quad\\text\{sharp\.\}Equivalently: in the CV problem withM=m\+1M=m\+1arms whose best arm has deterministic selection estimate, the sharp constant is\(M−1\)/\(2​M\)\\sqrt\{\(M\-1\)/\(2M\)\}\.

*Proof, in five steps\.*WriteT=max⁡\(0,Z1,…,Zm\)T=\\max\(0,Z\_\{1\},\\dots,Z\_\{m\}\)\.

### C\.1Step 1: Two\-Point Reduction per Arm

By Dinkelbach conjugation, maximize𝔼⁡\[T\]−λ​V\\mathbb\{E\}\[T\]\-\\lambda Vat the criticalλ\\lambda\. For fixed other arms, both𝔼⁡\[T\]\\mathbb\{E\}\[T\]andVVare linear in armii’s law, so the per\-arm problem maximizes a linear functional over the constraint set\{mass​1,mean​0\}\\\{\\text\{mass \}1,\\ \\text\{mean \}0\\\}, whose extreme points have at most 2 atoms\. An arm whose up\-atom is non\-positive is \(by the mean\-zero constraint\) the point massδ0\\delta\_\{0\}; it contributes nothing toT≥0T\\geq 0and is dropped, reducingmm; sincem/\(2​\(m\+1\)\)m/\(2\(m\+1\)\)is increasing inmm, the bound for the reduced problem implies the stated one\. So without loss of generality armiitakesui\>0u\_\{i\}\>0with probabilityxix\_\{i\}anddi=−xiui/qid\_\{i\}=\-x\_\{i\}u\_\{i\}/q\_\{i\}with probabilityqi=1−xiq\_\{i\}=1\-x\_\{i\}, withvi=xi​ui2/qiv\_\{i\}=x\_\{i\}u\_\{i\}^\{2\}/q\_\{i\}\.

\(The fully careful statement of this reduction, covering finiteness of the sup, integrability of the per\-arm integrand, the Bayer–Teichmann representation theorem, and the one\-sweep exact\-replacement argument, is written out in Appendix[D\.1](https://arxiv.org/html/2610.31948#A4.SS1)for Theorem 3; it is the same Dinkelbach argument, with the deterministic floor entering only through the other\-arms maximumZ−imaxZ^\{\\max\}\_\{\-i\}\.\)

### C\.2Step 2: The Exact Formula

Sort the arms so thatu1≥⋯≥umu\_\{1\}\\geq\\dots\\geq u\_\{m\}\. Partition by the first up arm:T=uiT=u\_\{i\}iff armiiis up and all armsj<ij<iare down \(armsj\>ij\>icannot change the max then, sinceuj≤uiu\_\{j\}\\leq u\_\{i\}and their down values are negative\); if all arms are down,T=0T=0\. Hence

𝔼⁡\[T\]=∑ixi​ui​si,si=∏j<iqj\.\\mathbb\{E\}\[T\]=\\sum\_\{i\}x\_\{i\}u\_\{i\}s\_\{i\},\\qquad s\_\{i\}=\\prod\_\{j<i\}q\_\{j\}\.

### C\.3Step 3: The Cauchy–Schwarz Split

Factor each term and apply Cauchy–Schwarz:

𝔼⁡\[T\]\\displaystyle\\mathbb\{E\}\[T\]=∑i\[ui​xi/qi\]⋅\[xi​qi⋅si\]\\displaystyle=\\sum\_\{i\}\\Bigl\[u\_\{i\}\\sqrt\{x\_\{i\}/q\_\{i\}\}\\Bigr\]\\cdot\\Bigl\[\\sqrt\{x\_\{i\}q\_\{i\}\}\\cdot s\_\{i\}\\Bigr\]≤∑ixi​ui2/qi⋅∑ixi​qi​si2\\displaystyle\\leq\\sqrt\{\\textstyle\\sum\_\{i\}x\_\{i\}u\_\{i\}^\{2\}/q\_\{i\}\}\\cdot\\sqrt\{\\textstyle\\sum\_\{i\}x\_\{i\}q\_\{i\}s\_\{i\}^\{2\}\}=V⋅f⁡\(x\),f⁡\(x\)=∑ixi​qi​si2,\\displaystyle=\\sqrt\{V\}\\cdot\\sqrt\{f\(x\)\},\\qquad f\(x\)=\\sum\_\{i\}x\_\{i\}q\_\{i\}s\_\{i\}^\{2\},with equality atui∝qi​siu\_\{i\}\\propto q\_\{i\}s\_\{i\}\. This choice issort\-consistent: sincesi\+1=si​qis\_\{i\+1\}=s\_\{i\}q\_\{i\},

ui\+1/ui=\(qi\+1​si\+1\)/\(qi​si\)=qi\+1≤1,u\_\{i\+1\}/u\_\{i\}=\(q\_\{i\+1\}s\_\{i\+1\}\)/\(q\_\{i\}s\_\{i\}\)=q\_\{i\+1\}\\leq 1,so the maximizinguurespects the assumed orderu1≥⋯≥umu\_\{1\}\\geq\\dots\\geq u\_\{m\}, and the split loses nothing\.

### C\.4Step 4: The Recursion and Its Exact Solution

Sinces1=1s\_\{1\}=1andsi=q1⋅∏1<j<iqjs\_\{i\}=q\_\{1\}\\cdot\\prod\_\{1<j<i\}q\_\{j\}fori≥2i\\geq 2,

f⁡\(x\)=x1​q1\+q12⋅f⁡\(x2,…,xm\),f\(x\)=x\_\{1\}q\_\{1\}\+q\_\{1\}^\{2\}\\cdot f\(x\_\{2\},\\dots,x\_\{m\}\),somaxx⁡f=Gm\\max\_\{x\}f=G\_\{m\}where

Gm=maxx∈\[0,1\]⁡\[x⁡\(1−x\)\+\(1−x\)2​Gm−1\],G0=0\.G\_\{m\}=\\max\_\{x\\in\[0,1\]\}\\bigl\[\\,x\(1\-x\)\+\(1\-x\)^\{2\}G\_\{m\-1\}\\,\\bigr\],\\qquad G\_\{0\}=0\.
Claim:Gm=m/\(2​\(m\+1\)\)G\_\{m\}=m/\(2\(m\+1\)\), with optimizerx∗=1/\(m\+1\)x^\{\*\}=1/\(m\+1\)\.

###### Proof by induction\.

Base:G0=0=0/2G\_\{0\}=0=0/2\. AssumeGm−1=\(m−1\)/\(2​m\)G\_\{m\-1\}=\(m\-1\)/\(2m\)\. The objectivex⁡\(1−x\)\+\(1−x\)2​\(m−1\)/\(2​m\)x\(1\-x\)\+\(1\-x\)^\{2\}\(m\-1\)/\(2m\)is a concave quadratic inxx; setting its derivative to zero,

\(1−2​x\)−m−1m​\(1−x\)=0\\displaystyle\(1\-2x\)\-\\tfrac\{m\-1\}\{m\}\(1\-x\)=0⇔m⁡\(1−2​x\)=\(m−1\)​\(1−x\)⇔x⁡\(m\+1\)=1,\\displaystyle\\quad\\iff m\(1\-2x\)=\(m\-1\)\(1\-x\)\\iff x\(m\+1\)=1,sox∗=1/\(m\+1\)∈\(0,1\)x^\{\*\}=1/\(m\+1\)\\in\(0,1\)\. The value there is

x∗​\(1−x∗\)\+\(1−x∗\)2​Gm−1\\displaystyle x^\{\*\}\(1\-x^\{\*\}\)\+\(1\-x^\{\*\}\)^\{2\}G\_\{m\-1\}=m\(m\+1\)2\+\(mm\+1\)2​m−12​m\\displaystyle=\\tfrac\{m\}\{\(m\+1\)^\{2\}\}\+\\bigl\(\\tfrac\{m\}\{m\+1\}\\bigr\)^\{2\}\\tfrac\{m\-1\}\{2m\}=2​m\+m⁡\(m−1\)2​\(m\+1\)2\\displaystyle=\\frac\{2m\+m\(m\-1\)\}\{2\(m\+1\)^\{2\}\}=m⁡\(m\+1\)2​\(m\+1\)2=m2​\(m\+1\)\.∎\\displaystyle=\\frac\{m\(m\+1\)\}\{2\(m\+1\)^\{2\}\}=\\frac\{m\}\{2\(m\+1\)\}\.\\qed

Combining Steps 3–4:𝔼⁡\[T\]≤V⋅Gm=m/\(2​\(m\+1\)\)⋅V\\mathbb\{E\}\[T\]\\leq\\sqrt\{V\}\\cdot\\sqrt\{G\_\{m\}\}=\\sqrt\{m/\(2\(m\+1\)\)\}\\cdot\\sqrt\{V\}\.

### C\.5Step 5: Attainment \(The Cascade Law\)

Take armk=1,…,mk=1,\\dots,m:

uk=km​with probability​xk=1k\+1,hence​dk=−xk​ukqk=−1m​for every​k\.\\begin\{gathered\}u\_\{k\}=\\tfrac\{k\}\{m\}\\ \\text\{with probability\}\\ x\_\{k\}=\\tfrac\{1\}\{k\+1\},\\\\ \\text\{hence\}\\ d\_\{k\}=\-\\tfrac\{x\_\{k\}u\_\{k\}\}\{q\_\{k\}\}=\-\\tfrac\{1\}\{m\}\\ \\text\{for every \}k\.\\end\{gathered\}The supremum is attained exactly, for everymm, by a two\-line computation\. Each arm has

Var⁡Zk=xk​uk2qk=1k\+1⋅k2m2⋅k\+1k=km2,\\operatorname\{Var\}Z\_\{k\}=\\frac\{x\_\{k\}u\_\{k\}^\{2\}\}\{q\_\{k\}\}=\\frac\{1\}\{k\+1\}\\cdot\\frac\{k^\{2\}\}\{m^\{2\}\}\\cdot\\frac\{k\+1\}\{k\}=\\frac\{k\}\{m^\{2\}\},soV=∑k=1mk/m2=\(m\+1\)/\(2​m\)V=\\sum\_\{k=1\}^\{m\}k/m^\{2\}=\(m\+1\)/\(2m\)\. The cascade is indexed by increasing up\-value \(uk=k/mu\_\{k\}=k/m\), so armkkoccupies sorted positionm\+1−km\+1\-k, and the head survival factor of Appendix[A\.1](https://arxiv.org/html/2610.31948#A1.SS1)at that position is the product of theqjq\_\{j\}over the arms with larger up\-value, that is overj\>kj\>k\. Withqj=1−1/\(j\+1\)=j/\(j\+1\)q\_\{j\}=1\-1/\(j\+1\)=j/\(j\+1\)the product telescopes:

s\(k\)=∏j\>kqj=∏j=k\+1mjj\+1=k\+1m\+1,s\_\{\(k\)\}=\\prod\_\{j\>k\}q\_\{j\}=\\prod\_\{j=k\+1\}^\{m\}\\frac\{j\}\{j\+1\}=\\frac\{k\+1\}\{m\+1\},so each term of the exact formula is

xk​uk​s\(k\)=1k\+1⋅km⋅k\+1m\+1=km⁡\(m\+1\),x\_\{k\}u\_\{k\}s\_\{\(k\)\}=\\frac\{1\}\{k\+1\}\\cdot\\frac\{k\}\{m\}\\cdot\\frac\{k\+1\}\{m\+1\}=\\frac\{k\}\{m\(m\+1\)\},and

𝔼⁡\[T\]=∑k=1mkm⁡\(m\+1\)=12identically in​m\.\\mathbb\{E\}\[T\]=\\sum\_\{k=1\}^\{m\}\\frac\{k\}\{m\(m\+1\)\}=\\frac\{1\}\{2\}\\quad\\text\{identically in \}m\.Hence𝔼​\[T\]2/V=\(1/4\)⋅2​m/\(m\+1\)=m/\(2​\(m\+1\)\)=Gm\\mathbb\{E\}\[T\]^\{2\}/V=\(1/4\)\\cdot 2m/\(m\+1\)=m/\(2\(m\+1\)\)=G\_\{m\}exactly\. The same configuration appears as the Theorem\-3 attaining law with the floor realized by a deterministic\-zero arm \(Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\)\. ∎

## Appendix DTheorem 3 \(Independent Noise, General\)

###### Theorem 3\.

For independent mean\-zeroZ1,…,ZMZ\_\{1\},\\dots,Z\_\{M\}:

sup𝔼⁡\[maxi⁡Zi\]/V=\(M−1\)/\(2​M\)=GM−1,\\sup\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]/\\sqrt\{V\}\\;=\\;\\sqrt\{\(M\-1\)/\(2M\)\}\\;=\\;\\sqrt\{G\_\{M\-1\}\},i\.e\. the Theorem\-2 value with one fewer arm: the optimal role of one arm is as a deterministic floor\. The sup is attained exactly \(Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\)\.

The proof is a chain of four reductions plus the attainment lemma:

two\-point reduction \([D\.1](https://arxiv.org/html/2610.31948#A4.SS1)\)→convexity \([D\.2](https://arxiv.org/html/2610.31948#A4.SS2)\)→\\displaystyle\\text\{two\-point reduction \(\\ref\{app:d1\}\)\}\\to\\text\{convexity \(\\ref\{app:d2\}\)\}\\to\{\}head recursion \([D\.3](https://arxiv.org/html/2610.31948#A4.SS3)\)→Φt≤Gt​\([D\.4](https://arxiv.org/html/2610.31948#A4.SS4)\);attainment \([D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\)\.\\displaystyle\\text\{head recursion \(\\ref\{app:d3\}\)\}\\to\\Phi\_\{t\}\\leq G\_\{t\}\\ \\text\{\(\\ref\{app:d4\}\)\};\\quad\\text\{attainment \(\\ref\{app:d5\}\)\}\.Throughout, only upper bounds \(≤\\leq\) are needed in[D\.1](https://arxiv.org/html/2610.31948#A4.SS1)–[D\.4](https://arxiv.org/html/2610.31948#A4.SS4); equality follows from[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\.

### D\.1The Two\-Point Reduction

###### Proposition\(two\-point reduction\)\.

R∗:=sup\{𝔼⁡\[maxi⁡Zi\]:Zi​independent, mean\-zero,​∑Var⁡Zi≤1\}R^\{\*\}:=\\sup\\\{\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]:Z\_\{i\}\\text\{ independent, mean\-zero, \}\\textstyle\\sum\\operatorname\{Var\}Z\_\{i\}\\leq 1\\\}is unchanged if every arm is restricted to laws with at most two atoms\.

###### Proof\.

Step 0 \(normalization and finiteness\)\.𝔼⁡\[maxi⁡Zi\]≥maxi⁡𝔼⁡\[Zi\]=0\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]\\geq\\max\_\{i\}\\mathbb\{E\}\[Z\_\{i\}\]=0, and scalingZ→c​ZZ\\to cZscales the objective byccand the variance byc2c^\{2\}, so the sup over∑Var≤1\\sum\\operatorname\{Var\}\\leq 1equals \(as suprema\) the sup at∑Var=1\\sum\\operatorname\{Var\}=1, and the ratio form𝔼⁡\[max\]/∑Var\\mathbb\{E\}\[\\max\]/\\sqrt\{\\sum\\operatorname\{Var\}\}has the same value\.R∗R^\{\*\}is finite before anything else is argued: Corollary 1a \(Samuelson pointwise plus Cauchy–Schwarz; no independence used\) gives𝔼⁡\[maxi⁡Zi\]≤\(M−1\)/M⋅V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]\\leq\\sqrt\{\(M\-1\)/M\}\\cdot\\sqrt\{V\}for every mean\-zero vector, so

0≤R∗≤\(M−1\)/M<1\.0\\leq R^\{\*\}\\leq\\sqrt\{\(M\-1\)/M\}<1\.AssumeM≥2M\\geq 2throughout Steps 1–5 \(atM=1M=1the theorem is the trivial0=00=0andZ−imaxZ^\{\\max\}\_\{\-i\}below would be a maximum over an empty set\); forM≥2M\\geq 2,R∗\>0R^\{\*\}\>0\(the arm±1\\pm 1with probability1/21/2each, plus a zero arm, gives1/21/2\)\.

Step 1 \(Dinkelbach conjugation\)\.Forλ\>0\\lambda\>0let

Φ⁡\(λ\)=sup\{𝔼⁡\[maxi⁡Zi\]−λ⋅∑Var⁡Zi\}\\Phi\(\\lambda\)=\\sup\\Bigl\\\{\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]\-\\lambda\\cdot\\sum\\operatorname\{Var\}Z\_\{i\}\\Bigr\\\}over independent mean\-zero laws, unconstrained\. For anyZZwith∑Var=s\\sum\\operatorname\{Var\}=s:𝔼⁡\[max\]≤R∗​s\\mathbb\{E\}\[\\max\]\\leq R^\{\*\}\\sqrt\{s\}\(finite by Step 0\), so

𝔼⁡\[max\]−λ​s≤maxs≥0⁡\(R∗​s−λ​s\)=R∗2/\(4​λ\);\\mathbb\{E\}\[\\max\]\-\\lambda s\\leq\\max\_\{s\\geq 0\}\\bigl\(R^\{\*\}\\sqrt\{s\}\-\\lambda s\\bigr\)=R^\{\*2\}/\(4\\lambda\);conversely, scaling a near\-optimalZZtos=\(R∗/2​λ\)2s=\(R^\{\*\}/2\\lambda\)^\{2\}shows equality\. SoΦ⁡\(λ\)=R∗2/\(4​λ\)<∞\\Phi\(\\lambda\)=R^\{\*2\}/\(4\\lambda\)<\\infty, and determiningΦ\\Phion the two\-point class determinesR∗R^\{\*\}on it, unambiguously, viaR∗=2​λ​Φ​\(λ\)R^\{\*\}=2\\sqrt\{\\lambda\\Phi\(\\lambda\)\}, which needs onlyR∗≥0R^\{\*\}\\geq 0\.

Step 2 \(per\-arm linearity\)\.Fixλ\\lambdaand all arms exceptii, and letZ−imax=maxj≠i⁡ZjZ^\{\\max\}\_\{\-i\}=\\max\_\{j\\neq i\}Z\_\{j\}\(independent ofZiZ\_\{i\}\)\. Define

g⁡\(z\)=𝔼⁡\[max⁡\(z,Z−imax\)\]\.g\(z\)=\\mathbb\{E\}\\bigl\[\\max\(z,Z^\{\\max\}\_\{\-i\}\)\\bigr\]\.ggis a 1\-Lipschitz convex function withg⁡\(z\)→𝔼⁡\[Z−imax\]g\(z\)\\to\\mathbb\{E\}\[Z^\{\\max\}\_\{\-i\}\]asz→−∞z\\to\-\\inftyandg⁡\(z\)∼zg\(z\)\\sim zasz→\+∞z\\to\+\\infty\(indeedg⁡\(z\)−z=𝔼⁡\[\(Z−imax−z\)\+\]↓0g\(z\)\-z=\\mathbb\{E\}\[\(Z^\{\\max\}\_\{\-i\}\-z\)^\{\+\}\]\\downarrow 0\)\. The Fubini step behindggis licensed:\|max⁡\(z,Z−imax\)\|≤\|z\|\+\|Z−imax\|\|\\max\(z,Z^\{\\max\}\_\{\-i\}\)\|\\leq\|z\|\+\|Z^\{\\max\}\_\{\-i\}\|, both integrable \(finite variance plus mean zero impliesL1L^\{1\}\), product measure, so Tonelli/Fubini applies\. The per\-arm objective is then

Ji​\(μ\)=∫ψ​𝑑μ\+const,ψ:=g−λ​z2J\_\{i\}\(\\mu\)=\\int\\psi\\,d\\mu\+\\text\{const\},\\qquad\\psi:=g\-\\lambda z^\{2\}\(defined as one integral, not a difference\), which is linear inμ\\mu; the constraint set is\{μ∈P⁡\(ℝ\):∫z​𝑑μ=0\}\\\{\\mu\\in P\(\\mathbb\{R\}\):\\int z\\,d\\mu=0\\\}\.

Step 3 \(integrability; no compactness needed\)\.ψ\\psiis bounded above: on the left,g→𝔼⁡\[Z−imax\]g\\to\\mathbb\{E\}\[Z^\{\\max\}\_\{\-i\}\], soψ≤C−λ​z2\\psi\\leq C\-\\lambda z^\{2\}; on the right,g⁡\(z\)−z=𝔼⁡\[\(Z−imax−z\)\+\]↓0g\(z\)\-z=\\mathbb\{E\}\[\(Z^\{\\max\}\_\{\-i\}\-z\)^\{\+\}\]\\downarrow 0, soψ≤C\+z−λ​z2\\psi\\leq C\+z\-\\lambda z^\{2\}\. HencesupJi<∞\\sup J\_\{i\}<\\infty,JiJ\_\{i\}is well\-defined in\[−∞,∞\)\[\-\\infty,\\infty\)for every mean\-zeroμ\\mu\(measures without a second moment score−∞\-\\infty\), and anyμ\\muwithJi​\(μ\)\>−∞J\_\{i\}\(\\mu\)\>\-\\inftyhasψ∈L1​\(μ\)\\psi\\in L^\{1\}\(\\mu\)\. That is all that Step 4’s general\-integrand theorem requires: no compact\-support detour is necessary\.

The compact\-support route via Tchakaloff’s theorem is therefore available but not needed, and we do not take it\.

Step 4 \(Bayer–Teichmann plus linear\-program basic solutions\)\.Consider the moment map

μ↦\(∫𝑑μ,∫z​𝑑μ,∫ψ​𝑑μ\)\.\\mu\\mapsto\\Bigl\(\\int d\\mu,\\ \\int z\\,d\\mu,\\ \\int\\psi\\,d\\mu\\Bigr\)\.Apply Corollary 2 of[Bayer and Teichmann \(2006\)](https://arxiv.org/html/2610.31948#bib.bib6)withΩ=ℝ\\Omega=\\mathbb\{R\},AAany full\-measure set, andφ=\(1,z,ψ\):ℝ→ℝ3\\varphi=\(1,z,\\psi\):\\mathbb\{R\}\\to\\mathbb\{R\}^\{3\}: for a positive measureμ\\muconcentrated inAAand a Borel mapφ:Ω→ℝN\\varphi:\\Omega\\to\\mathbb\{R\}^\{N\}whose push\-forwardφ∗​μ\\varphi\_\{\*\}\\muhas first moments, there exist an integer1≤k≤N1\\leq k\\leq N, pointsω1,…,ωk∈A\\omega\_\{1\},\\dots,\\omega\_\{k\}\\in Aand weightsλi\>0\\lambda\_\{i\}\>0with∫Ωφj​𝑑μ=∑i=1kλi​φj​\(ωi\)\\int\_\{\\Omega\}\\varphi\_\{j\}\\,d\\mu=\\sum\_\{i=1\}^\{k\}\\lambda\_\{i\}\\varphi\_\{j\}\(\\omega\_\{i\}\)for everyjj, under integrability alone\. The hypotheses hold here:1,z,ψ1,z,\\psiare Borel andμ\\mu\-integrable;11becauseμ\\muis a probability measure;z∈L1​\(μ\)z\\in L^\{1\}\(\\mu\)because the mean\-zero constraint presupposes it;ψ∈L1​\(μ\)\\psi\\in L^\{1\}\(\\mu\)may be assumed by Step 3 \(ψ\\psiis continuous and bounded above\)\. Conclusion: the value vector is achieved by a measure with at mostN=3N=3atoms, of mass exactly11\(theφ1=1\\varphi\_\{1\}=1coordinate\) and mean exactly00\(theφ2=z\\varphi\_\{2\}=zcoordinate\)\.

The argument does not depend on the exact atom count from the citation: among measures on any finite atom set, maximizing the linear objective∫ψ​𝑑μ\\int\\psi\\,d\\muunder the two equality constraints \(mass=1\\text\{mass\}=1,mean=0\\text\{mean\}=0\) is a linear program \(LP\) whose constraint matrix\[\[1,1,…\],\[z1,z2,…\]\]\[\[1,1,\\dots\],\[z\_\{1\},z\_\{2\},\\dots\]\]has rank≤2\\leq 2and whose feasible set is a compact subset of the simplex; hence the LP is never unbounded, and an optimal vertex with at most 2 active atoms exists \(rank\-1 degeneracy forces a one\-point measure, which, being mean\-zero, isδ0\\delta\_\{0\}\)\. Combining: the per\-arm sup is approached within two\-point mean\-zero laws\. \(The underlying convexity fact is that the barycenter of an integrable random vector lies in the convex hull, not just the closed hull, of its support; this is the probability\-measure consequence that[Bayer and Teichmann \(2006\)](https://arxiv.org/html/2610.31948#bib.bib6)derive from their Theorem 1\.\)

Step 5 \(one sweep, exact replacements\)\.The joint objective isJi​\(μi\)\+ciJ\_\{i\}\(\\mu\_\{i\}\)\+c\_\{i\}, where bothggandci=−λ∑j≠iVarZjc\_\{i\}=\-\\lambda\\sum\_\{j\\neq i\}\\operatorname\{Var\}Z\_\{j\}depend only on the other arms\. Replace arms one at a time by anexactLP optimum: by Steps 3–4, for each arm there is a two\-point mean\-zero law whoseJiJ\_\{i\}value is≥Ji​\(μi\)\\geq J\_\{i\}\(\\mu\_\{i\}\)\(the finitely\-atomic representer followed by the LP vertex; both exact, no per\-armε\\varepsilon\)\. Each replacement does not decrease the joint value, and a previously replaced arm’s*law*stays supported on at most two atoms \(possibly the one\-pointδ0\\delta\_\{0\}; later replacements change only its role inZ−jmaxZ^\{\\max\}\_\{\-j\}, and support size is a property of the law itself\)\. A later replacement may destroy the per\-arm optimality of an earlier one; this is immaterial, because the argument uses only two facts about each replacement: it does not decrease the joint value, and it leaves the replaced arm two\-point\. One sweep ofMMexact replacements from anε\\varepsilon\-optimal starting configuration givesΦ2​p​t​\(λ\)≥Φ⁡\(λ\)−ε\\Phi\_\{\\mathrm\{2pt\}\}\(\\lambda\)\\geq\\Phi\(\\lambda\)\-\\varepsilon; with the trivial≤\\leq,Φ2​p​t=Φ\\Phi\_\{\\mathrm\{2pt\}\}=\\Phi, and Step 1 run inside the two\-point class \(which is scaling\-closed\) givesR2​p​t=R∗R\_\{\\mathrm\{2pt\}\}=R^\{\*\}\. The sweep terminates inMMsteps\. ∎

### D\.2The Convexity Step

Work in the two\-point class with∑Var=1\\sum\\operatorname\{Var\}=1, arms sorted by up value, and the notation of Appendix[A\.1](https://arxiv.org/html/2610.31948#A1.SS1)\(wi=xi​uiw\_\{i\}=x\_\{i\}u\_\{i\},sis\_\{i\},QQ,PkP\_\{k\}\)\. The formula forE⁡\(w\)E\(w\)below is derived under the sort orderu1≥⋯≥uMu\_\{1\}\\geq\\dots\\geq u\_\{M\}; the maximization over the variance ellipsoid afterwards drops the order constraint, which can only enlarge the supremum, and an upper bound is all that is required\. Partition by the first up arm as in Appendix[C\.2](https://arxiv.org/html/2610.31948#A3.SS2), except that the all\-down event \(probabilityQQ\) now contributes the largest*down*valuemaxi⁡di=−mini⁡\(wi/qi\)\\max\_\{i\}d\_\{i\}=\-\\min\_\{i\}\(w\_\{i\}/q\_\{i\}\)instead of00; the objective is

E⁡\(w\)=∑iwi​si−Q⋅mini⁡\(wi/qi\)\.E\(w\)=\\sum\_\{i\}w\_\{i\}s\_\{i\}\-Q\\cdot\\min\_\{i\}\(w\_\{i\}/q\_\{i\}\)\.Since−min=max\-\\min=\\maxof the negatives,E⁡\(w\)=maxk⁡Lk​\(w\)E\(w\)=\\max\_\{k\}L\_\{k\}\(w\)with

Lk​\(w\)=∑iwi​si−Q⋅wk/qk,L\_\{k\}\(w\)=\\sum\_\{i\}w\_\{i\}s\_\{i\}\-Q\\cdot w\_\{k\}/q\_\{k\},a maximum ofMMlinearfunctionals ofww, hence convex; andEEis homogeneous of degree 1 inww\. For fixedxx, the variance constraint∑ivi=∑iwi2/\(xi​qi\)≤1\\sum\_\{i\}v\_\{i\}=\\sum\_\{i\}w\_\{i\}^\{2\}/\(x\_\{i\}q\_\{i\}\)\\leq 1is an ellipsoid inww, so

supellipsoidE=max⁡supellipsoidk⁡Lk=maxk⁡hk​\(x\),\\sup\_\{\\text\{ellipsoid\}\}E=\\max\_\{k\}\\sup\_\{\\text\{ellipsoid\}\}L\_\{k\}=\\max\_\{k\}\\sqrt\{h\_\{k\}\(x\)\},with

hk​\(x\):=∑i≠kxi​qi​si2\+xk​qk​sk2​\(1−Pk\)2,h\_\{k\}\(x\):=\\sum\_\{i\\neq k\}x\_\{i\}q\_\{i\}s\_\{i\}^\{2\}\+x\_\{k\}q\_\{k\}s\_\{k\}^\{2\}\(1\-P\_\{k\}\)^\{2\},wherePk=∏j\>kqjP\_\{k\}=\\prod\_\{j\>k\}q\_\{j\}\(the coefficient ofwkw\_\{k\}inLkL\_\{k\}issk−Q/qk=sk​\(1−Pk\)s\_\{k\}\-Q/q\_\{k\}=s\_\{k\}\(1\-P\_\{k\}\), usingQ=sk​qk​PkQ=s\_\{k\}q\_\{k\}P\_\{k\}; equivalently, the expansion uses1−P⁡\(2−P\)=\(1−P\)21\-P\(2\-P\)=\(1\-P\)^\{2\}\)\. Because the supremum is taken as a maximum over thekkattaining arms rather than through a first\-order condition, ties among them, subgradients and boundary cases play no role\.

Ifkkis last in sort order,Pk=1P\_\{k\}=1andhk=fM−1​\(x\)≤GM−1h\_\{k\}=f\_\{M\-1\}\(x\)\\leq G\_\{M\-1\}immediately \(Theorem 2, Step[C\.4](https://arxiv.org/html/2610.31948#A3.SS4)\)\. The remaining task issupxhk​\(x\)≤GM−1\\sup\_\{x\}h\_\{k\}\(x\)\\leq G\_\{M\-1\}for everykk\.

### D\.3The Head Recursion

Decomposehkh\_\{k\}: withA=∑i<kxi​qi​si2A=\\sum\_\{i<k\}x\_\{i\}q\_\{i\}s\_\{i\}^\{2\}the head sum,S=skS=s\_\{k\}, tail valueΘ=ft​\(y\)\\Theta=f\_\{t\}\(y\)over thet=M−kt=M\-karms afterkk\(in their own coordinatesyy, with survivals computed inside the tail\), and tail survivalP=PkP=P\_\{k\},

hk=A\+S2⋅\[xk​qk​\(1−P\)2\+qk2​Θ\]h\_\{k\}=A\+S^\{2\}\\cdot\\bigl\[\\,x\_\{k\}q\_\{k\}\(1\-P\)^\{2\}\+q\_\{k\}^\{2\}\\Theta\\,\\bigr\]\(fori\>ki\>k,si=sk​qk⋅∏k<j<iqjs\_\{i\}=s\_\{k\}q\_\{k\}\\cdot\\prod\_\{k<j<i\}q\_\{j\}, which yields the factorS2​qk2S^\{2\}q\_\{k\}^\{2\}on the tail sum\)\. The bracket equals

Φt​\(xk,y\):=xk​\(1−xk\)​\(1−P⁡\(y\)\)2\+\(1−xk\)2​ft​\(y\),\\Phi\_\{t\}\(x\_\{k\},y\):=x\_\{k\}\(1\-x\_\{k\}\)\(1\-P\(y\)\)^\{2\}\+\(1\-x\_\{k\}\)^\{2\}f\_\{t\}\(y\),the key quantity of Appendix[D\.4](https://arxiv.org/html/2610.31948#A4.SS4)\. Maximizing the head over itsk−1k\-1arms is the recursionR⁡\(c\)=maxx⁡\[x⁡\(1−x\)\+\(1−x\)2​c\]R\(c\)=\\max\_\{x\}\\bigl\[x\(1\-x\)\+\(1\-x\)^\{2\}c\\bigr\]appliedk−1k\-1times \(peel the first arm as in Appendix[C\.4](https://arxiv.org/html/2610.31948#A3.SS4):A\+S2​c=x1​q1\+q12​\[A′\+S′2​c\]A\+S^\{2\}c=x\_\{1\}q\_\{1\}\+q\_\{1\}^\{2\}\[A^\{\\prime\}\+S^\{\\prime 2\}c\]\),RRis increasing incc\(the coefficient\(1−x\)2\(1\-x\)^\{2\}is nonnegative\), andR⁡\(Gj\)=Gj\+1R\(G\_\{j\}\)=G\_\{j\+1\}, which is the Theorem\-2 recursion\. Hence

supxhk≤Rk−1​\(supΦM−k\),\\sup\_\{x\}h\_\{k\}\\leq R^\{k\-1\}\\bigl\(\\sup\\Phi\_\{M\-k\}\\bigr\),andonly≤\\leqis needed; equality holds numerically but is not claimed\. GivenΦt≤Gt\\Phi\_\{t\}\\leq G\_\{t\}\(Appendix[D\.4](https://arxiv.org/html/2610.31948#A4.SS4)\),

supxhk≤Rk−1​\(GM−k\)=GM−1for every​k=1\.\.M\.\\sup\_\{x\}h\_\{k\}\\leq R^\{k\-1\}\(G\_\{M\-k\}\)=G\_\{M\-1\}\\qquad\\text\{for every \}k=1\.\.M\.\(The composition identity holds becauseR⁡\(Gj\)=Gj\+1R\(G\_\{j\}\)=G\_\{j\+1\}for everyjj: this is them=j\+1m=j\+1instance of the recursion solved in Appendix[C\.4](https://arxiv.org/html/2610.31948#A3.SS4), soRk−1​\(GM−k\)=GM−1R^\{k\-1\}\(G\_\{M\-k\}\)=G\_\{M\-1\}follows by induction onkk\.\) Combining[D\.1](https://arxiv.org/html/2610.31948#A4.SS1)–[D\.3](https://arxiv.org/html/2610.31948#A4.SS3)with[D\.4](https://arxiv.org/html/2610.31948#A4.SS4):

sup𝔼⁡\[maxi⁡Zi\]/V\\displaystyle\\sup\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\]/\\sqrt\{V\}≤maxk⁡supxhk\\displaystyle\\leq\\max\_\{k\}\\sqrt\{\\sup\\nolimits\_\{x\}h\_\{k\}\}≤GM−1=\(M−1\)/\(2​M\)\.\\displaystyle\\leq\\sqrt\{G\_\{M\-1\}\}=\\sqrt\{\(M\-1\)/\(2M\)\}\.

### D\.4The Key InequalityΦt≤Gt\\Phi\_\{t\}\\leq G\_\{t\}

###### Proposition\.

For att\-arm tail \(t≥1t\\geq 1\),

Φt​\(x,y\)=x⁡\(1−x\)​\(1−P⁡\(y\)\)2\+\(1−x\)2​ft​\(y\)≤Gt,\\Phi\_\{t\}\(x,y\)=x\(1\-x\)\(1\-P\(y\)\)^\{2\}\+\(1\-x\)^\{2\}f\_\{t\}\(y\)\\leq G\_\{t\},whereP⁡\(y\)=∏j\(1−yj\)P\(y\)=\\prod\_\{j\}\(1\-y\_\{j\}\)andft​\(y\)=∑jyj​\(1−yj\)​\(sj′\)2f\_\{t\}\(y\)=\\sum\_\{j\}y\_\{j\}\(1\-y\_\{j\}\)\(s^\{\\prime\}\_\{j\}\)^\{2\}withsj′s^\{\\prime\}\_\{j\}the within\-tail survivals\.

*Proof, in four steps\.*

Step 1 \(the tail trade\-off curve has a closed form\)\.Define

Ψt​\(P\)=sup\{ft​\(y\):∏j\(1−yj\)=P\},\\Psi\_\{t\}\(P\)=\\sup\\bigl\\\{f\_\{t\}\(y\):\\textstyle\\prod\_\{j\}\(1\-y\_\{j\}\)=P\\bigr\\\},the best tail value at fixed tail survival\. Then

Ψt​\(P\)=\(1−P\)⋅\[\(t−1\)\+\(t\+1\)​P\]2​t\.\\Psi\_\{t\}\(P\)=\\frac\{\(1\-P\)\\cdot\\bigl\[\(t\-1\)\+\(t\+1\)P\\bigr\]\}\{2t\}\.
###### Proof by induction\.

Baset=1t=1:Ψ1​\(P\)=P⁡\(1−P\)\\Psi\_\{1\}\(P\)=P\(1\-P\)directly \(one arm,y1=1−Py\_\{1\}=1\-P\), matching the formula\. For the step, peel the first tail arm \(r=1−y1r=1\-y\_\{1\}, so the remaining constraint is∏j≥2\(1−yj\)=P/r\\prod\_\{j\\geq 2\}\(1\-y\_\{j\}\)=P/r\):

Ψt​\(P\)=maxr∈\[P,1\]⁡\[\(1−r\)​r\+r2​Ψt−1​\(P/r\)\]\.\\Psi\_\{t\}\(P\)=\\max\_\{r\\in\[P,1\]\}\\bigl\[\\,\(1\-r\)r\+r^\{2\}\\Psi\_\{t\-1\}\(P/r\)\\,\\bigr\]\.Substituting the inductive form, the objective is a downward parabola inrr\(leading coefficient−t/\(2\(t−1\)\)<0\-t/\(2\(t\-1\)\)<0\) with unique critical point

r∗=t−1\+Pt,r^\{\*\}=\\frac\{t\-1\+P\}\{t\},which is feasible:r∗≥P⇔\(t−1\)​\(1−P\)≥0r^\{\*\}\\geq P\\iff\(t\-1\)\(1\-P\)\\geq 0, andr∗≤1⇔P≤1r^\{\*\}\\leq 1\\iff P\\leq 1\. Explicitly, substitutingΨt−1​\(P/r\)=\(r−P\)​\(\(t−2\)​r\+t​P\)/\(2​\(t−1\)​r2\)\\Psi\_\{t\-1\}\(P/r\)=\(r\-P\)\(\(t\-2\)r\+tP\)/\(2\(t\-1\)r^\{2\}\)gives the objective

r−r2\+\(r−P\)​\(\(t−2\)​r\+t​P\)2​\(t−1\),r\-r^\{2\}\+\\frac\{\(r\-P\)\\bigl\(\(t\-2\)r\+tP\\bigr\)\}\{2\(t\-1\)\},a quadratic inrrwith coefficients

a=−t2​\(t−1\),b=t−1\+Pt−1,c=−t​P22​\(t−1\)\.a=\\frac\{\-t\}\{2\(t\-1\)\},\\qquad b=\\frac\{t\-1\+P\}\{t\-1\},\\qquad c=\\frac\{\-tP^\{2\}\}\{2\(t\-1\)\}\.Its value at the vertexr∗=−b/\(2a\)=\(t−1\+P\)/tr^\{\*\}=\-b/\(2a\)=\(t\-1\+P\)/tisc−b2/\(4​a\)c\-b^\{2\}/\(4a\), and the numerator factors:

\(t−1\+P\)2−t2​P2\\displaystyle\(t\-1\+P\)^\{2\}\-t^\{2\}P^\{2\}=\(t−1\+P−t​P\)​\(t−1\+P\+t​P\)\\displaystyle=\(t\-1\+P\-tP\)\(t\-1\+P\+tP\)=\(t−1\)​\(1−P\)\\displaystyle=\(t\-1\)\(1\-P\)⋅\[\(t−1\)\+\(t\+1\)​P\],\\displaystyle\\cdot\\bigl\[\(t\-1\)\+\(t\+1\)P\\bigr\],so the vertex value is\(1−P\)​\[\(t−1\)\+\(t\+1\)​P\]/\(2​t\)\(1\-P\)\\bigl\[\(t\-1\)\+\(t\+1\)P\\bigr\]/\(2t\), which is the claimed form\.

*TheP=0P=0branch\.*The peeling identity presumesr\>0r\>0\. AtP=0P=0the excludedr=0r=0branch \(y1=1y\_\{1\}=1\) givesft=y1​\(1−y1\)\+0=0f\_\{t\}=y\_\{1\}\(1\-y\_\{1\}\)\+0=0, which never attains the max fort≥2t\\geq 2\. MoreoverΨt​\(0\)=Gt−1\\Psi\_\{t\}\(0\)=G\_\{t\-1\}is attained as a value, not merely a supremum:ftf\_\{t\}is a polynomial, well\-defined atyj=1y\_\{j\}=1, and placing an always\-firing arm last reducesftf\_\{t\}toft−1f\_\{t\-1\}of the remaining arms, whose maximum isGt−1G\_\{t\-1\}by Appendix[C\.4](https://arxiv.org/html/2610.31948#A3.SS4)\.

Two checks of the closed form: atP=1/\(t\+1\)P=1/\(t\+1\),1−P=t/\(t\+1\)1\-P=t/\(t\+1\)and\(t−1\)\+\(t\+1\)​P=t\(t\-1\)\+\(t\+1\)P=t, soΨt=t/\(2​\(t\+1\)\)=Gt\\Psi\_\{t\}=t/\(2\(t\+1\)\)=G\_\{t\}, matching the telescoped survival of the optimal schedule; atP=0P=0,Ψt=\(t−1\)/\(2​t\)=Gt−1\\Psi\_\{t\}=\(t\-1\)/\(2t\)=G\_\{t\-1\}, consistent with an always\-firing arm placed last costing nothing\. ∎

Step 1′\(order\-independence; why the upper envelope is safe\)\.ftf\_\{t\}is order\-dependent, but theuu\-variables were already eliminated by the Cauchy–Schwarz step, so no sort constraint binds onyy; andΨt\\Psi\_\{t\}takes the sup over*all*ordered tuples, which dominates the specific ordered configuration appearing inhkh\_\{k\}\. The boundft​\(y\)≤Ψt​\(P⁡\(y\)\)f\_\{t\}\(y\)\\leq\\Psi\_\{t\}\(P\(y\)\)therefore holds pointwise, and only this pointwise domination is used below\.

Step 2 \(vertex analysis\)\.For fixed tailyy, Step 1′gives

Φt​\(x,y\)≤F⁡\(x\):=α​x​\(1−x\)\+β​\(1−x\)2,α=\(1−P\)2,β=Ψt\(P\)\.\\begin\{gathered\}\\Phi\_\{t\}\(x,y\)\\leq F\(x\):=\\alpha\\,x\(1\-x\)\+\\beta\\,\(1\-x\)^\{2\},\\\\ \\alpha=\(1\-P\)^\{2\},\\qquad\\beta=\\Psi\_\{t\}\(P\)\.\\end\{gathered\}FFis a quadratic inxxwithF⁡\(0\)=βF\(0\)=\\beta,F⁡\(1\)=0F\(1\)=0, and vertexx∗=\(α−2​β\)/\(2​\(α−β\)\)x^\{\*\}=\(\\alpha\-2\\beta\)/\(2\(\\alpha\-\\beta\)\)whenβ<α\\beta<\\alpha\. Cases:

- •β≥α\\beta\\geq\\alpha:the parabola opens upward \(coefficientβ−α≥0\\beta\-\\alpha\\geq 0\), so the max over\[0,1\]\[0,1\]is at an endpoint;F⁡\(0\)=β=Ψt​\(P\)≤GtF\(0\)=\\beta=\\Psi\_\{t\}\(P\)\\leq G\_\{t\}\(Step 1’s form is maximized atP=1/\(t\+1\)P=1/\(t\+1\)with valueGtG\_\{t\}\) andF⁡\(1\)=0F\(1\)=0\.
- •α/2≤β<α\\alpha/2\\leq\\beta<\\alpha:downward parabola with vertexx∗=\(α−2​β\)/\(2​\(α−β\)\)≤0x^\{\*\}=\(\\alpha\-2\\beta\)/\(2\(\\alpha\-\\beta\)\)\\leq 0, so the max on\[0,1\]\[0,1\]is atx=0x=0,F=β≤GtF=\\beta\\leq G\_\{t\}\.
- •β<α/2\\beta<\\alpha/2\(interior vertex\):the vertex value isF∗=β\+\(α−2​β\)2/\(4​\(α−β\)\)F^\{\*\}=\\beta\+\(\\alpha\-2\\beta\)^\{2\}/\(4\(\\alpha\-\\beta\)\), and F∗≤Gt⇔β≤α−α2/\(4​Gt\)\.F^\{\*\}\\leq G\_\{t\}\\iff\\beta\\leq\\alpha\-\\alpha^\{2\}/\(4G\_\{t\}\)\.- –Sub\-caseα≤2​Gt\\alpha\\leq 2G\_\{t\}:α−α2/\(4​Gt\)≥α−α/2=α/2\>β\\alpha\-\\alpha^\{2\}/\(4G\_\{t\}\)\\geq\\alpha\-\\alpha/2=\\alpha/2\>\\beta, soF∗≤GtF^\{\*\}\\leq G\_\{t\}\. - –Sub\-caseα\>2​Gt\\alpha\>2G\_\{t\}, i\.e\.a:=1−P\>t/\(t\+1\)a:=1\-P\>\\sqrt\{t/\(t\+1\)\}: the one nontrivial branch, handled in Step 3\.

Step 3 \(the nontrivial branch is a factored cubic\)\.WithΨt​\(1−a\)=a⁡\(2​t−\(t\+1\)​a\)/\(2​t\)\\Psi\_\{t\}\(1\-a\)=a\(2t\-\(t\+1\)a\)/\(2t\)and1/\(4​Gt\)=\(t\+1\)/\(2​t\)1/\(4G\_\{t\}\)=\(t\+1\)/\(2t\), the required inequalityβ≤α−α2/\(4​Gt\)\\beta\\leq\\alpha\-\\alpha^\{2\}/\(4G\_\{t\}\)readsΨt​\(1−a\)≤a2−\(t\+1\)​a4/\(2​t\)\\Psi\_\{t\}\(1\-a\)\\leq a^\{2\}\-\(t\+1\)a^\{4\}/\(2t\), and

\(2​t/a\)⋅\[a2−\(t\+1\)​a4/\(2​t\)−Ψt​\(1−a\)\]\\displaystyle\(2t/a\)\\cdot\\bigl\[\\,a^\{2\}\-\(t\+1\)a^\{4\}/\(2t\)\-\\Psi\_\{t\}\(1\-a\)\\,\\bigr\]=−\(a−1\)⋅\(\(t\+1\)a2\+\(t\+1\)a−2t\)\\displaystyle=\-\(a\-1\)\\cdot\\bigl\(\(t\+1\)a^\{2\}\+\(t\+1\)a\-2t\\bigr\)\(an identity verified by expanding both sides\)\. Ona∈\[t/\(t\+1\),1\]a\\in\[\\sqrt\{t/\(t\+1\)\},1\]: the factor\(a−1\)≤0\(a\-1\)\\leq 0; the second factor at the left endpoint is\(t\+1\)⋅t/\(t\+1\)\+\(t\+1\)​t/\(t\+1\)−2​t=t⁡\(t\+1\)−t\>0\(t\+1\)\\cdot t/\(t\+1\)\+\(t\+1\)\\sqrt\{t/\(t\+1\)\}\-2t=\\sqrt\{t\(t\+1\)\}\-t\>0and is increasing inaa, so the product is≥0\\geq 0throughout, i\.e\.Ψt​\(1−a\)≤a2−a4/\(4​Gt\)\\Psi\_\{t\}\(1\-a\)\\leq a^\{2\}\-a^\{4\}/\(4G\_\{t\}\)where it is needed, with equality only ata=1a=1\. ∎

Step 4 \(endpoints meet, and the equality branch\)\.Ata=1a=1\(P=0P=0\):

Ψt​\(0\)=Gt−1=1−14​Gt\\Psi\_\{t\}\(0\)=G\_\{t\-1\}=1\-\\frac\{1\}\{4G\_\{t\}\}\(both sides equal\(t−1\)/\(2​t\)\(t\-1\)/\(2t\)\): the constraint curve and the trade\-off curve touch at the always\-firing\-tail configuration\. The equality branch ata=1a=1for generalttis

x∗=1/\(t\+1\)with an always\-firinglasttail arm\.x^\{\*\}=1/\(t\+1\)\\quad\\text\{with an always\-firing \{last\} tail arm\.\}This is the regime in which the tail always fires and armkkitself takes the role of the deterministic floor\. ∎

This completes the chain:[D\.1](https://arxiv.org/html/2610.31948#A4.SS1)\(two\-point reduction\)→\\to[D\.2](https://arxiv.org/html/2610.31948#A4.SS2)\(maxk⁡hk\\max\_\{k\}\\sqrt\{h\_\{k\}\}\)→\\to[D\.3](https://arxiv.org/html/2610.31948#A4.SS3)\(Rk−1R^\{k\-1\}composition,≤\\leqonly\)→\\to[D\.4](https://arxiv.org/html/2610.31948#A4.SS4)\(Φt≤Gt\\Phi\_\{t\}\\leq G\_\{t\}\) givessup𝔼⁡\[maxi⁡Zi\]/V≤\(M−1\)/\(2​M\)\\sup\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}\\leq\\sqrt\{\(M\-1\)/\(2M\)\}for independent mean\-zero noise\. Equality is Appendix[D\.5](https://arxiv.org/html/2610.31948#A4.SS5)\.

### D\.5The Attainment Lemma

###### Attainment Lemma\.

The Theorem\-3 sup is attained exactly for everyMM: the\(M−1\)\(M\-1\)\-arm cascade of Theorem 2 \(armkk:uk=k/\(M−1\)u\_\{k\}=k/\(M\-1\)with probability1/\(k\+1\)1/\(k\+1\), else−1/\(M−1\)\-1/\(M\-1\)\) plus onedeterministic\-zero armis a legitimate independentMM\-arm mean\-zero configuration, and𝔼⁡\[maxi⁡Zi\]=𝔼⁡\[max⁡\(0,Z1,…,ZM−1\)\]\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]=\\mathbb\{E\}\[\\max\(0,Z\_\{1\},\\dots,Z\_\{M\-1\}\)\]is the Theorem\-2 quantity withm=M−1m=M\-1, so by the computation in Appendix[C\.5](https://arxiv.org/html/2610.31948#A3.SS5)\(withm=M−1m=M\-1:𝔼⁡\[T\]=1/2\\mathbb\{E\}\[T\]=1/2,V=M/\(2​\(M−1\)\)V=M/\(2\(M\-1\)\)\),

𝔼​\[max\]2/V=14⋅2​\(M−1\)M=M−12​M\.\\mathbb\{E\}\[\\max\]^\{2\}/V=\\frac\{1\}\{4\}\\cdot\\frac\{2\(M\-1\)\}\{M\}=\\frac\{M\-1\}\{2M\}\.The bias\-transfer form𝔼⁡\[gI\]\\mathbb\{E\}\[g\_\{I\}\]needs a limiting construction, given below; the ratio𝔼⁡\[maxi⁡Zi\]/V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}itself does not\.

#### The Limiting Constructions for𝔼⁡\[gI\]\\mathbb\{E\}\[g\_\{I\}\]\.

The gaps must be placed just*below*the up\-values of the extremal law, not near zero\. Give the deterministic arm the top mean,g0=0g\_\{0\}=0, and armkkthe gapgk=uk−ε​ukg\_\{k\}=u\_\{k\}\-\\varepsilon u\_\{k\}withε∈\(0,1\)\\varepsilon\\in\(0,1\), whereuk=k/\(M−1\)u\_\{k\}=k/\(M\-1\)is its up\-value\. Armkkthen beats the floor exactly when it is up, sinceZk−gk=ε​uk\>0Z\_\{k\}\-g\_\{k\}=\\varepsilon u\_\{k\}\>0up and−1/\(M−1\)−gk<0\-1/\(M\-1\)\-g\_\{k\}<0down; and among the up arms the largestε​uk\\varepsilon u\_\{k\}wins, which is the same arm that attainsmax⁡\(0,Z1,…,ZM−1\)\\max\(0,Z\_\{1\},\\dots,Z\_\{M\-1\}\)\. Hence

𝔼⁡\[gI\]=\(1−ε\)​𝔼​\[max⁡\(0,Z1,…,ZM−1\)\]→ε→0\+𝔼⁡\[maxi⁡Zi\],\\mathbb\{E\}\[g\_\{I\}\]\\;=\\;\(1\-\\varepsilon\)\\,\\mathbb\{E\}\\bigl\[\\max\(0,Z\_\{1\},\\dots,Z\_\{M\-1\}\)\\bigr\]\\;\\xrightarrow\[\\varepsilon\\to 0^\{\+\}\]\{\}\\;\\mathbb\{E\}\\bigl\[\\max\_\{i\}Z\_\{i\}\\bigr\],withVVunchanged, since the means do not enter it\. The ratio𝔼⁡\[gI\]/V\\mathbb\{E\}\[g\_\{I\}\]/\\sqrt\{V\}therefore rises to the constant asε→0\+\\varepsilon\\to 0^\{\+\}, that is as every alternative’s deficit approaches the gain its own noise can supply and selection becomes a near\-tie\. The marginsε​uk\\varepsilon u\_\{k\}must keep the order of theuku\_\{k\}: with gaps just below theuku\_\{k\}but margins in another order the limit is smaller, for instance5/12<1/25/12<1/2atM=3M=3\.

AtM=2M=2this is the whole picture in closed form\. With the floorZ1=0Z\_\{1\}=0,Z2=±sZ\_\{2\}=\\pm sand gapggon the second arm, the second arm is selected exactly when it is up andg<sg<s, so

𝔼⁡\[gI\]V=g2​s\(g<s\),g4​s\(g=s\),0\(g\>s\)\.\\frac\{\\mathbb\{E\}\[g\_\{I\}\]\}\{\\sqrt\{V\}\}=\\frac\{g\}\{2s\}\\quad\(g<s\),\\qquad\\frac\{g\}\{4s\}\\quad\(g=s\),\\qquad 0\\quad\(g\>s\)\.The supremum1/21/2is approached asg→s−g\\to s^\{\-\}\. Atg→0g\\to 0the ratio goes to zero: a pool of equally good alternatives has no bias to transfer, because every selection is then correct\. Vanishing gaps are the wrong limit\.

#### The One\-Up Laws\.

The same mechanism carries the constants of Corollaries 1a and 1b over to the𝔼⁡\[gI\]\\mathbb\{E\}\[g\_\{I\}\]form, but the gaps must rise toM​dMd, the lead of an up arm over the optimal arm \(which is then down\), and not to the up\-value\(M−1\)​d\(M\-1\)d\. Give arm11the top mean and every other arm the gapgg\. WhenJ≠1J\\neq 1the up armJJbeats every other non\-optimal arm and beats arm11exactly wheng<M​dg<Md; whenJ=1J=1arm11wins; and the common shock of Corollary 1b shifts every score equally\. With ties broken uniformly, for both laws,

𝔼⁡\[gI\]=M−1M​g\(g<M​d\),M−12​M​g\(g=M​d\),0\(g\>M​d\),\\mathbb\{E\}\[g\_\{I\}\]=\\tfrac\{M\-1\}\{M\}\\,g\\quad\(g<Md\),\\qquad\\tfrac\{M\-1\}\{2M\}\\,g\\quad\(g=Md\),\\qquad 0\\quad\(g\>Md\),withVVunchanged\. Hence𝔼⁡\[gI\]→\(M−1\)​d=𝔼⁡\[maxi⁡Zi\]\\mathbb\{E\}\[g\_\{I\}\]\\to\(M\-1\)d=\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]asg→M​d−g\\to Md^\{\-\}, and𝔼⁡\[gI\]/V\\mathbb\{E\}\[g\_\{I\}\]/\\sqrt\{V\}rises to\(M−1\)/M\\sqrt\{\(M\-1\)/M\}and to\(M−1\)/M\(M\-1\)/Mrespectively; gaps at the up\-value\(M−1\)​d\(M\-1\)dgive only the fraction\(M−1\)/M\(M\-1\)/Mof each constant\.

#### Necessity of a Deterministic Arm atM=2M=2\(Proved\)\.

𝔼⁡\[max⁡\(Z1,Z2\)\]=𝔼​\|Z1−Z2\|/2≤v1\+v2/2\\mathbb\{E\}\[\\max\(Z\_\{1\},Z\_\{2\}\)\]=\\mathbb\{E\}\|Z\_\{1\}\-Z\_\{2\}\|/2\\leq\\sqrt\{v\_\{1\}\+v\_\{2\}\}/2, with equality iff\|Z1−Z2\|\|Z\_\{1\}\-Z\_\{2\}\|is a\.s\. constant; for independent arms this forces one arm deterministic \(Z1=0Z\_\{1\}=0a\.s\.,Z2=±sZ\_\{2\}=\\pm s\): the deterministic\-floor structure appears by itself\.

## Appendix EFormal Verification in Lean 4

The formalization, which will be released with the code, covers every theorem, corollary and lemma of the paper in Lean 4 with Mathlib \(toolchain and Mathlibv4\.34\.0\-rc1; 11 files, about 7,900 lines\)\. It contains nosorry, and every theorem depends only on Lean’s standard axiomspropext,Classical\.choiceandQuot\.sound\. It builds withlake build\.

#### What Is Formalized\.

Random\-variable statements are made on an arbitrary probability space\(Ω,P\)\(\\Omega,P\)forZ:Fin​M→Ω→ℝZ:\\mathrm\{Fin\}\\,M\\to\\Omega\\to\\mathbb\{R\}, with hypothesesMemLp \(Z i\) 2 P\(finite variance\),∫Zi​𝑑P=0\\int Z\_\{i\}\\,dP=0and, where the class requires it,iIndepFun Z P\(mutual independence\)\. The maximum is the pointwise supremumω↦supiZi​\(ω\)\\omega\\mapsto\\sup\_\{i\}Z\_\{i\}\(\\omega\)andVVis the sum of the Mathlib variances\. Sharpness is formalized as a greatest element: for Theorems 2 and 3 the statementIsGreatestasserts both that the constant bounds the ratio𝔼⁡\[maxi⁡Zi\]/V\\mathbb\{E\}\[\\max\_\{i\}Z\_\{i\}\]/\\sqrt\{V\}over all admissible laws and that some law attains it\.

#### Correspondence\.

Table[4](https://arxiv.org/html/2610.31948#A5.T4)lists the main Lean names; theREADMEof the released formalization gives the full list, including the paper\-specific algebra of Appendices[C](https://arxiv.org/html/2610.31948#A3)and[D](https://arxiv.org/html/2610.31948#A4)and the closed forms behind Tables[1](https://arxiv.org/html/2610.31948#S3.T1)and[2](https://arxiv.org/html/2610.31948#S3.T2)\.

Table 4:Paper results and the Lean theorems that verify them\.
#### Where the Formal Proofs Take Shorter Routes\.

Two steps of the independent case are formalized along routes different from, and shorter than, the ones written in this appendix\. The two\-point reduction of Appendix[D\.1](https://arxiv.org/html/2610.31948#A4.SS1)is proved without[Bayer and Teichmann \(2006\)](https://arxiv.org/html/2610.31948#bib.bib6): an elementary supporting\-line lemma \(a function bounded byBBon every mean\-zero two\-point law satisfiesφ⁡\(z\)≤B\+c​z\\varphi\(z\)\\leq B\+czfor somecc\) combined with Fubini’s theorem arm by arm\. The two\-point bound of Theorem 3 is proved by one induction that removes the arm with the largest up\-value and applies a two\-term Cauchy–Schwarz step, and the inequalityΦt≤Gt\\Phi\_\{t\}\\leq G\_\{t\}of Appendix[D\.4](https://arxiv.org/html/2610.31948#A4.SS4)follows, onceftf\_\{t\}is replaced by its closed\-form boundΨt\\Psi\_\{t\}, from the sum\-of\-squares certificate

2​t​\(t\+1\)​\(Gt−x⁡\(1−x\)​\(1−P\)2−\(1−x\)2​Ψt​\(P\)\)\\displaystyle 2t\(t\+1\)\\bigl\(G\_\{t\}\-x\(1\-x\)\(1\-P\)^\{2\}\-\(1\-x\)^\{2\}\\Psi\_\{t\}\(P\)\\bigr\)=\(t−\(t\+1\)​\(1−x\)​\(1−P\)\)2\+2​t​\(t\+1\)​x​P​\(1−x\)​\(1−P\),\\displaystyle=\\bigl\(t\-\(t\+1\)\(1\-x\)\(1\-P\)\\bigr\)^\{2\}\+2t\(t\+1\)\\,xP\(1\-x\)\(1\-P\),valid fort≥1t\\geq 1and nonnegative onx,P∈\[0,1\]x,P\\in\[0,1\]\. The route written here \(ellipsoid, maximum ofMMvalues, vertex analysis and factored cubic\) is formalized separately as well, so both proofs are checked\.