COBRA and BIPS with target sets (EPI-4, Theorem 3) #
Both COBRA with branching factor 1 + ρ and its dual BIPS read, in a round ρ, a finite set
tg ρ x of neighbours used by each vertex x: COBRA pushes from x to tg ρ x, and in BIPS a
vertex u is infected iff it is the source or tg ρ u meets the infected set. This file proves,
for an arbitrary target map tg,
- the pathwise duality and Theorem 4 (
tgt_hit_iff_bips_reverse,tgt_duality), by the proof ofcobra_hit_iff_bips_reverseandcobra_bips_duality; - monotonicity, persistence of the source,
univabsorbing and nonemptiness of COBRA when the target sets are nonempty; - when
tg ρ uonly depends on the coordinateuofρunder an equivalenceR ≃ (u : V) → Ω u(independent vertices), the moment generating function bound (12) and the formulaE|A'| = ∑_u P(u ∈ A').
cobraCoinStep p and bipsCoinStep p v are tgtCobraStep (coinTargets p) and
tgtBipsStep (coinTargets p) v by definition.
COBRA with target sets: every vertex x of D pushes to the vertices of tg ρ x.
Equations
- Epidemics.tgtCobraStep tg D ρ = D.biUnion (tg ρ)
Instances For
BIPS with target sets and source v: u is infected iff u = v or tg ρ u meets A.
Equations
- Epidemics.tgtBipsStep tg v A ρ = insert v {u : V | ∃ y ∈ tg ρ u, y ∈ A}
Instances For
Pathwise duality with target sets: COBRA from C visits v within the rounds l iff
BIPS from {v} along the reversed rounds infects a vertex of C.
Theorem 4 with target sets: P(Hit_C(v) > t) = P(C ∩ A_t = ∅ ∣ A₀ = {v}).
With independent targets, the size of the next BIPS set counts independent events.
Moment generating function of one round (computation (12)) for BIPS with independent target sets.
Expected size of one round for BIPS with independent target sets:
E|A'| = ∑_u P(u ∈ A').