Lemma 5.10 — an exponential variable on an event of probability :
ProvedNonMarkovColorings.Main.lemma_5_10exponential-distributionp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be an exponential random variable with mean and let be an event of probability . Then
It converts high-probability bounds into expectation bounds in §5.2.
Formalization Note. is measurable with law expMeasure (1/μ) (rate ); is a measurable set and P.real A; at both sides are under Lean's conventions ().
Differences from the source:
- encoding: exponential random variable with mean μ, event A → Measurable X, P.map X = expMeasure (1/μ), MeasurableSet A; E[X1{A}] = ∫ A.indicator X ∂P; reason: the law fixes integrability of X, so the Bochner integral is the expectation
Preamble
import Mathlib
Formal statement
namespace NonMarkovColorings.Main
/-- Lemma 5.10 ([HV03, Observation 21]). If `X` is an exponential random variable with mean
`μ` and `A` is an event of probability `p`, then `E[X 1{A}] ≤ p (μ log(e/p) + 1)`. -/
theorem lemma_5_10 {Ω : Type*} [MeasurableSpace Ω] (P : MeasureTheory.Measure Ω)
[MeasureTheory.IsProbabilityMeasure P] (μ : ℝ) (hμ : 0 < μ) (X : Ω → ℝ)
(hX : Measurable X) (hlaw : P.map X = ProbabilityTheory.expMeasure (1 / μ))
(A : Set Ω) (hA : MeasurableSet A) :
∫ ω, A.indicator X ω ∂P ≤
P.real A * (μ * Real.log (Real.exp 1 / P.real A) + 1) := by sorry
end NonMarkovColorings.Main
Source
Jain, Mizgerd, Vigoda, Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity, arXiv:2604.11938 (PDF of 2026-11-03, sha256 f3bf0cf0…), p. 36, Lemma 5.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.