Lemma 4.2 — the positive-part bound
ProvedStochMatchPoly.lemma_4_2matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandom-subgraphsparsificationstochastic-matching
- For and ,
- Consequently, if is a real random variable with finite variance and , then
The second form bounds the expected overload of a vertex in the main proof.
Differences from the source:
- encoding: W has finite variance → MemLp W 2 P on a probability space (Ω, P); reason: finite variance is square integrability, which also gives integrability of W and (W − c)₊
Preamble
import Mathlib open MeasureTheory ProbabilityTheory universe u
Formal statement
namespace StochMatchPoly
/-- S. Behnezhad, *Stochastic Matching with Polynomial Degree*, arXiv:2611.03367 (held version,
sha256 409beb43…), Lemma 4.2 (A positive-part bound), p.10 (PDF p.11).
"For b > 0 and r ∈ ℝ, (r − b)₊ ≤ r²/(4b), (r)₊ := max{r, 0}. Consequently, if W has finite
variance and c > E W, then E(W − c)₊ ≤ Var(W)/(4(c − E W))."
**Formalization Note.** The second part is stated for a real random variable `W` on an arbitrary
probability space; "finite variance" is `MemLp W 2 P` (square integrable, which also makes `W`
and `(W − c)₊` integrable), `E W` is the Bochner integral and `Var(W)` is Mathlib's `variance`. -/
theorem lemma_4_2 :
(∀ b r : ℝ, 0 < b → max (r - b) 0 ≤ r ^ 2 / (4 * b)) ∧
∀ (Ω : Type u) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (W : Ω → ℝ)
(c : ℝ), MemLp W 2 P → ∫ ω, W ω ∂P < c →
∫ ω, max (W ω - c) 0 ∂P ≤ variance W P / (4 * (c - ∫ ω, W ω ∂P)) := by sorry
end StochMatchPoly
Source
S. Behnezhad, Stochastic Matching with Polynomial Degree, arXiv:2611.03367 (preprint, held version, sha256 409beb43bd8ab862a4a4a595be9c08afd92590790382102cb640d81d9b564017), Lemma 4.2, p.10 (PDF p.11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.