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
- Epidemics.endHealthy step A₀ t = Dynamics.expList R t fun (l : List R) => ↑(Fintype.card V) - ↑(Epidemics.roundRun step A₀ l).card
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.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)
:
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}.