§3.2 pp. 10–15 — of the product of one-sided relaxed probabilities is at least
OpenOfflineStochMatch.Attenuation.relaxed_boundLet be a finite graph without parallel edges, with edge probabilities , patiences ( allowed), and feasible for LP (3). Let be or . For every edge ,
Here is the probability, with each edge of arriving before independently with probability , that (1) no such early edge has , and (2) at most early edges have .
This is the analytic part of the proof of Theorem 1 (§3.2, pp. 10–15). It starts from the lower bound (8) of by the integral of the product of the one-sided probabilities. It then covers the reduction of Lemma 2 (, , saturated patience constraints), Lemma 3 (the factor ), the Poisson and Chernoff bounds (Lemmas 4–5, Eqs. (9)–(10)), the cases (Eqs. (12)–(15)) and with the exchange argument of Lemma 6 and Proposition 1, and finally Eqs. (22)–(25). Formalization Note The statement is about the one-sided relaxed probabilities, not about the safe event itself, and it is stated for arbitrary , that is, before the reduction of Lemma 2 to . The infimum is approached when , , and at each endpoint many small edges carry total -mass 1 with and total -mass 1 with .
import Mathlib import Definitions.Def_OfflineStochMatch_Attenuation_Setting import Definitions.Def_OfflineStochMatch_Attenuation_SideProb
namespace OfflineStochMatch.Attenuation
theorem relaxed_bound {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : EdmondsMatching65.Polyhedron.Graph V E) (hG : Function.Injective G.ends)
(p y : E → ℝ) (t : V → ℕ∞) (aT : ℝ → ℝ)
(hp : ∀ f, 0 ≤ p f ∧ p f ≤ 1) (ht : ∀ v, 2 ≤ t v) (hy : LPFeasible G p t y)
(haT : aT = expAtt (1 / 2) ∨ aT = linAtt (1 / 2)) (e : E) (u v : V)
(huv : G.ends e = s(u, v)) :
betaStar ≤ aT (p e * y e) *
∫ x in (0 : ℝ)..1, sideProb G p t y aT e u x * sideProb G p t y aT e v x := by sorry
end OfflineStochMatch.Attenuation