Eq. (29), p. 18 — F(i) ≥ 1 − e^{−F*(i)} ≥ (1 − 1/e)F*(i) when z_j ∈ [0,1] and Σ_{j≤k} z_j ≤ 1
ProvedOfflineStochMatch.UnitPatience.eq_29am-gmexponential-boundinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with , and for put and . Then
The first inequality is the bound , which the page derives from the inequality of arithmetic and geometric means; the second uses . Together with (27) and (28) it gives Lemma 8.
Formalization Note The two inequalities are stated as a conjunction; is written . The sequence is indexed by and only the indices are constrained.
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_UnitPatience_Setting
Formal statement
namespace OfflineStochMatch.UnitPatience
open Finset
theorem eq_29 (k : ℕ) (z : ℕ → ℝ) (hz : ∀ j ∈ Icc 1 k, 0 ≤ z j ∧ z j ≤ 1)
(hsum : ∑ j ∈ Icc 1 k, z j ≤ 1) (i : ℕ) (hi : i ≤ k) :
1 - Real.exp (-Fstar z i) ≤ Fcum z i ∧
(1 - Real.exp (-1)) * Fstar z i ≤ 1 - Real.exp (-Fstar z i) := by sorry
end OfflineStochMatch.UnitPatience
Source
Brubach, Grammel, Ma, MacRury, Srinivasan, Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes, arXiv:2106.06892v3, p. 18, Eq. (29) (proof of Lemma 8; F(i) defined on p. 17, F*(i) on p. 18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.