Lemma 4.3 — A logarithmic-power quantile guarantee implies the full expectation bound E[X] ≤ 4(2t)^t.
OpenGreedyColoringLCA969.LowerBound.Supplement.lemma_4_3graph-theorylocal-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any probability space, let be a measurable nonnegative random variable, and let be an integer. Suppose for every ,
Then its nonnegative extended expectation satisfies
The conclusion includes finiteness of the expectation; integrability is not assumed. This is the quantitative conversion needed for the finite-label upper bound.
Differences from the source:
- encoding: a nonnegative random variable and its expectation → a measurable nonnegative real-valued X on a probability space and its nonnegative extended integral; reason: measurability is part of being a random variable, and no integrability premise is added
Preamble
import Definitions.Def_GreedyColoringLCA969_LowerBound_GraphBasics open scoped ENNReal BigOperators open MeasureTheory Classical set_option autoImplicit false
Formal statement
namespace GreedyColoringLCA969.LowerBound.Supplement
theorem lemma_4_3 {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (X : Ω → ℝ) (hX : Measurable X)
(hnonneg : ∀ ω, 0 ≤ X ω) (t : ℕ) (ht : 1 ≤ t)
(htail : ∀ ε : ℝ, 0 < ε → ε ≤ 1 / 2 →
ENNReal.ofReal (1 - ε) ≤ μ {ω | X ω ≤ (log2 (1 / ε))^t}) :
(∫⁻ ω, ENNReal.ofReal (X ω) ∂μ) ≤ ENNReal.ofReal (4 * (2 * (t : ℝ))^t) := by sorry
end GreedyColoringLCA969.LowerBound.Supplement
Source
Zi Song Yeoh, Krzysztof Onak, Dragos-Florian Ristache, STOC 2027 submission #969 (October 2026), p. 15 (PDF 16), Lemma 4.3; proof pp.37–38 (PDF 38–39), Appendix B.1