§8.3 — N₂ ≥ (1/ε) ln(1/β) makes the FAST bound (8.5) at most β
ProvedScenarioApproach.Fast.fast_bound_le_of_N2fast-algorithmp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1sample-complexityscenario-approach
Let and let be natural numbers. If
then the right-hand side of the FAST bound (8.5) is at most :
Combined with Theorem 8.5 this gives the sample-size rule of FAST: with first-stage scenarios and detuning scenarios, , so the total number of scenarios grows additively, , rather than multiplicatively in and .
Formalization Note The statement holds for every and ; the book's choice plays no role in the inequality. The exponent is natural-number subtraction, which only matters for , where .
Preamble
import Mathlib
Formal statement
namespace ScenarioApproach.Fast
/-- The `N₂` rule of FAST (p. 95): for `ε, β ∈ (0, 1)`, if `N₂ ≥ (1/ε) ln(1/β)` then the
right-hand side of (8.5) is at most `β`, whatever `N₁` and `d`:
`(1-ε)^{N₂} ∑_{i=0}^{d-1} (N₁ choose i) ε^i (1-ε)^{N₁-i} ≤ β`. -/
theorem fast_bound_le_of_N2 (d N₁ N₂ : ℕ) (ε β : ℝ)
(hε0 : 0 < ε) (hε1 : ε < 1) (hβ0 : 0 < β) (hβ1 : β < 1)
(hN₂ : (1 / ε) * Real.log (1 / β) ≤ N₂) :
(1 - ε) ^ N₂ *
∑ i ∈ Finset.range d, (N₁.choose i : ℝ) * ε ^ i * (1 - ε) ^ (N₁ - i) ≤ β := by sorry
end ScenarioApproach.Fast
Source
Campi & Garatti, Introduction to the Scenario Approach, SIAM/MOS 2018, DOI 10.1137/1.9781611975444, p. 95, §8.3 (Pros: Reduced sample size requirements)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.