BanditAlgorithm.subgaussian_sample_mean_tail_bound
Proved(Hoeffding-type bound, GOAL — L&S Corollary 5.5) Assume are independent, -subgaussian random variables for (with ), and let
be the sample mean. Then for any ,
(Here -subgaussian means Mathlib's HasSubgaussianMGF with variance proxy .)
import Mathlib.Probability.Moments.SubGaussian open MeasureTheory ProbabilityTheory Real NNReal
theorem BanditAlgorithm.subgaussian_sample_mean_tail_bound
{Ω : Type} {mΩ : MeasurableSpace Ω} {P : Measure Ω} [IsProbabilityMeasure P]
{n : ℕ} (hn : 0 < n) {X : Fin n → Ω → ℝ} {m : ℝ} {σ : ℝ≥0} (hσ : 0 < σ)
(h_indep : iIndepFun (fun i ω ↦ X i ω - m) P)
(h_subG : ∀ i, HasSubgaussianMGF (fun ω ↦ X i ω - m) (σ ^ 2) P)
{ε : ℝ} (hε : 0 ≤ ε) :
P.real {ω | m + ε ≤ (∑ i, X i ω) / n} ≤
exp (-((n : ℝ) * ε ^ 2) / (2 * (σ : ℝ) ^ 2)) ∧
P.real {ω | (∑ i, X i ω) / n ≤ m - ε} ≤
exp (-((n : ℝ) * ε ^ 2) / (2 * (σ : ℝ) ^ 2)) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setting. Ω is an arbitrary type carrying a σ-algebra and a measure P which is assumed to be a probability measure. n is a natural number with 0 < n. X is a family of n real-valued functions on Ω, indexed by i ∈ {0, …, n−1}. m is an arbitrary real number (it is not separately assumed to be the mean of any Xᵢ; it enters only through the two hypotheses below). σ is a nonnegative real number with 0 < σ, and ε is a real number with 0 ≤ ε (ε = 0 is allowed).
Hypotheses.
- Independence: the centered family of functions ω ↦ Xᵢ(ω) − m, for i ranging over the n indices, is a mutually independent family under P (independence of the whole family in the σ-algebra sense: the σ-algebras pulled back by these maps are mutually independent).
- Sub-Gaussian MGF: for every index i, the centered function ω ↦ Xᵢ(ω) − m has a sub-Gaussian moment generating function with variance proxy σ² under P; concretely this means: for every real t, the function ω ↦ exp(t·(Xᵢ(ω) − m)) is P-integrable, and E_P[exp(t·(Xᵢ − m))] ≤ exp(σ²·t²/2).
Claim. Write A(ω) = (∑ᵢ Xᵢ(ω))/n for the sample mean (n > 0, so no division by zero). The conclusion is the conjunction of two one-sided bounds, both with the same right-hand side:
- P{ω : m + ε ≤ A(ω)} ≤ exp(−(n·ε²)/(2·σ²)), and
- P{ω : A(ω) ≤ m − ε} ≤ exp(−(n·ε²)/(2·σ²)).
Here P{…} denotes the real-number value the measure assigns to the set.
Edge cases and conventions. Both events are defined with non-strict inequalities (≤), so e.g. the first event includes sample means exactly equal to m + ε. With ε = 0 the right-hand side is exp(0) = 1, and both bounds hold trivially. σ > 0 rules out a 0/0 in the exponent. No measurability hypothesis on the Xᵢ is stated separately (measurability enters only implicitly through the integrability in the sub-Gaussian hypothesis); the measure of a possibly non-measurable set is its outer-measure value.
Confirmed by the mission captain (proposal self-audit).