centered_sampling_chernoff_exponential_tail
Provedchernoffconcentrationmatrix-completionmgf
Cramér–Chernoff exponential (MGF) tail bound on the bespoke finite Bernoulli observation measure. For inclusion probability , any scalar statistic of the observation set, any threshold , and any ,
where is and is . This is Markov's inequality applied to the increasing transform : pointwise , summed against the nonnegative observation weights . It is the canonical 'MGF tail' (Chernoff) half of the Cramér–Chernoff method, valid on this bespoke powerset-Bernoulli measure with no Mathlib MeasureTheory dependency. Paired with the exact MGF factorization centered_sampling_coefficient_mgf_factorization (and any sub-Gaussian MGF bound) it yields exponential concentration for the centered sampling coefficient.
Preamble
import Definitions.Def_matrix_completion_neumann import Mathlib.Analysis.SpecialFunctions.Exp open MatrixCompletion open scoped BigOperators Classical
Formal statement
theorem centered_sampling_chernoff_exponential_tail
{n₁ n₂ : ℕ} (p : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1)
(Z : Finset (Fin n₁ × Fin n₂) → ℝ) (t lam : ℝ) (hlam : 0 < lam) :
bernoulliEventProb p (fun Omega => t ≤ Z Omega) ≤
Real.exp (-(lam * t)) *
bernoulliExpectation p (fun Omega => Real.exp (lam * Z Omega)) := by
sorrySource
Boucheron-Lugosi-Massart, Concentration Inequalities, OUP 2013, Ch. 2 'The Cramer-Chernoff method' (generic Chernoff bound P(Z>=t) <= e^{-lambda t} E[e^{lambda Z}]); applied to the centered sampling coefficient of Candes-Recht 2009, arXiv:0805.4471, Section 6.