Eqs. (3.15)–(3.16) — exponential bound on
ProvedScenarioApproach.Removal.binomial_sum_le_expbinomial-tailp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1scenario-approach
Let , and be natural numbers, let , and let . Then
(the last line of (3.15)), and
These bounds turn the binomial tail in (3.13) into an explicit exponential, from which the violation level of Theorem 1.2 is solved for.
Formalization Note The book applies the chain to the specific of (1.9); the inequalities hold for every , and that range is stated as a hypothesis (for the factors change sign and the chain breaks). The exponent is a natural number, exact because ; terms with vanish since .
Preamble
import Mathlib
Formal statement
namespace ScenarioApproach.Removal
theorem binomial_sum_le_exp (N k d : ℕ) (hk : 1 ≤ k) (hd : 1 ≤ d)
(a : ℝ) (ha : a = 1 + 1 / Real.sqrt k)
(εk : ℝ) (hε0 : 0 ≤ εk) (hε1 : εk ≤ 1) :
(∑ i ∈ Finset.range (k + d), (N.choose i : ℝ) * εk ^ i * (1 - εk) ^ (N - i) ≤
a ^ (k + d - 1) * (1 - (1 - 1 / a) * εk) ^ N) ∧
(∑ i ∈ Finset.range (k + d), (N.choose i : ℝ) * εk ^ i * (1 - εk) ^ (N - i) ≤
Real.exp (-(1 - a) * ((k + d - 1 : ℕ) : ℝ)) * Real.exp (-(1 - 1 / a) * εk * N)) := by sorry
end ScenarioApproach.Removal
Source
Campi & Garatti, Introduction to the Scenario Approach, SIAM/MOS 2018, DOI 10.1137/1.9781611975444, p. 47, Eqs. (3.15)–(3.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.