Generic large and end phases (EPI-4, Lemmas 3 and 4) #
The same one-round hypotheses as the small phase, with c in place of 1 - λ: relative growth
E|A'| ≥ |A| (1 + c (1 - |A|/n)) and the Chernoff lower tail. Lemma 3 stops the process once
|A| ≥ 9n/10 and applies Dynamics.expList_escape.
theorem
Epidemics.round_slow_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)))
(hn : 2 ≤ Fintype.card V)
{A : Finset V}
(hA : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ ↑A.card)
(hsmall : 10 * A.card < 9 * Fintype.card V)
:
While 10|A| < 9n and |A| ≥ 4000 log n/c², one round fails to multiply the size by
1 + c/23 with probability at most n^{-5}.
theorem
Epidemics.round_large_phase
{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)))
(hn : 2 ≤ Fintype.card V)
{A₀ : Finset V}
(hA₀ : 4000 * Real.log ↑(Fintype.card V) / c ^ 2 ≤ ↑A₀.card)
{T : ℕ}
(hT : 24 * Real.log ↑(Fintype.card V) / c ≤ ↑T)
:
Lemma 3, generic form. From |A₀| ≥ 4000 log n/c², the probability that every prefix
has size < 9n/10 through time T ≥ 24 log n/c is at most T/n⁵.