One-sided relaxed safety event at an endpoint of and its probability at arrival probability
DefinitionOfflineStochMatch_Attenuation_SideProbFix an edge of the graph in the attenuation setting and an endpoint of . Write for the other edges at (notation of p. 11).
Arrival indicators. For a processing order , arrivedBefore σ e is the indicator vector with exactly when is processed before .
One-sided relaxed condition. For indicators and the coins of Algorithm 1, means:
- no has ;
- (that is, at most such edges; no subtraction in ).
It depends only on the coordinates in . Any probe made before to an edge of is at an edge with . Hence and for arrivedBefore σ e together imply that is safe.
Probability. is the probability of when all coordinates are independent with , , , :
This is the conditional probability, given arrival time , of the paper's one-sided sufficient condition for safety (p. 11, the display before Lemma 3 and the bound by ), here stated for arbitrary before the reduction of Lemma 2.
import Mathlib
import Definitions.Def_OfflineStochMatch_Attenuation_Setting
namespace OfflineStochMatch.Attenuation
variable {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
/-- `E(r)`, the edges other than `e` incident to the vertex `r` (p. 11). -/
def otherIncident (G : EdmondsMatching65.Polyhedron.Graph V E) (e : E) (r : V) : Finset E :=
(incident G r).erase e
/-- Arrival indicators induced by the order `σ`: `true` at `f` exactly when `f` comes before `e`. -/
def arrivedBefore {n : ℕ} (σ : E ≃ Fin n) (e : E) : E → Bool :=
fun f => decide (σ f < σ e)
/-- One-sided relaxed condition at the endpoint `r` of `e`, given arrival indicators `B` and the
coins `Y`, `A`, `P`: (1) no `f ∈ E(r)` with `B f = Y f = A f = P f = true`, and (2) the number of
`f ∈ E(r)` with `B f = Y f = A f = true`, plus one, is at most `t r`. -/
def SideOK (G : EdmondsMatching65.Polyhedron.Graph V E) (t : V → ℕ∞) (e : E) (r : V)
(B Y A P : E → Bool) : Prop :=
(∀ f ∈ otherIncident G e r, ¬ (B f = true ∧ Y f = true ∧ A f = true ∧ P f = true)) ∧
((((otherIncident G e r).filter
(fun f => B f = true ∧ Y f = true ∧ A f = true)).card : ℕ∞) + 1 ≤ t r)
open Classical in
/-- Probability of `SideOK` when each edge independently arrives before `e` with probability `x`
and the coins are `Y_f ~ Bernoulli(y_f)`, `A_f ~ Bernoulli(ã(p_f y_f))`, `P_f ~ Bernoulli(p_f)`. -/
noncomputable def sideProb (G : EdmondsMatching65.Polyhedron.Graph V E) (p : E → ℝ) (t : V → ℕ∞)
(y : E → ℝ) (aT : ℝ → ℝ) (e : E) (r : V) (x : ℝ) : ℝ :=
∑ B : E → Bool, ∑ Y : E → Bool, ∑ A : E → Bool, ∑ P : E → Bool,
coinWeight (fun _ => x) B * coinWeight y Y * coinWeight (attProb aT p y) A *
coinWeight p P * (if SideOK G t e r B Y A P then 1 else 0)
end OfflineStochMatch.Attenuation