§2.2, (2.4), p. 3 — (1/N) log P(Z_N ≥ a) ≤ −I(a)
ProvedKleywegtSAA.ExpRate.ld_upper_boundcramer-chernofflarge-deviationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be independent, identically distributed real random variables on a probability space , distributed as , and let . Let and . Then for every and every real ,
with the convention .
This is the upper bound of Cramér's large-deviations theorem in non-asymptotic form; it holds without any moment assumption on .
Formalization Note The inequality is in the extended reals: of a probability is ENNReal.log, with , and may be (then and the claim is ). The sequence is -indexed: is the -st term and is the first term.
Preamble
import Mathlib import Definitions.Def_KleywegtSAA_ExpRate_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace KleywegtSAA.ExpRate
/-- The large-deviations upper bound (2.4), p. 3: for an i.i.d. real sequence with sample average
`Z_N`, every `N ≥ 1` and every real `a`, `(1/N) log P(Z_N ≥ a) ≤ −I(a)`, with `log 0 = −∞`. -/
theorem ld_upper_bound {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(Y : ℕ → Ω → ℝ) (hYm : ∀ i, Measurable (Y i)) (hind : iIndepFun Y P)
(hid : ∀ i, IdentDistrib (Y i) (Y 0) P P) :
∀ N : ℕ, 1 ≤ N → ∀ a : ℝ,
((1 / (N : ℝ) : ℝ) : EReal) * ENNReal.log (P {ω | a ≤ sampleMean Y N ω}) ≤
- rateFn P (Y 0) a := by sorry
end KleywegtSAA.ExpRate
Source
Kleywegt & Shapiro, The sample average approximation method for stochastic discrete optimization, preprint (two-author version, sha256 56657748…), p. 3, (2.4) and the definition of I(z) below it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.