Documentation

Epidemics.CobraCoverPhases

The three phases chained, for an abstract growth process (EPI-4, Theorems 2 and 3) #

GrowthProcess step src c collects what the proofs of Lemmas 2 to 4 use about one round of a set process: the source src is always in the next set (H1), the moment generating function bound of bips_mgf_le (H2), the growth bound E|A'| ≥ |A| (1 + c (1 - |A|/n)) of Lemma 1 (H3), monotonicity in the current set (H4), and univ is absorbing (H5). BIPS satisfies it with c = 1 - λ (Theorem 2) and BIPS with branching factor 1 + ρ with c = ρ₀ (1 - λ₀) (Theorem 3).

From {src}, Lemma 2 reaches size m = ⌈4000 log n/c²⌉₊, Lemma 3 then reaches 9n/10 and Lemma 4 infects every vertex; the phases are chained at their first hitting times (round_first_hit). Under c ≥ 128 √(log n/n) the three lengths add up to 60000 log n/c³ (phase_schedule), and the failure probability is ≤ 3/n³ (GrowthProcess.fail_le). Restarting from the current set every ⌈60000 log n/c³⌉₊ rounds bounds the tail sums of the infection time (GrowthProcess.tail_sum_le_log), the paper's equation (1).

theorem Epidemics.avg_lower_tail_of_mgf {R : Type u_1} [Fintype R] (X : R → ℝ) (hmgf : ∀ (ψ : ℝ), (Dynamics.avg fun (ρ : R) => Real.exp (-ψ * X ρ)) ≤ Real.exp (-(1 - Real.exp (-ψ)) * Dynamics.avg X)) {δ μ : ℝ} (hδ0 : 0 < δ) (hδ1 : δ < 1) (hμ : μ ≤ Dynamics.avg X) :
(Dynamics.avg fun (ρ : R) => if X ρ ≤ (1 - δ) * μ then 1 else 0) ≤ Real.exp (-(δ ^ 2 * μ / 2))

Chernoff lower tail from the moment generating function (the computation of bips_chernoff_lower, for any real observable X of one round): if E e^{-ψ X} ≤ exp(-(1 - e^{-ψ}) E X) for every ψ, μ ≤ E X and 0 < δ < 1, then P(X ≤ (1 - δ) μ) ≤ exp(-δ² μ/2).

structure Epidemics.GrowthProcess {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] (step : Finset V → R → Finset V) (src : V) (c : ℝ) :

The one-round hypotheses of the generic phase lemmas: (H1) the source is always in the next set, (H2) the moment generating function bound, (H3) growth E|A'| ≥ |A| (1 + c (1 - |A|/n)), (H4) monotonicity, (H5) univ is absorbing.

Instances For
    theorem Epidemics.GrowthProcess.chernoff {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] {step : Finset V → R → Finset V} {src : V} {c : ℝ} (hP : GrowthProcess step src c) (A : Finset V) (δ μ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1) (hμ : μ ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) :
    (Dynamics.avg fun (ρ : R) => if ↑(step A ρ).card ≤ (1 - δ) * μ then 1 else 0) ≤ Real.exp (-(δ ^ 2 * μ / 2))

    The Chernoff lower tail (H2'), from the moment generating function bound.

    theorem Epidemics.GrowthProcess.run_mono {V : Type u_1} {R : Type u_2} {step : Finset V → R → Finset V} (hmono : ∀ (A B : Finset V) (ρ : R), A ⊆ B → step A ρ ⊆ step B ρ) {A B : Finset V} (h : A ⊆ B) (l : List R) :
    roundRun step A l ⊆ roundRun step B l
    theorem Epidemics.GrowthProcess.src_mem_run {V : Type u_1} {R : Type u_2} {step : Finset V → R → Finset V} {src : V} (hsrc : ∀ (A : Finset V) (ρ : R), src ∈ step A ρ) {A : Finset V} (hA : src ∈ A) (l : List R) :
    src ∈ roundRun step A l
    theorem Epidemics.GrowthProcess.fail_le {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] {step : Finset V → R → Finset V} {src : V} {c : ℝ} [Nonempty R] (hP : GrowthProcess step src c) (hc1 : c ≤ 1) (hn2 : 2 ≤ Fintype.card V) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ c) {T : ℕ} (hT : 60000 * Real.log ↑(Fintype.card V) / c ^ 3 ≤ ↑T) :
    (Dynamics.expList R T fun (l : List R) => if roundRun step {src} l = Finset.univ then 0 else 1) ≤ 3 / ↑(Fintype.card V) ^ 3

    The three phases chained (proof of Theorem 2, generic form). If c ≥ 128 √(log n/n) and T ≥ 60000 log n/c³, the process started from {src} has not covered V at time T with probability at most 3/n³.

    theorem Epidemics.GrowthProcess.tail_sum_le {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] {step : Finset V → R → Finset V} {src : V} {c : ℝ} [Nonempty R] (hP : GrowthProcess step src c) {T₀ : ℕ} (hT₀ : 0 < T₀) (hhalf : (Dynamics.expList R T₀ fun (l : List R) => if roundRun step {src} l = Finset.univ then 0 else 1) ≤ 1 / 2) (H : ℕ) :
    (∑ s ∈ Finset.range H, Dynamics.expList R s fun (l : List R) => if roundRun step {src} l = Finset.univ then 0 else 1) ≤ 2 * ↑T₀

    Restarting (equation (1), generic form): if from {src} the failure probability at time T₀ > 0 is at most 1/2, then every partial tail sum ∑_{s < H} P(A_s ≠ V) is at most 2 T₀. From a state A ∋ src the process dominates the one restarted from {src}, so P(A_{s + T₀} ≠ V) ≤ P(A_s ≠ V)/2.

    theorem Epidemics.GrowthProcess.card_ge_of_gap {V : Type u_1} [Fintype V] {c : ℝ} (hc1 : c ≤ 1) (hn2 : 2 ≤ Fintype.card V) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ c) :

    The gap hypothesis c ≥ 128 √(log n/n) with c ≤ 1 forces n ≥ 16385 (so 3/n² ≤ 1/2 in the restarting arguments).

    theorem Epidemics.GrowthProcess.tail_sum_le_log {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] {step : Finset V → R → Finset V} {src : V} {c : ℝ} [Nonempty R] (hP : GrowthProcess step src c) (hc1 : c ≤ 1) (hn2 : 2 ≤ Fintype.card V) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ c) (H : ℕ) :
    (∑ s ∈ Finset.range H, Dynamics.expList R s fun (l : List R) => if roundRun step {src} l = Finset.univ then 0 else 1) ≤ 130000 * Real.log ↑(Fintype.card V) / c ^ 3

    Tail sums of the infection time (generic form of Theorem 2 in expectation): under c ≥ 128 √(log n/n), every partial sum ∑_{s < H} P(A_s ≠ V) from {src} is at most 130000 log n/c³.