Integrating a shifted exponential tail gives expectation at most twice the scale
ProvedRGMISFast.lintegral_le_two_scale_of_exp_tailLet X be a measurable natural-valued random variable on a probability space and let F>0. If for every h≥0,
then
This is the general tail-integration step in the proof of Theorem 1.1, stated independently of graphs. The expectation is represented by the nonnegative Lebesgue integral.
Preamble
import Mathlib open MeasureTheory open scoped ENNReal set_option autoImplicit false
Formal statement
theorem RGMISFast.lintegral_le_two_scale_of_exp_tail {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] (X : Ω → ℕ) (hX : Measurable X)
(F : ℝ) (hF : 0 < F)
(htail : ∀ h : ℝ, 0 ≤ h → μ {ω | F * (1 + h) < (X ω : ℝ)} ≤
ENNReal.ofReal (Real.exp (-h))) :
∫⁻ ω, (X ω : ℝ≥0∞) ∂μ ≤ ENNReal.ofReal (2 * F) := by sorrySource
Randomized Greedy MIS Is Fast at Every Node, proof of Theorem 1.1, p.17, displayed tail-integration formula. Generalization from the query counter to any measurable natural-valued random variable.