Theorem 3 — is optimal for (20) iff global balance, pairwise balance and zero sampling ratio hold
ProvedMPBSelect.theorem_3Consider solutions and parameters with probabilities , ; conditional means that are pairwise distinct at each (assumption (i)), with conditional optima ; a unique most probable best (assumption (ii)); and standard deviations . Let , the balance weights (17) and the pairwise rates. Consider the relaxed OCBA problem
Then a feasible is optimal for (20) if and only if it satisfies all three of the following.
- Global balance. For all ,
- Pairwise balance. For all ,
- Zero asymptotic sampling ratio. for all .
The conditions characterize the asymptotically optimal static budget allocation for selecting the most probable best under the relaxed rate (20); the paper's sequential sampling algorithms are designed so that their sampling ratios converge to a solution of this system. The third condition contrasts with classical ranking and selection, where every optimal sampling ratio is positive.
Differences from the source:
- reading: "Any α" → every in the feasible set of (20); reason: optimality presupposes feasibility, and the three conditions are invariant under scaling, so for infeasible the "if" direction would fail.
- reading: standing hypotheses , , (standard deviation) → fields of the problem; reason: for , is empty and (20) has no objective; is the support of and (17) divides by ; Model (4) has variance and the formulas divide by it.
- encoding: solutions, parameters and →
Fin k,Fin B,Fin k → Fin B → ℝ, with , as fields characterized by their defining properties, and the minimum over asFinset.inf'; reason: Lean convention; same instances.
import Mathlib import Definitions.Def_MPBSelect_Problem import Definitions.Def_MPBSelect_feasibleSet import Definitions.Def_MPBSelect_Problem_IsOptimal import Definitions.Def_MPBSelect_Problem_GlobalBalance import Definitions.Def_MPBSelect_Problem_PairwiseBalance import Definitions.Def_MPBSelect_Problem_ZeroRatio
namespace MPBSelect
/-- **Theorem 3 (Optimality conditions for (20)).**
Kim, Kim, Song, *Selection of the Most Probable Best*, arXiv:2207.07533v2, Theorem 3, p.17:
"Any α is optimal for (20), if and only if, α satisfies the following system of equations:
• (Global balance condition) For all 1 ≤ b ≤ B, α²_{i^b}(θb)/λ²_{i^b}(θb) =
Σ_{i≠i^b,i∗} α²_i(θb)/λ²_i(θb).
• (Pairwise balance condition) For all (i,θb),(j,θb′) ∈ Ξ, {Wi(θb)} given in (17) satisfies
Wi(θb)Gi(θb) = Wj(θb′)Gj(θb′). (21)
• (Zero asymptotic sampling ratio) αi∗(θb) = 0 for all θb ∈ Θc_{i∗}."
For every MPB problem `P` (`k ≥ 2` solutions, `B` parameters with positive probabilities,
assumptions (i)–(ii) of p.7, positive standard deviations) and every allocation `α` in the
feasible set of (20): `α` is optimal for (20) iff it satisfies global balance at every
`θ_b`, pairwise balance (21) at every two pairs of `Ξ`, and the zero sampling ratio at every
`θ_b ∈ Θ^c_{i*}`.
**Formalization Note** `α` ranges over the simplex `Σ_i Σ_b α_i(θ_b) = 1, α ≥ 0` of (20):
optimality presupposes feasibility, and the three conditions are invariant under scaling. -/
theorem theorem_3 {k B : ℕ} (P : Problem k B) (α : Fin k → Fin B → ℝ)
(hα : α ∈ feasibleSet k B) :
P.IsOptimal α ↔ P.GlobalBalance α ∧ P.PairwiseBalance α ∧ P.ZeroRatio α := by sorry
end MPBSelect
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.