§3.2 p. 11 — the random-order probability of both one-sided relaxed events equals the integral of the product of one-sided probabilities
OpenOfflineStochMatch.Attenuation.safe_relaxed_integralLet be a finite loopless graph without parallel edges ( injective) and let be an edge. Take arbitrary real vectors , patiences and a function (no range assumptions are needed: the identity is algebraic). Then
Here = arrivedBefore σ e marks the edges processed before , and on the left is a uniformly random order of while the coins have the Bernoulli weights of prob in the Setting.
This is the probabilistic step on p. 11 of the paper. A uniformly random order is the same as i.i.d. uniform arrival times . Given , each other edge arrives before independently with probability . The two one-sided events depend on the disjoint edge sets and : they are disjoint because has no parallel edges. So they are conditionally independent, and integrating over gives the right-hand side. In the finite model: for a fixed set , the probability that the set of edges before is exactly is .
import Mathlib import Definitions.Def_OfflineStochMatch_Attenuation_Setting import Definitions.Def_OfflineStochMatch_Attenuation_SideProb
namespace OfflineStochMatch.Attenuation
theorem safe_relaxed_integral {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 : ℝ → ℝ) (e : E) (u v : V) (huv : G.ends e = s(u, v)) :
prob p y (attProb aT p y) (fun σ Y A P =>
SideOK G t e u (arrivedBefore σ e) Y A P ∧ SideOK G t e v (arrivedBefore σ e) Y A P) =
∫ 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