Documentation

Epidemics.CobraCoverChain

Chaining one-round phases (EPI-4, Theorems 1 and 2) #

A first-hit bound for a round-driven process, and the geometric estimate for a tail that contracts every T₀ steps. The BIPS and COBRA theorems instantiate both.

theorem Epidemics.expList_fail_le_one {R : Type u_2} [Fintype R] [Nonempty R] (T : ℕ) (P : List R → Prop) [DecidablePred P] :
(Dynamics.expList R T fun (l : List R) => if P l then 0 else 1) ≤ 1
theorem Epidemics.forall_not_cons {S : Type u_1} {R : Type u_2} (step : S → R → S) (P : S → Prop) (a : S) (ρ : R) (l : List R) {T₁ : ℕ} (hP : ¬P a) :
(∀ s ≤ T₁ + 1, ¬P (List.foldl step a (List.take s (ρ :: l)))) ↔ ∀ t ≤ T₁, ¬P (List.foldl step (step a ρ) (List.take t l))

Stepping once: avoiding P for T₁ + 1 steps from a, when a itself misses P, is avoiding P for T₁ steps from step a ρ.

theorem Epidemics.round_first_hit {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) (P Q : S → Prop) [DecidablePred P] [DecidablePred Q] {T₂ : ℕ} {ε : ℝ} (hε : 0 ≤ ε) (hgood : ∀ (b : S), P b → ∀ (T' : ℕ), T₂ ≤ T' → (Dynamics.expList R T' fun (l : List R) => if Q (List.foldl step b l) then 0 else 1) ≤ ε) (a : S) (T₁ T₂' : ℕ) (hT : T₂ ≤ T₂') :
(Dynamics.expList R (T₁ + T₂') fun (l : List R) => if Q (List.foldl step a l) then 0 else 1) ≤ (Dynamics.expList R T₁ fun (l : List R) => if ∀ s ≤ T₁, ¬P (List.foldl step a (List.take s l)) then 1 else 0) + ε

If every state satisfying P reaches Q within T₂ steps except with probability ε, and the same bound holds for every longer horizon, then from an arbitrary start the failure probability after T₁ + T₂' steps is at most the probability of avoiding P for T₁ steps, plus ε.

theorem Epidemics.geom_partial_le {ε : ℝ} (hε0 : 0 ≤ ε) (hε1 : ε < 1) (q : ℕ) :
∑ j ∈ Finset.range q, ε ^ j ≤ 1 / (1 - ε)
theorem Epidemics.sum_range_add {m n : ℕ} (f : ℕ → ℝ) :
∑ s ∈ Finset.range (m + n), f s = ∑ s ∈ Finset.range m, f s + ∑ s ∈ Finset.range n, f (m + s)
theorem Epidemics.iterate_shift {a : ℕ → ℝ} {T₀ : ℕ} {ε : ℝ} (hε0 : 0 ≤ ε) (hshift : ∀ (s : ℕ), a (s + T₀) ≤ ε * a s) (q r : ℕ) :
a (q * T₀ + r) ≤ ε ^ q * a r
theorem Epidemics.sum_range_shift_le {a : ℕ → ℝ} {T₀ : ℕ} {ε : ℝ} (hT : 0 < T₀) (hε0 : 0 ≤ ε) (hε1 : ε < 1) (h0 : ∀ (s : ℕ), 0 ≤ a s) (h1 : ∀ (s : ℕ), a s ≤ 1) (hshift : ∀ (s : ℕ), a (s + T₀) ≤ ε * a s) (H : ℕ) :
∑ s ∈ Finset.range H, a s ≤ ↑T₀ / (1 - ε)

If 0 ≤ a s ≤ 1 and a (s + T₀) ≤ ε a s with 0 ≤ ε < 1, every partial sum is at most T₀ / (1 - ε).

theorem Epidemics.cobraStep_nonempty {V : Type u_3} [DecidableEq V] {G : SimpleGraph V} {k : ℕ} (hk : 1 ≤ k) {D : Finset V} (hD : D.Nonempty) (ρ : Choices G k) :