Union bound for the maximum of sub-Gaussian variables
Provedmax_subgaussian_deviation_union_boundRole. Finite empirical-process supremum concentration via the union bound — the standard first step in controlling over a finite index set or a finite net, and a reusable building block toward the empirical-process supremum (Talagrand) concentration of exact matrix completion.
Claim (maximal sub-Gaussian deviation). Let be a finite family of real random variables on a probability space, each sub-Gaussian with parameter (HasSubgaussianMGF (X i) (c i)). Then for every ,
Equivalently, , and with a uniform parameter this is .
Proof. The event equals the finite union . By the union bound measureReal_biUnion_finset_le, its probability is at most , and each term is bounded by via the two-sided sub-Gaussian tail (one-sided Chernoff HasSubgaussianMGF.measure_ge_le applied to and , combined with measureReal_union_le).
Source. Standard maximal-inequality union bound for sub-Gaussian variables. R. Vershynin, High-Dimensional Probability, CUP 2018, §2.5 (maximum of sub-Gaussians); S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities, OUP 2013, §2.5 (the maximal inequality). Derived from Mathlib's HasSubgaussianMGF.measure_ge_le and measureReal_biUnion_finset_le.
import Mathlib.Probability.Moments.SubGaussian import Mathlib.MeasureTheory.Measure.Real open MeasureTheory ProbabilityTheory Real open scoped NNReal ENNReal
theorem max_subgaussian_deviation_union_bound
{Ω : Type*} {mΩ : MeasurableSpace Ω} {μ : Measure Ω} [IsProbabilityMeasure μ]
{ι : Type*} {X : ι → Ω → ℝ} {c : ι → ℝ≥0} {s : Finset ι}
(h_subG : ∀ i ∈ s, HasSubgaussianMGF (X i) (c i) μ) {ε : ℝ} (hε : 0 ≤ ε) :
μ.real {ω | ∃ i ∈ s, ε ≤ |X i ω|}
≤ ∑ i ∈ s, 2 * Real.exp (-ε ^ 2 / (2 * c i)) := by sorry