Documentation

Epidemics.CobraCoverCoin

One round of BIPS with branching factor 1 + p/q (EPI-4, Corollary 1) #

A round of the coin processes is Choices G 2 × (V → Fin q): two neighbour samples and a coin per vertex. Regrouping by vertex (coinEquiv) gives the product of the per-vertex samples CoinSample G q u = (Fin 2 → G.neighborSet u) × Fin q, so the vertices are independent. Vertex u uses its first sample, and also its second one when its coin is < p (coinTgt), so with P = d_A(u)/r and ρ = p/q it meets A with probability 1 - (1 - P)(1 - ρ P) = (1 + ρ) P - ρ P² (coin_hit_prob). As in Lemma 1, the spectral bound ∑_u P_u² ≤ λ² |A| + (1 - λ²) |A|²/n gives Corollary 1 (coin_expected_growth).

@[reducible, inline]
abbrev Epidemics.CoinSample {V : Type u_1} (G : SimpleGraph V) (q : ℕ) (u : V) :
Type u_1

The samples of one vertex u in a round of the coin processes.

Equations
Instances For
    def Epidemics.coinEquiv {V : Type u_1} (G : SimpleGraph V) (q : ℕ) :
    Choices G 2 × (V → Fin q) ≃ ((u : V) → CoinSample G q u)

    Regrouping a round of the coin processes by vertex.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      def Epidemics.coinTgt {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) {u : V} (a : CoinSample G q u) :

      The neighbours used by u given its samples: the first one, and the second one when the coin is < p.

      Equations
      Instances For
        theorem Epidemics.coinTgt_nonempty {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) {u : V} (a : CoinSample G q u) :
        theorem Epidemics.coinTgt_hit_indicator {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) {u : V} (A : Finset V) (a : CoinSample G q u) :
        (if ∃ y ∈ coinTgt p a, y ∈ A then 1 else 0) = (1 - if ↑(a.1 0) ∈ A then 0 else 1) + ((if ↑(a.1 0) ∈ A then 0 else 1) * if ↑(a.1 1) ∈ A then 1 else 0) * if ↑a.2 < p then 1 else 0

        Meeting A with the targets: first sample in A, or coin < p and second sample in A, written as 1 - m₀ + m₀ h₁ c with m₀ = 1_{first ∉ A}, h₁ = 1_{second ∈ A}, c = 1_{coin < p}.

        theorem Epidemics.coin_hit_prob {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) {p q : ℕ} (hq : 0 < q) (hpq : p ≤ q) (u : V) (A : Finset V) :
        (Dynamics.avg fun (a : CoinSample G q u) => if ∃ y ∈ coinTgt p a, y ∈ A then 1 else 0) = (1 + ↑p / ↑q) * (↑(G.neighborFinset u ∩ A).card / ↑r) - ↑p / ↑q * (↑(G.neighborFinset u ∩ A).card / ↑r) ^ 2

        Infection probability of a vertex u ≠ v with branching factor 1 + ρ, ρ = p/q: (1 + ρ) P - ρ P² with P = d_A(u)/r.

        theorem Epidemics.coin_expected_growth {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) {p q : ℕ} (hq : 0 < q) (hpq : p ≤ q) (v : V) (A : Finset V) :
        ↑A.card * (1 + ↑p / ↑q * (1 - Dynamics.lambdaG G r ^ 2) * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : Choices G 2 × (V → Fin q)) => ↑(tgtBipsStep (fun (ρ : Choices G 2 × (V → Fin q)) (x : V) => coinTgt p ((coinEquiv G q) ρ x)) v A ρ).card

        Corollary 1 (Section 3), for the target-set form of BIPS with branching factor 1 + p/q: E|A'| ≥ |A| (1 + ρ (1 - λ²)(1 - |A|/n)) with ρ = p/q.

        theorem Epidemics.coin_rate {lam₀ ρ₀ : ℝ} (hlam₀ : lam₀ < 1) (hρ₀ : 0 < ρ₀) :
        ∃ (c : ℝ), 0 < c ∧ c ≤ 1 ∧ ∀ (ρ lam : ℝ), ρ₀ ≤ ρ → 0 ≤ lam → lam ≤ lam₀ → c ≤ ρ * (1 - lam ^ 2)

        The rate of Theorem 3: c = min 1 (ρ₀ (1 - max λ₀ 0)) satisfies 0 < c ≤ 1 and c ≤ ρ (1 - λ²) whenever ρ ≥ ρ₀ and 0 ≤ λ ≤ λ₀.

        theorem Epidemics.exists_gap_N {c : ℝ} (hc : 0 < c) :
        ∃ (N : ℕ), 2 ≤ N ∧ ∀ (n : ℕ), N ≤ n → 128 * √(Real.log ↑n / ↑n) ≤ c

        Choice of N in Theorem 3: for a constant c > 0, 128 √(log n/n) ≤ c for all large n (from log n ≤ 2 √n).