Documentation

Epidemics.CobraCoverEngineLarge

Generic large and end phases (EPI-4, Lemmas 3 and 4) #

The same one-round hypotheses as the small phase, with c in place of 1 - λ: relative growth E|A'| ≥ |A| (1 + c (1 - |A|/n)) and the Chernoff lower tail. Lemma 3 stops the process once |A| ≥ 9n/10 and applies Dynamics.expList_escape.

def Epidemics.stepFreeze {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (n : ℕ) (A : Finset V) (ρ : R) :

Freeze the round once the infected set covers at least 9n/10.

Equations
Instances For
    def Epidemics.largeTarget {V : Type u_1} [Fintype V] (A₀ : Finset V) (z : ℝ) (t : ℕ) :

    States that have already reached 9n/10, or have grown by (1 + z)^t from A₀.

    Equations
    Instances For
      theorem Epidemics.expList_take {R : Type u_2} [Fintype R] (T : ℕ) (F : List R → ℝ) :
      (Dynamics.expList R T fun (l : List R) => F (List.take T l)) = Dynamics.expList R T F
      theorem Epidemics.freeze_eq_of_below {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (n : ℕ) (A : Finset V) (m : List R) (h : ∀ s ≤ m.length, 10 * (roundRun step A (List.take s m)).card < 9 * n) :
      roundRun (stepFreeze step n) A m = roundRun step A m
      theorem Epidemics.round_slow_prob {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] (step : Finset V → R → Finset V) {c : ℝ} (hc0 : 0 < c) (hc1 : c ≤ 1) (hgrowth : ∀ (A : Finset V), ↑A.card * (1 + c * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) (hchernoff : ∀ (A : Finset V) (δ μ : ℝ), 0 < δ → δ < 1 → (μ ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) → (Dynamics.avg fun (ρ : R) => if ↑(step A ρ).card ≤ (1 - δ) * μ then 1 else 0) ≤ Real.exp (-(δ ^ 2 * μ / 2))) (hn : 2 ≤ Fintype.card V) {A : Finset V} (hA : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ ↑A.card) (hsmall : 10 * A.card < 9 * Fintype.card V) :
      (Dynamics.avg fun (ρ : R) => if ↑(step A ρ).card < ↑A.card * (1 + c / 23) then 1 else 0) ≤ ↑(Fintype.card V) ^ (-5)

      While 10|A| < 9n and |A| ≥ 4000 log n/c², one round fails to multiply the size by 1 + c/23 with probability at most n^{-5}.

      theorem Epidemics.take_take_of_le {R : Type u_2} (l : List R) {s T : ℕ} (hs : s ≤ T) :

      Prefixes of l.take T of length at most T are prefixes of l.

      theorem Epidemics.one_add_c_div_pow_ge {c : ℝ} {n T : ℕ} (hc0 : 0 < c) (hc1 : c ≤ 1) (hn : 2 ≤ n) (hT : 24 * Real.log ↑n / c ≤ ↑T) :
      ↑n ≤ (1 + c / 23) ^ T

      (1 + c/23)^T ≥ n for T ≥ 24 log n / c, using log(1 + z) ≥ z/(1 + z) ≥ c/24.

      theorem Epidemics.round_large_phase {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] [Nonempty R] (step : Finset V → R → Finset V) {c : ℝ} (hc0 : 0 < c) (hc1 : c ≤ 1) (hgrowth : ∀ (A : Finset V), ↑A.card * (1 + c * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) (hchernoff : ∀ (A : Finset V) (δ μ : ℝ), 0 < δ → δ < 1 → (μ ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) → (Dynamics.avg fun (ρ : R) => if ↑(step A ρ).card ≤ (1 - δ) * μ then 1 else 0) ≤ Real.exp (-(δ ^ 2 * μ / 2))) (hn : 2 ≤ Fintype.card V) {A₀ : Finset V} (hA₀ : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ ↑A₀.card) {T : ℕ} (hT : 24 * Real.log ↑(Fintype.card V) / c ≤ ↑T) :
      (Dynamics.expList R T fun (l : List R) => if ∀ s ≤ T, 10 * (roundRun step A₀ (List.take s l)).card < 9 * Fintype.card V then 1 else 0) ≤ ↑T / ↑(Fintype.card V) ^ 5

      Lemma 3, generic form. From |A₀| ≥ 4000 log n/c², the probability that every prefix has size < 9n/10 through time T ≥ 24 log n/c is at most T/n⁵.