ProbabilityTheory.HasBernsteinMGF.measure_le_le
theoremverifiedimported Lean
Lower-tail Bernstein bound. Let $X : \Omega \to \bbr$ be a random variable on a probability space carrying a finite measure $\mu$, and suppose $X$ satisfies the Bernstein moment generating function condition with parameters $c$ and $t_{\max}$: for every $t$ with $|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 X(\omega) \le -s\}\bigr) \;\le\; \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_le_le {μ : Measure Ω} [IsFiniteMeasure μ] (h : HasBernsteinMGF X μ c tmax) (hc : 0 < c) (s : ℝ) (hs_pos : 0 ≤ s) (hs_le : s ≤ 2 * c * tmax) : (μ {ω | X ω ≤ -s}).toReal ≤ Real.exp (-s ^ 2 / (4 * c))
- Source
- TCSlib, `ProbabilityTheory.HasBernsteinMGF.measure_le_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_le_le← ProbabilityTheory.HasBernsteinMGF.measure_le_le (TCSlib/LearningTheory/JohnsonLindenstrauss/Bernstein.lean:173): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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
- ProbabilityTheory.HasBernsteinMGF.measure_abs_gt_leTwo-sided Bernstein tail bound. Let $X : \Omega \to \bbr$ be a random variable on a probability space $(\Omega, \mu)$, 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/-- **Lower-tail Bernstein bound** by symmetry. If `X` has a Bernstein-type MGF with parameters `(c, tmax)` under a finite measure `μ`, `c > 0`, and `0 ≤ s ≤ 2c·tmax`, then the measure of the event `{X ≤ −s}` is at most `exp(−s²/(4c))`. This is the Chernoff step of [Ver18, proof of Thm 2.8.1] applied to `−X`; the same single-parameter deviation as in `measure_ge_le` applies. **Proof sketch.** Step 1: take `t = −s/(2c)`; the hypotheses give `−tmax ≤ t ≤ 0`, so the MGF bound applies at `t`. Step 2 (Chernoff, lower tail): the measure of `{X ≤ −s}` is at most `exp(−t·(−s))` times the MGF of `X` at `t` (Mathlib's `measure_le_le_exp_mul_mgf`), which is at most `exp(−t·(−s) + c·t²)`. Step 3: at this `t` the exponent equals `−s²/(4c)` exactly. -/lemma ProbabilityTheory.HasBernsteinMGF.measure_le_le {μ : Measure Ω} [IsFiniteMeasure μ] (h : HasBernsteinMGF X μ c tmax) (hc : 0 < c) (s : ℝ) (hs_pos : 0 ≤ s) (hs_le : s ≤ 2 * c * tmax) : (μ {ω | X ω ≤ -s}).toReal ≤ Real.exp (-s ^ 2 / (4 * c)) := by -- Step 1: use t = -s/(2c), which lies in `[-tmax, 0]`. set t : ℝ := -(s / (2 * c)) with ht_def have h2c_pos : 0 < 2 * c := by linarith have ht_neg : t ≤ 0 := by rw [ht_def]; linarith [div_nonneg hs_pos h2c_pos.le] have ht_le_tmax : -t ≤ tmax := by rw [ht_def]; simp only [neg_neg]; rw [div_le_iff₀ h2c_pos]; linarith have ht_abs : |t| ≤ tmax := by rw [abs_of_nonpos ht_neg]; exact ht_le_tmax -- Step 2: Chernoff (lower tail) via `measure_le_le_exp_mul_mgf`. have h_chernoff : (μ {ω | X ω ≤ -s}).toReal ≤ Real.exp (-t * (-s)) * mgf X μ t := measure_le_le_exp_mul_mgf (-s) ht_neg (h.integrable t ht_abs) refine le_trans h_chernoff ?_ refine le_trans (mul_le_mul_of_nonneg_left (h.mgf_le t ht_abs) (Real.exp_pos _).le) ?_ rw [← Real.exp_add] apply Real.exp_le_exp.mpr -- Step 3: at the optimal `t = -s/(2c)` the exponent is exactly `-s²/(4c)`. have h_exponent : -t * (-s) + c * t ^ 2 = -s ^ 2 / (4 * c) := by rw [ht_def] field_simp ring exact h_exponent.le