Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.2 p. 11 — the random-order probability of both one-sided relaxed events equals the integral of the product of one-sided probabilities

Open
OfflineStochMatch.Attenuation.safe_relaxed_integral

by kmehltretter82 · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

attenuationpatiencerandom-orderstochastic-matching

Let G=(V,E)G=(V,E)G=(V,E) be a finite loopless graph without parallel edges (ends\mathrm{ends}ends injective) and let e={u,v}e=\{u,v\}e={u,v} be an edge. Take arbitrary real vectors p,yp,yp,y, patiences ttt and a function a~\tilde aa~ (no range assumptions are needed: the identity is algebraic). Then

Pr⁡σ,Y,A,P[SideOKu(Bσ,Y,A,P)∧SideOKv(Bσ,Y,A,P)]=∫01sideProbu(x) sideProbv(x) dx.\Pr_{\sigma,Y,A,P}\big[\mathrm{SideOK}_u(B^\sigma,Y,A,P)\wedge \mathrm{SideOK}_v(B^\sigma,Y,A,P)\big]=\int_0^1 \mathrm{sideProb}_u(x)\,\mathrm{sideProb}_v(x)\,dx .σ,Y,A,PPr​[SideOKu​(Bσ,Y,A,P)∧SideOKv​(Bσ,Y,A,P)]=∫01​sideProbu​(x)sideProbv​(x)dx.

Here BσB^\sigmaBσ = arrivedBefore σ e marks the edges processed before eee, and on the left σ\sigmaσ is a uniformly random order of EEE 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 π(f)∈[0,1]\pi(f)\in[0,1]π(f)∈[0,1]. Given π(e)=x\pi(e)=xπ(e)=x, each other edge arrives before eee independently with probability xxx. The two one-sided events depend on the disjoint edge sets E(u)E(u)E(u) and E(v)E(v)E(v): they are disjoint because GGG has no parallel edges. So they are conditionally independent, and integrating over xxx gives the right-hand side. In the finite model: for a fixed set S⊆E∖{e}S\subseteq E\setminus\{e\}S⊆E∖{e}, the probability that the set of edges before eee is exactly SSS is ∣S∣! (∣E∣−1−∣S∣)!/∣E∣!=∫01x∣S∣(1−x)∣E∣−1−∣S∣dx|S|!\,(|E|-1-|S|)!/|E|!=\int_0^1 x^{|S|}(1-x)^{|E|-1-|S|}dx∣S∣!(∣E∣−1−∣S∣)!/∣E∣!=∫01​x∣S∣(1−x)∣E∣−1−∣S∣dx.

Preamble
import Mathlib
import Definitions.Def_OfflineStochMatch_Attenuation_Setting
import Definitions.Def_OfflineStochMatch_Attenuation_SideProb
Formal statement
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
Source
Brubach, Grammel, Ma, MacRury, Srinivasan, Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes, arXiv:2106.06892v3, §3.2 p. 11: conditioning on the arrival time of e and factorizing over the two endpoints (display before Lemma 3), giving Eq. (8)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me