Exponential tail from geometric binomial moments
ProvedRGMISFast.binomial_moment_exponential_tailprobabilityrandomized-greedy-mis
Let be a natural-valued random variable on a measure space, and let . Assume for every integer that is measurable and
Then for every real ,
This is the graph-independent moment-to-tail implication used for Equation (27). No probability-measure assumption is needed: the hypothesis on the positive-order binomial moments suffices. The source applies it with .
Preamble
import Mathlib import Definitions.Def_RGMISFast_Gamma import Definitions.Def_RGMISFast_condLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal open RGMISFast
Formal statement
theorem RGMISFast.binomial_moment_exponential_tail {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) (K : Ω → ℕ) (C : ℝ) (hC : 1 ≤ C)
(hmom : ∀ k : ℕ, 1 ≤ k →
Measurable (fun ω => (K ω).choose k) ∧
∫⁻ ω, ((K ω).choose k : ℝ≥0∞) ∂μ ≤ ENNReal.ofReal ((2*Real.exp 1*C)^k))
(x : ℝ) (hx : 1 ≤ x) :
μ {ω | 32*C*x < (K ω:ℝ)} ≤ ENNReal.ofReal (Real.exp (-x)) := by sorrySource
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, §6.1, Lemma 6.1 proof: Equations (24)–(25), printed p.23, and tail bounds paragraph proving Equation (27), printed p.24 (PDF pp.25–26).