Theorem 43 and the total spreading time with double exponential shrinking (EPI-8, proofs) #
double_shrinking_upper_tail_proof: Theorem 43's tailC n^{A' - α' r}, from the main case (double_shrinking_tail_main) and the degenerate casesg = 0(nothing to do) andα = 0(fast finishing everywhere).double_shrinking_exp_tail: the same tail in the formA e^{-α' r}(forn ≥ 3), which composes with the other regimes bytail_compose, and gives the expectation throughsum_notYet_le_of_tail.- The total spreading time: Theorem 21, Lemma 19 and Theorem 43 composed as in
spreading_upper_tail_proof.
theorem
Epidemics.Revisited.double_shrinking_tail_alpha_zero
{n : ℕ}
{τ : ℝ}
(hn : 1 ≤ n)
(P : RumorProcess n)
(hFF : P.FastFinishing 0 τ)
(S : Finset (Fin n))
(T₀ r : ℕ)
:
Theorem 43 with α = 0: every state finishes fast, so the tail is n^{1 - τ r}.
theorem
Epidemics.Revisited.double_shrinking_upper_tail_proof
{ℓ a c g α τ : ℝ}
(hℓ : 1 < ℓ)
(ha : 0 ≤ a)
(hc : 0 ≤ c)
(hg0 : 0 ≤ g)
(hα0 : 0 ≤ α)
(hag : a * g ^ (ℓ - 1) < 1)
(hτ : 0 < τ)
:
∃ (C : ℝ) (A' : ℝ) (α' : ℝ),
1 ≤ C ∧ 0 ≤ A' ∧ 0 < α' ∧ ∃ (N : ℕ),
∀ (n : ℕ),
N ≤ n →
∀ (P : RumorProcess n),
P.UpperDoubleShrinking ℓ a c g α →
P.FastFinishing α τ →
∀ (S : Finset (Fin n)),
↑n - ↑S.card ≤ g * ↑n →
∀ (r : ℕ), P.notYet (↑n) (⌈Real.logb ℓ (Real.log ↑n)⌉₊ + r) S ≤ C * ↑n ^ (A' - α' * ↑r)
Theorem 43, tail (proof of double_shrinking_upper_tail, with 1 ≤ C and 0 ≤ A').
theorem
Epidemics.Revisited.exp_tail_of_poly
{n : ℕ}
(P : RumorProcess n)
{m C A' α' : ℝ}
(hC : 1 ≤ C)
(hn : 3 ≤ n)
(T₀ : ℕ)
(S : Finset (Fin n))
(h : ∀ (r : ℕ), P.notYet m (T₀ + r) S ≤ C * ↑n ^ (A' - α' * ↑r))
(r : ℕ)
:
A polynomial tail C n^{A' - α' r} is an exponential tail C e^{A'} e^{-α' r} once
ln n ≥ 1.
theorem
Epidemics.Revisited.double_shrinking_upper_expect_proof
{ℓ a c g α τ : ℝ}
(hℓ : 1 < ℓ)
(ha : 0 ≤ a)
(hc : 0 ≤ c)
(hg0 : 0 ≤ g)
(hα0 : 0 ≤ α)
(hag : a * g ^ (ℓ - 1) < 1)
(hτ : 0 < τ)
:
∃ (B : ℝ) (N : ℕ),
∀ (n : ℕ),
N ≤ n →
∀ (P : RumorProcess n),
P.UpperDoubleShrinking ℓ a c g α →
P.FastFinishing α τ →
∀ (S : Finset (Fin n)),
↑n - ↑S.card ≤ g * ↑n → ∀ (R : ℕ), ∑ t ∈ Finset.range R, P.notYet (↑n) t S ≤ Real.logb ℓ (Real.log ↑n) + B
Theorem 43, expectation (proof of double_shrinking_upper_expect).
theorem
Epidemics.Revisited.spreading_upper_tail_double_proof
{γlo γhi a b c f ℓ a' c' g α τ p : ℝ}
(hγlo : 0 < γlo)
(hγ : γlo ≤ γhi)
(ha : 0 ≤ a)
(hb : 0 ≤ b)
(hc : 0 ≤ c)
(hf0 : 0 < f)
(hf1 : f < 1)
(haf : a * f < 1)
(hℓ : 1 < ℓ)
(ha' : 0 ≤ a')
(hc' : 0 ≤ c')
(hg0 : 0 < g)
(hα0 : 0 ≤ α)
(hag : a' * g ^ (ℓ - 1) < 1)
(hτ : 0 < τ)
(hp0 : 0 < p)
(hp1 : p ≤ 1)
:
∃ (A : ℝ) (κ : ℝ),
0 ≤ A ∧ 0 < κ ∧ ∃ (N : ℕ),
∀ (n : ℕ),
N ≤ n →
∀ (γ : ℝ),
γlo ≤ γ →
γ ≤ γhi →
∀ (P : RumorProcess n),
P.UpperGrowth γ a b c f →
P.UpperDoubleShrinking ℓ a' c' g α →
P.FastFinishing α τ →
(∀ (S : Finset (Fin n)),
f * ↑n ≤ ↑S.card → g * ↑n < ↑n - ↑S.card → ∀ x ∉ S, p ≤ P.informProb S x) →
∀ (S : Finset (Fin n)),
S.Nonempty →
∀ (r : ℕ),
P.notYet (↑n) (⌈Real.logb (1 + γ) ↑n⌉₊ + ⌈Real.logb ℓ (Real.log ↑n)⌉₊ + r) S ≤ A * Real.exp (-κ * ↑r)
Total spreading time with double exponential shrinking, tail (proof of
spreading_upper_tail_double).
theorem
Epidemics.Revisited.spreading_upper_expect_double_proof
{γlo γhi a b c f ℓ a' c' g α τ p : ℝ}
(hγlo : 0 < γlo)
(hγ : γlo ≤ γhi)
(ha : 0 ≤ a)
(hb : 0 ≤ b)
(hc : 0 ≤ c)
(hf0 : 0 < f)
(hf1 : f < 1)
(haf : a * f < 1)
(hℓ : 1 < ℓ)
(ha' : 0 ≤ a')
(hc' : 0 ≤ c')
(hg0 : 0 < g)
(hα0 : 0 ≤ α)
(hag : a' * g ^ (ℓ - 1) < 1)
(hτ : 0 < τ)
(hp0 : 0 < p)
(hp1 : p ≤ 1)
:
∃ (B : ℝ) (N : ℕ),
∀ (n : ℕ),
N ≤ n →
∀ (γ : ℝ),
γlo ≤ γ →
γ ≤ γhi →
∀ (P : RumorProcess n),
P.UpperGrowth γ a b c f →
P.UpperDoubleShrinking ℓ a' c' g α →
P.FastFinishing α τ →
(∀ (S : Finset (Fin n)), f * ↑n ≤ ↑S.card → g * ↑n < ↑n - ↑S.card → ∀ x ∉ S, p ≤ P.informProb S x) →
∀ (S : Finset (Fin n)),
S.Nonempty →
∀ (R : ℕ),
∑ t ∈ Finset.range R, P.notYet (↑n) t S ≤ Real.logb (1 + γ) ↑n + Real.logb ℓ (Real.log ↑n) + B
Total spreading time with double exponential shrinking, expectation (proof of
spreading_upper_expect_double).