Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (5.2) — for fully supported problems Theorem 3.7 holds with equality

Proved
ScenarioApproach.Generalization.violation_tail_eq_binomial_sum_of_fullySupported

by mikedeng1 · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

beta-distributionp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1scenario-approachsupport-constraints

Consider the convex scenario program with ddd decision variables: cost cTθc^T\thetacTθ, domain Θ⊆Rd\Theta\subseteq\mathbb R^dΘ⊆Rd, constraint sets Θδ\Theta_\deltaΘδ​, δ∈Δ\delta\in\Deltaδ∈Δ, and a probability P\mathbb PP on Δ\DeltaΔ. Assume

  1. (Assumption 3.4) Θ\ThetaΘ and every Θδ\Theta_\deltaΘδ​ are convex and closed;
  2. (Assumption 3.6) for every mmm and every sample (δ1,…,δm)(\delta_1,\dots,\delta_m)(δ1​,…,δm​) the program with these mmm constraints has a unique solution;
  3. the problem is fully supported (Definition 5.4): for every m≥dm\ge dm≥d, with probability 1 the program with mmm i.i.d. constraints has exactly ddd support constraints.

Let 1≤d≤N1\le d\le N1≤d≤N, let θ∗\theta^*θ∗ be the solution of the program with NNN i.i.d. constraints δ1,…,δN∼P\delta_1,\dots,\delta_N\sim\mathbb Pδ1​,…,δN​∼P, and V(θ∗)V(\theta^*)V(θ∗) its violation. Then for every ε∈[0,1]\varepsilon\in[0,1]ε∈[0,1]

PN{V(θ∗)>ε}=∑i=0d−1(Ni)εi(1−ε)N−i.\mathbb P^N\{V(\theta^*)>\varepsilon\}=\sum_{i=0}^{d-1}\binom{N}{i}\varepsilon^i(1-\varepsilon)^{N-i}.PN{V(θ∗)>ε}=i=0∑d−1​(iN​)εi(1−ε)N−i.

So the bound of Theorem 3.7 is attained exactly by fully supported problems: V(θ∗)V(\theta^*)V(θ∗) then has the Beta(d,N−d+1)(d,N-d+1)(d,N−d+1) distribution, whatever P\mathbb PP is.

Formalization Note The book writes the display (5.2) for d=2d=2d=2 and states in words that the result of Theorem 3.7 holds with equality for fully supported problems; the general-ddd equality is stated here. The solution is a map θstar : (Fin N → Δ) → EuclideanSpace ℝ (Fin d) with θstar ω the solution for every sample. Measurability, glossed over in the book (p. 33), is assumed as joint measurability of {(θ,δ):θ∈Θδ}\{(\theta,\delta):\theta\in\Theta_\delta\}{(θ,δ):θ∈Θδ​} and measurability of θstar. The probability is compared in [0,∞][0,\infty][0,∞] via ENNReal.ofReal.

Preamble
import Mathlib
import Definitions.Def_ScenarioApproach_Generalization_violation
import Definitions.Def_ScenarioApproach_Generalization_scenarioProgram
import Definitions.Def_ScenarioApproach_Generalization_supportConstraint
Formal statement
namespace ScenarioApproach.Generalization

/-- Eq. (5.2) and the sentence before §5.2 (p. 58): for fully supported problems the bound of
Theorem 3.7 holds with equality. -/
theorem violation_tail_eq_binomial_sum_of_fullySupported
    {d N : ℕ} {Δ : Type*} [MeasurableSpace Δ]
    (P : MeasureTheory.Measure Δ) [MeasureTheory.IsProbabilityMeasure P]
    (c : EuclideanSpace ℝ (Fin d)) (Θ : Set (EuclideanSpace ℝ (Fin d)))
    (Θδ : Δ → Set (EuclideanSpace ℝ (Fin d)))
    -- Assumption 3.4 (convexity): `Θ` and every `Θ_δ` are convex and closed
    (hΘ_convex : Convex ℝ Θ) (hΘ_closed : IsClosed Θ)
    (hΘδ_convex : ∀ δ, Convex ℝ (Θδ δ)) (hΘδ_closed : ∀ δ, IsClosed (Θδ δ))
    -- Assumption 3.6 (existence and uniqueness), for every `m` and every sample
    (hexu : ∀ (m : ℕ) (ω : Fin m → Δ), ∃! θ, IsSolution c Θ Θδ ω θ)
    -- measurability, glossed over on p. 33: the constraint relation is jointly measurable
    (hmeas : MeasurableSet {p : EuclideanSpace ℝ (Fin d) × Δ | p.1 ∈ Θδ p.2})
    -- `θstar ω` is the solution of the scenario program with the `N` sampled constraints `ω`
    (θstar : (Fin N → Δ) → EuclideanSpace ℝ (Fin d))
    (hθstar : ∀ ω, IsSolution c Θ Θδ ω (θstar ω)) (hθstar_meas : Measurable θstar)
    (hfs : FullySupported c Θ Θδ P)
    (hd : 1 ≤ d) (hN : d ≤ N) (ε : ℝ) (hε0 : 0 ≤ ε) (hε1 : ε ≤ 1) :
    MeasureTheory.Measure.pi (fun _ : Fin N => P) {ω | ε < violation P Θδ (θstar ω)} =
      ENNReal.ofReal
        (∑ i ∈ Finset.range d, (N.choose i : ℝ) * ε ^ i * (1 - ε) ^ (N - i)) := by sorry

end ScenarioApproach.Generalization
Source
Campi & Garatti, Introduction to the Scenario Approach, SIAM/MOS 2018, DOI 10.1137/1.9781611975444, p. 58, text after Definition 5.4 and Eq. (5.2)
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me