Documentation

Epidemics.Revisited.DoubleShrinkingTotal

Theorem 43 and the total spreading time with double exponential shrinking (EPI-8, proofs) #

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 : ℕ) :
P.notYet (↑n) (T₀ + r) S ≤ 1 * ↑n ^ (1 - τ * ↑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 : ℕ) :
P.notYet m (T₀ + r) S ≤ C * Real.exp A' * Real.exp (-α' * ↑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_exp_tail {ℓ a c g α τ : ℝ} (hℓ : 1 < ℓ) (ha : 0 ≤ a) (hc : 0 ≤ c) (hg0 : 0 ≤ g) (hα0 : 0 ≤ α) (hag : a * g ^ (ℓ - 1) < 1) (hτ : 0 < τ) :
∃ (A : ℝ) (α' : ℝ), 0 ≤ A ∧ 0 < α' ∧ ∃ (N : ℕ), 3 ≤ 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 ≤ A * Real.exp (-α' * ↑r)

Theorem 43, exponential form of the tail.

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).