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]
:
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.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 : ℕ)
:
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)
: