Documentation

Epidemics.CobraCoverEngine

Generic one-step growth engine, small phase (EPI-4, Lemma 2) #

Lemmas 2 to 4 use only a round-driven set process with a persistent source, an MGF bound, and a linear growth lower bound E|A'| ≥ |A| (1 + c (1 - |A|/n)) for some 0 < c ≤ 1. This file proves the small-set phase with c in place of 1 - λ. The large phase is in CobraCoverEngineLarge and the end phase is in CobraCoverEngineEnd.

def Epidemics.roundRun {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) (l : List R) :

The state of a round-driven process after the rounds l, starting from A.

Equations
Instances For
    @[simp]
    theorem Epidemics.roundRun_nil {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) :
    roundRun step A [] = A
    @[simp]
    theorem Epidemics.roundRun_cons {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) (ρ : R) (l : List R) :
    roundRun step A (ρ :: l) = roundRun step (step A ρ) l
    theorem Epidemics.roundRun_append {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) (l₁ l₂ : List R) :
    roundRun step A (l₁ ++ l₂) = roundRun step (roundRun step A l₁) l₂
    theorem Epidemics.roundRun_take_succ {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) (ρ : R) (l : List R) (s : ℕ) :
    roundRun step A (List.take (s + 1) (ρ :: l)) = roundRun step (step A ρ) (List.take s l)
    noncomputable def Epidemics.smallWeight {V : Type u_1} {R : Type u_2} [Fintype R] (step : Finset V → R → Finset V) (φ : ℝ) (m t : ℕ) (A : Finset V) :

    E(e^{-φ |A_t|} 1_{|A_s| ≤ m for all s < t}), for the process step started at A.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      noncomputable def Epidemics.smallProb {V : Type u_1} {R : Type u_2} [Fintype R] (step : Finset V → R → Finset V) (m t : ℕ) (A : Finset V) :

      P(|A_s| ≤ m for every s ≤ t).

      Equations
      Instances For
        theorem Epidemics.forall_lt_cons {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) (ρ : R) (l : List R) (m t : ℕ) :
        (∀ s < t + 1, (roundRun step A (List.take s (ρ :: l))).card ≤ m) ↔ A.card ≤ m ∧ ∀ s < t, (roundRun step (step A ρ) (List.take s l)).card ≤ m
        theorem Epidemics.forall_le_cons {V : Type u_1} {R : Type u_2} (step : Finset V → R → Finset V) (A : Finset V) (ρ : R) (l : List R) (m t : ℕ) :
        (∀ s ≤ t + 1, (roundRun step A (List.take s (ρ :: l))).card ≤ m) ↔ A.card ≤ m ∧ ∀ s ≤ t, (roundRun step (step A ρ) (List.take s l)).card ≤ m
        theorem Epidemics.smallProb_succ_pull {V : Type u_1} {R : Type u_2} [Fintype R] (step : Finset V → R → Finset V) (m t : ℕ) (A : Finset V) (ρ : R) :
        (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t + 1, (roundRun step A (List.take s (ρ :: l))).card ≤ m then 1 else 0) = (if A.card ≤ m then 1 else 0) * smallProb step m t (step A ρ)
        theorem Epidemics.smallWeight_succ_pull {V : Type u_1} {R : Type u_2} [Fintype R] (step : Finset V → R → Finset V) (φ : ℝ) (m t : ℕ) (A : Finset V) (ρ : R) :
        (Dynamics.expList R t fun (l : List R) => Real.exp (-φ * ↑(roundRun step A (ρ :: l)).card) * if ∀ s < t + 1, (roundRun step A (List.take s (ρ :: l))).card ≤ m then 1 else 0) = (if A.card ≤ m then 1 else 0) * smallWeight step φ m t (step A ρ)
        theorem Epidemics.smallProb_le_weight {V : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : Finset V → R → Finset V) (φ : ℝ) (hφ : 0 ≤ φ) (m t : ℕ) (A : Finset V) :
        smallProb step m t A ≤ Real.exp (φ * ↑m) * smallWeight step φ m t A

        While the set stays of size at most m, the failure probability is at most e^{φ m} times the weighted expectation. Only φ ≥ 0 is used.

        theorem Epidemics.smallProb_le_one {V : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : Finset V → R → Finset V) (m t : ℕ) (A : Finset V) :
        smallProb step m t A ≤ 1
        theorem Epidemics.exp_mean_le {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] (step : Finset V → R → Finset V) {c x φ : ℝ} (hc0 : 0 < c) (hx : x = c / 2) (hφ : φ = Real.log (1 + x)) {m : ℕ} (hm : 2 * m ≤ Fintype.card V) (hgrowth : ∀ (A : Finset V), ↑A.card * (1 + c * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) {A : Finset V} (hA1 : 1 ≤ A.card) (hAm : A.card ≤ m) :
        Real.exp (-(1 - Real.exp (-φ)) * Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) ≤ Real.exp (φ - x - φ * ↑A.card)

        One round from a set of size in 1, …, m multiplies the Laplace weight by at most e^{φ - x}.

        theorem Epidemics.smallWeight_contract {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] [Nonempty R] (step : Finset V → R → Finset V) (src : V) (hsrc : ∀ (A : Finset V) (ρ : R), src ∈ step A ρ) {c x φ : ℝ} (hc0 : 0 < c) (hx : x = c / 2) (hφ : φ = Real.log (1 + x)) (hmgf : ∀ (A : Finset V) (ψ : ℝ), (Dynamics.avg fun (ρ : R) => Real.exp (-ψ * ↑(step A ρ).card)) ≤ Real.exp (-(1 - Real.exp (-ψ)) * Dynamics.avg fun (ρ : R) => ↑(step A ρ).card)) (hgrowth : ∀ (A : Finset V), ↑A.card * (1 + c * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : R) => ↑(step A ρ).card) {m : ℕ} (hm : 2 * m ≤ Fintype.card V) (t : ℕ) (A : Finset V) :
        1 ≤ A.card → smallWeight step φ m t A ≤ Real.exp (↑t * (φ - x)) * Real.exp (-φ * ↑A.card)

        While |A| ≥ 1, the weighted expectation contracts by e^{φ - x} at every round.

        theorem Epidemics.round_small_phase {V : Type u_1} {R : Type u_2} [Fintype V] [Fintype R] [Nonempty R] (step : Finset V → R → Finset V) (src : V) (hsrc : ∀ (A : Finset V) (ρ : R), src ∈ step A ρ) (hmgf : ∀ (A : Finset V) (ψ : ℝ), (Dynamics.avg fun (ρ : R) => Real.exp (-ψ * ↑(step A ρ).card)) ≤ Real.exp (-(1 - Real.exp (-ψ)) * Dynamics.avg fun (ρ : R) => ↑(step A ρ).card)) {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) {m T : ℕ} (hm : 2 * m ≤ Fintype.card V) (C : ℝ) (hT : 13 * ↑m / c + 24 * C * Real.log ↑(Fintype.card V) / c ^ 2 ≤ ↑T) :
        smallProb step m T {src} ≤ ↑(Fintype.card V) ^ (-C)

        Lemma 2, abstract form. A round-driven process with a persistent source, the BIPS moment bound and relative growth 1 + c (1 - |A|/n) exceeds size m ≤ n/2 within T ≥ 13 m/c + 24 C log n/c² rounds, except with probability n^{-C}.