ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_le
theoremverifiedimported Lean
Two-sided Bernstein tail bound. Let $X : \Omega \to \bbr$ be a random variable on a probability space $(\Omega, \mu)$, and let $c, t_{\max} \ge 0$ be real parameters such that $X$ satisfies the Bernstein moment generating function condition with parameters $c$ and $t_{\max}$: for every $t$ with $\abs{t} \le t_{\max}$ the exponential moment $e^{tX}$ is $\mu$-integrable and $\E_\mu[e^{tX}] \le e^{c t^2}$. If $c > 0$, then for every $s$ with $0 \le s \le 2 c\, t_{\max}$, \[ \mu\bigl(\{\omega \mid s < \abs{X(\omega)}\}\bigr) \;\le\; 2\exp\!\Bigl(-\frac{s^2}{4c}\Bigr). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real in variable {Ω : Type*} {mΩ : MeasurableSpace Ω} in variable {X : Ω → ℝ} {μ : Measure Ω} {c tmax : ℝ} in lemma ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_le {μ : Measure Ω} [IsProbabilityMeasure μ] (h : HasBernsteinMGF X μ c tmax) (hc : 0 < c) (s : ℝ) (hs_pos : 0 ≤ s) (hs_le : s ≤ 2 * c * tmax) : (μ {ω | s < |X ω|}).toReal ≤ 2 * Real.exp (-s ^ 2 / (4 * c))
- Source
- TCSlib, `ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_le`
- Lean proof
- By Ganesh Sankar, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Ganesh Sankar. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_le← ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_le (TCSlib/LearningTheory/JohnsonLindenstrauss/Bernstein.lean:209): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- ProbabilityTheory.HasBernsteinMGF.measure_le_leLower-tail Bernstein bound. Let $X : \Omega \to \bbr$ be a random variable on a probability space carrying a finite measure $\mu$, and…
- ProbabilityTheory.HasBernsteinMGF.measure_ge_leUpper-tail Bernstein bound. Let $X : \Omega \to \bbr$ be a random variable on a finite measure space $(\Omega, \mu)$, and suppose $X$…
- ProbabilityTheory.HasBernsteinMGF$\texttt{ProbabilityTheory.HasBernsteinMGF}\ X\ \mu\ c\ t_{\max}$ is a predicate on a random variable $X : \Omega \to \mathbb{R}$, a…
- Used by 1
- chi_squared_tailChi-squared tail bound for independent $N(0,1/k)$ variables. Let $\mu$ be a probability measure on $\Omega$, let $k \ge 1$, and let…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory ProbabilityTheory Real invariable {Ω : Type*} {mΩ : MeasurableSpace Ω} invariable {X : Ω → ℝ} {μ : Measure Ω} {c tmax : ℝ} in/-- **Two-sided Bernstein bound.** If `X` has a Bernstein-type MGF with parameters `(c, tmax)` under a probability measure `μ`, `c > 0`, and `0 ≤ s ≤ 2c·tmax`, then the probability of the event `{s < |X|}` is at most `2·exp(−s²/(4c))`. This is the two-sided form of the Chernoff step in [Ver18, proof of Thm 2.8.1], with the same single-parameter deviation as `measure_ge_le`. **Proof sketch.** Step 1: the event `{s < |X|}` is contained in the union of the two one-sided events `{s ≤ X}` and `{X ≤ −s}`. Step 2: by monotonicity and the union bound its probability is at most the sum of the two one-sided probabilities, each of which is at most `exp(−s²/(4c))` by `measure_ge_le` and `measure_le_le`. -/lemma ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_le {μ : Measure Ω} [IsProbabilityMeasure μ] (h : HasBernsteinMGF X μ c tmax) (hc : 0 < c) (s : ℝ) (hs_pos : 0 ≤ s) (hs_le : s ≤ 2 * c * tmax) : (μ {ω | s < |X ω|}).toReal ≤ 2 * Real.exp (-s ^ 2 / (4 * c)) := by -- Step 1: bad event ⊆ {s ≤ X} ∪ {X ≤ -s}. have hsubset : {ω | s < |X ω|} ⊆ {ω | s ≤ X ω} ∪ {ω | X ω ≤ -s} := by intro ω hω rw [Set.mem_setOf_eq] at hω rw [Set.mem_union, Set.mem_setOf_eq, Set.mem_setOf_eq] by_contra h_neither rw [not_or] at h_neither obtain ⟨h1, h2⟩ := h_neither have hXlt : X ω < s := lt_of_not_ge h1 have hXgt : -s < X ω := lt_of_not_ge h2 have habs_lt : |X ω| < s := abs_lt.mpr ⟨hXgt, hXlt⟩ exact (lt_irrefl s) (lt_of_lt_of_le hω habs_lt.le) -- Step 2: apply union + the two single-tail bounds. calc (μ {ω | s < |X ω|}).toReal ≤ (μ ({ω | s ≤ X ω} ∪ {ω | X ω ≤ -s})).toReal := ENNReal.toReal_mono (measure_ne_top _ _) (measure_mono hsubset) _ ≤ (μ {ω | s ≤ X ω}).toReal + (μ {ω | X ω ≤ -s}).toReal := by rw [← ENNReal.toReal_add (measure_ne_top _ _) (measure_ne_top _ _)] exact ENNReal.toReal_mono (ENNReal.add_ne_top.mpr ⟨measure_ne_top _ _, measure_ne_top _ _⟩) (measure_union_le _ _) _ ≤ Real.exp (-s ^ 2 / (4 * c)) + Real.exp (-s ^ 2 / (4 * c)) := by gcongr · exact h.measure_ge_le hc s hs_pos hs_le · exact h.measure_le_le hc s hs_pos hs_le _ = 2 * Real.exp (-s ^ 2 / (4 * c)) := by ring