Documentation

Epidemics.CobraCoverTargets

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,

cobraCoinStep p and bipsCoinStep p v are tgtCobraStep (coinTargets p) and tgtBipsStep (coinTargets p) v by definition.

def Epidemics.tgtCobraStep {V : Type u_1} {R : Type u_2} [DecidableEq V] (tg : R → V → Finset V) (D : Finset V) (ρ : R) :

COBRA with target sets: every vertex x of D pushes to the vertices of tg ρ x.

Equations
Instances For
    def Epidemics.tgtBipsStep {V : Type u_1} {R : Type u_2} [DecidableEq V] [Fintype V] (tg : R → V → Finset V) (v : V) (A : Finset V) (ρ : R) :

    BIPS with target sets and source v: u is infected iff u = v or tg ρ u meets A.

    Equations
    Instances For
      theorem Epidemics.mem_tgtCobraStep {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} {D : Finset V} {ρ : R} {y : V} :
      y ∈ tgtCobraStep tg D ρ ↔ ∃ x ∈ D, y ∈ tg ρ x
      theorem Epidemics.mem_tgtBipsStep {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] {v : V} {A : Finset V} {ρ : R} {u : V} :
      u ∈ tgtBipsStep tg v A ρ ↔ u = v ∨ ∃ y ∈ tg ρ u, y ∈ A
      theorem Epidemics.hits_cons_roundRun {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (v : V) (C : Finset V) (ρ : R) (l : List R) :
      (∃ s ≤ (ρ :: l).length, v ∈ roundRun step C (List.take s (ρ :: l))) ↔ v ∈ C ∨ ∃ s ≤ l.length, v ∈ roundRun step (step C ρ) (List.take s l)

      The COBRA hitting event over the rounds ρ :: l (as hits_cons, for any step).

      theorem Epidemics.tgt_hit_iff_bips_reverse {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] (v : V) (C : Finset V) (l : List R) :
      (∃ s ≤ l.length, v ∈ roundRun (tgtCobraStep tg) C (List.take s l)) ↔ (C ∩ roundRun (tgtBipsStep tg v) {v} l.reverse).Nonempty

      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 Epidemics.tgt_duality {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] [Fintype R] (v : V) (C : Finset V) (t : ℕ) :
      (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, v ∉ roundRun (tgtCobraStep tg) C (List.take s l) then 1 else 0) = Dynamics.expList R t fun (l : List R) => if C ∩ roundRun (tgtBipsStep tg v) {v} l = ∅ then 1 else 0

      Theorem 4 with target sets: P(Hit_C(v) > t) = P(C ∩ A_t = ∅ ∣ A₀ = {v}).

      theorem Epidemics.src_mem_tgtBipsStep {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] (v : V) (A : Finset V) (ρ : R) :
      v ∈ tgtBipsStep tg v A ρ
      theorem Epidemics.tgtBipsStep_mono {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] (v : V) {A B : Finset V} (h : A ⊆ B) (ρ : R) :
      tgtBipsStep tg v A ρ ⊆ tgtBipsStep tg v B ρ
      theorem Epidemics.tgtBipsStep_univ {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] (htg : ∀ (ρ : R) (u : V), (tg ρ u).Nonempty) (v : V) (ρ : R) :
      theorem Epidemics.tgtCobraStep_nonempty {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} (htg : ∀ (ρ : R) (u : V), (tg ρ u).Nonempty) {D : Finset V} (hD : D.Nonempty) (ρ : R) :
      theorem Epidemics.card_tgtBipsStep_eq {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] {Ω : V → Type u_3} (e : R ≃ ((u : V) → Ω u)) (g : (u : V) → Ω u → Finset V) (htg : ∀ (ρ : R) (u : V), tg ρ u = g u (e ρ u)) (v : V) (A : Finset V) (ρ : R) :
      (tgtBipsStep tg v A ρ).card = {u : V | u = v ∨ ∃ y ∈ g u (e ρ u), y ∈ A}.card

      With independent targets, the size of the next BIPS set counts independent events.

      theorem Epidemics.tgtBips_mgf_le {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] [Fintype R] {Ω : V → Type u_3} [(u : V) → Fintype (Ω u)] (e : R ≃ ((u : V) → Ω u)) (g : (u : V) → Ω u → Finset V) (htg : ∀ (ρ : R) (u : V), tg ρ u = g u (e ρ u)) (v : V) (A : Finset V) (φ : ℝ) :
      (Dynamics.avg fun (ρ : R) => Real.exp (-φ * ↑(tgtBipsStep tg v A ρ).card)) ≤ Real.exp (-(1 - Real.exp (-φ)) * Dynamics.avg fun (ρ : R) => ↑(tgtBipsStep tg v A ρ).card)

      Moment generating function of one round (computation (12)) for BIPS with independent target sets.

      theorem Epidemics.tgtBips_expected_card {V : Type u_1} {R : Type u_2} [DecidableEq V] {tg : R → V → Finset V} [Fintype V] [Fintype R] {Ω : V → Type u_3} [(u : V) → Fintype (Ω u)] [∀ (u : V), Nonempty (Ω u)] (e : R ≃ ((u : V) → Ω u)) (g : (u : V) → Ω u → Finset V) (htg : ∀ (ρ : R) (u : V), tg ρ u = g u (e ρ u)) (v : V) (A : Finset V) :
      (Dynamics.avg fun (ρ : R) => ↑(tgtBipsStep tg v A ρ).card) = ∑ u : V, Dynamics.avg fun (a : Ω u) => if u = v ∨ ∃ y ∈ g u a, y ∈ A then 1 else 0

      Expected size of one round for BIPS with independent target sets: E|A'| = ∑_u P(u ∈ A').