Documentation

Epidemics.CobraCoverEngineEnd

Generic end phase (EPI-4, Lemma 4) #

Once |A| ≥ 9n/10 and 4000 log n/c² ≤ 9n/10, one round stays above 9n/10 except with probability n^{-8}, and the expected number of healthy vertices contracts by θ = 1 - (9/10) c. The scalar bounds are in CobraCoverNumerics.

theorem Epidemics.round_drop_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))) (hmono : ∀ (A B : Finset V) (ρ : R), A ⊆ B → step A ρ ⊆ step B ρ) (hn : 2 ≤ Fintype.card V) (hgap : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ 9 / 10 * ↑(Fintype.card V)) {A : Finset V} (hA : 9 * Fintype.card V ≤ 10 * A.card) :
(Dynamics.avg fun (ρ : R) => if 10 * (step A ρ).card < 9 * Fintype.card V then 1 else 0) ≤ ↑(Fintype.card V) ^ (-8)

From |A| ≥ 9n/10, one round falls below 9n/10 with probability at most n^{-8}.

theorem Epidemics.round_below_prob {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))) (hmono : ∀ (A B : Finset V) (ρ : R), A ⊆ B → step A ρ ⊆ step B ρ) (hn : 2 ≤ Fintype.card V) (hgap : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ 9 / 10 * ↑(Fintype.card V)) (t : ℕ) {A₀ : Finset V} (hA₀ : 9 * Fintype.card V ≤ 10 * A₀.card) :
(Dynamics.expList R t fun (l : List R) => if 9 * Fintype.card V ≤ 10 * (roundRun step A₀ l).card then 0 else 1) ≤ ↑t * ↑(Fintype.card V) ^ (-8)

After t rounds starting from |A₀| ≥ 9n/10, P(10|A_t| < 9n) ≤ t n^{-8}.

noncomputable def Epidemics.endHealthy {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] (step : Finset V → R → Finset V) (A₀ : Finset V) (t : ℕ) :

Expected number of healthy vertices.

Equations
Instances For
    theorem Epidemics.endHealthy_succ {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] (step : Finset V → R → Finset V) (A₀ : Finset V) (t : ℕ) :
    endHealthy step A₀ (t + 1) = Dynamics.expList R t fun (l : List R) => Dynamics.avg fun (ρ : R) => ↑(Fintype.card V) - ↑(step (roundRun step A₀ l) ρ).card
    theorem Epidemics.endGap_step {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) (hn : 0 < Fintype.card V) (A : Finset V) :
    (Dynamics.avg fun (ρ : R) => ↑(Fintype.card V) - ↑(step A ρ).card) ≤ (1 - 9 / 10 * c) * (↑(Fintype.card V) - ↑A.card) + ↑(Fintype.card V) * if 9 * Fintype.card V ≤ 10 * A.card then 0 else 1

    One round: E(n - |A'|) ≤ θ (n - |A|) + n 1_{10|A| < 9n}, with θ = 1 - (9/10) c.

    theorem Epidemics.endHealthy_rec {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))) (hmono : ∀ (A B : Finset V) (ρ : R), A ⊆ B → step A ρ ⊆ step B ρ) (hn : 2 ≤ Fintype.card V) (hgap : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ 9 / 10 * ↑(Fintype.card V)) {A₀ : Finset V} (hA₀ : 9 * Fintype.card V ≤ 10 * A₀.card) (t : ℕ) :
    endHealthy step A₀ (t + 1) ≤ (1 - 9 / 10 * c) * endHealthy step A₀ t + ↑t * ↑(Fintype.card V) ^ (-7)
    theorem Epidemics.endHealthy_le {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))) (hmono : ∀ (A B : Finset V) (ρ : R), A ⊆ B → step A ρ ⊆ step B ρ) (hn : 2 ≤ Fintype.card V) (hgap : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ 9 / 10 * ↑(Fintype.card V)) {A₀ : Finset V} (hA₀ : 9 * Fintype.card V ≤ 10 * A₀.card) (t : ℕ) :
    endHealthy step A₀ t ≤ (1 - 9 / 10 * c) ^ t * (↑(Fintype.card V) / 10) + ↑t ^ 2 * ↑(Fintype.card V) ^ (-7)
    theorem Epidemics.fail_le_gap {V : Type u_1} [Fintype V] [DecidableEq V] (A : Finset V) :
    (if A = Finset.univ then 0 else 1) ≤ ↑(Fintype.card V) - ↑A.card
    theorem Epidemics.roundRun_of_univ {V : Type u_1} {R : Type u_2} [Fintype V] (step : Finset V → R → Finset V) (huniv : ∀ (ρ : R), step Finset.univ ρ = Finset.univ) (l : List R) :
    theorem Epidemics.fail_append_le {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] (step : Finset V → R → Finset V) (huniv : ∀ (ρ : R), step Finset.univ ρ = Finset.univ) (A₀ : Finset V) (l₁ l₂ : List R) :
    (if roundRun step A₀ (l₁ ++ l₂) = Finset.univ then 0 else 1) ≤ if roundRun step A₀ l₁ = Finset.univ then 0 else 1
    theorem Epidemics.round_end_phase {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq 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))) (hmono : ∀ (A B : Finset V) (ρ : R), A ⊆ B → step A ρ ⊆ step B ρ) (huniv : ∀ (ρ : R), step Finset.univ ρ = Finset.univ) (hn : 2 ≤ Fintype.card V) (hgap : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ 9 / 10 * ↑(Fintype.card V)) {A₀ : Finset V} (hA₀ : 9 * Fintype.card V ≤ 10 * A₀.card) {T : ℕ} (hT : 8 * Real.log ↑(Fintype.card V) / c ≤ ↑T) :
    (Dynamics.expList R T fun (l : List R) => if roundRun step A₀ l = Finset.univ then 0 else 1) ≤ 1 / ↑(Fintype.card V) ^ 5

    Lemma 4, generic form. From |A₀| ≥ 9n/10, under 4000 log n/c² ≤ (9/10) n, the probability that time T ≥ 8 log n/c has not infected every vertex is at most n^{-5}.