Theorem 4.3 — Bernstein's inequality for martingales (Freedman)
ProvedBestBothWorlds.SAO.freedmanconcentrationmartingalesp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be a probability space with filtration , and let . For , suppose is -measurable, has conditional mean zero given , and satisfies almost surely, where . Write . For every and variance level ,
Formalization Note The almost-sure bound suffices for the probability inequality and implies integrability. The page does not explicitly restrict ; the Lean statement quantifies over every real .
Preamble
import Mathlib open MeasureTheory
Formal statement
namespace BestBothWorlds.SAO
/-- Theorem 4.3, equation (19) (p. 14): Freedman's Bernstein inequality with the paper's
two-sided bound `|X_t| ≤ b` and predictable variation `V_n`. -/
theorem freedman {Ω : Type*} {mΩ : MeasurableSpace Ω} (P : Measure Ω)
[IsProbabilityMeasure P] (ℱ : Filtration ℕ mΩ) (X : ℕ → Ω → ℝ) (n : ℕ) (hn : 1 ≤ n)
(b : ℝ) (hb : 0 < b)
(hmeas : ∀ t ∈ Finset.Icc 1 n, Measurable[ℱ t] (X t))
(hmds : ∀ t ∈ Finset.Icc 1 n, P[X t | ℱ (t - 1)] =ᵐ[P] 0)
(hbd : ∀ t ∈ Finset.Icc 1 n, ∀ᵐ ω ∂P, |X t ω| ≤ b)
(ε V : ℝ) (hε : 0 < ε) :
P.real {ω | ε ≤ ∑ t ∈ Finset.Icc 1 n, X t ω ∧
∑ t ∈ Finset.Icc 1 n, P[fun ω' => X t ω' ^ 2 | ℱ (t - 1)] ω ≤ V} ≤
Real.exp (-ε ^ 2 / (2 * V + 2 * b * ε / 3)) := by sorry
end BestBothWorlds.SAO
Source
Bubeck & Slivkins, The best of both worlds: stochastic and adversarial bandits, arXiv:1202.4473v1, p. 14, Theorem 4.3, eq. (19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.