Proposition 1, p. 14 — ∫₀¹ λφ ≥ λ(z*)∫₀¹ φ for λ ≥ 0 non-increasing and φ changing sign once at z*
ProvedOfflineStochMatch.Attenuation.proposition_1integral-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
Let be integrable, with and non-increasing. Suppose there is such that for all and for all . Then
In the paper this elementary bound drives the exchange argument (Lemma 6) for the case of patience .
Formalization Note Integrability is interval integrability on with respect to Lebesgue measure; the monotonicity, sign and nonnegativity conditions are imposed on only. Under these hypotheses is integrable on ( is bounded by there and monotone), so neither integral takes a default value.
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_Attenuation_Setting
Formal statement
namespace OfflineStochMatch.Attenuation
theorem proposition_1 (lam φ : ℝ → ℝ)
(hlam : IntervalIntegrable lam MeasureTheory.volume 0 1)
(hφ : IntervalIntegrable φ MeasureTheory.volume 0 1)
(hlam_nonneg : ∀ z ∈ Set.Icc (0 : ℝ) 1, 0 ≤ lam z)
(hlam_anti : AntitoneOn lam (Set.Icc (0 : ℝ) 1))
(zs : ℝ) (hzs : zs ∈ Set.Icc (0 : ℝ) 1)
(hφ_pos : ∀ z ∈ Set.Icc (0 : ℝ) zs, 0 ≤ φ z)
(hφ_neg : ∀ z ∈ Set.Icc zs 1, φ z ≤ 0) :
lam zs * ∫ z in (0 : ℝ)..1, φ z ≤ ∫ z in (0 : ℝ)..1, lam z * φ z := by sorry
end OfflineStochMatch.Attenuation
Source
Brubach, Grammel, Ma, MacRury, Srinivasan, Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes, arXiv:2106.06892v3, p. 14, Proposition 1 (Proposition 11 of reference [33])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.