The three stages of Theorem 43, for one value of n (EPI-8) #
- Geometric stage (
stage_geom): from at mostg nuninformed nodes to at mostg₀ n, with targetsg μ^j n,μ = (1 + a g^{ℓ-1}) / 2 < 1, in a constant numberKof phases. The paper uses Lemma 19 here, which gives the expectationO(1)but a tail whose rate does not depend onn; the per-round Chebyshev bound gives failure probabilityO(1/n)per phase. - Double exponential stage (
stage_double): targetsε_{j+1} = 2 a₁ ε_j^ℓ, written in closed formε_j = exp (-(κ + ℓ^j D₀))withκ (ℓ - 1) = ln (2 a₁), forJphases (Observation 3, Corollary 46 and Lemma 47 of the paper). - Finishing stage (
stage_finish): belowε_J nuninformed nodes every uninformed node stays uninformed with probability at mostθ, so all are informed aftertrounds except with probabilityθ^t n.
theorem
Epidemics.Revisited.stage_geom
{n : ℕ}
(P : RumorProcess n)
{ℓ a c g α τ lam μ δ : ℝ}
(K : ℕ)
(hℓ : 1 < ℓ)
(ha : 0 ≤ a)
(hc : 0 ≤ c)
(hg : 0 < g)
(hlam : a * g ^ (ℓ - 1) ≤ lam)
(hlamμ : lam < μ)
(hμ1 : μ ≤ 1)
(hδ : 0 < δ)
(hn : 1 ≤ n)
(h2 : 2 ≤ ↑n ^ (δ / 2))
(hq : (1 + c) * ↑n / (g * μ ^ K * (μ - lam) * ↑n) ^ 2 + ↑n ^ (1 - α) * ↑n ^ (-τ) / (g * μ ^ K * ↑n) ≤ ↑n ^ (-(2 * δ)))
(hDES : P.UpperDoubleShrinking ℓ a c g α)
(hFF : P.FastFinishing α τ)
(S : Finset (Fin n))
(hS : ↑n - ↑S.card ≤ g * ↑n)
(s : ℕ)
:
Stage 1: geometric targets g μ^j n.
theorem
Epidemics.Revisited.stage_double
{n : ℕ}
(P : RumorProcess n)
{ℓ a c g α τ a₁ κ D₀ δ : ℝ}
(J : ℕ)
(hℓ : 1 < ℓ)
(ha₁ : a ≤ a₁)
(ha₁0 : 0 < a₁)
(hc : 0 ≤ c)
(hκ : Real.log (2 * a₁) = κ * (ℓ - 1))
(hD₀ : 0 ≤ D₀)
(hε0 : epsSeq ℓ κ D₀ 0 ≤ g)
(hδ : 0 < δ)
(hn : 1 ≤ n)
(h2 : 2 ≤ ↑n ^ (δ / 2))
(hq :
(1 + c) * ↑n / (epsSeq ℓ κ D₀ J * ↑n / 2) ^ 2 + ↑n ^ (1 - α) * ↑n ^ (-τ) / (epsSeq ℓ κ D₀ J * ↑n) ≤ ↑n ^ (-(2 * δ)))
(hDES : P.UpperDoubleShrinking ℓ a c g α)
(hFF : P.FastFinishing α τ)
(S : Finset (Fin n))
(hS : ↑n - ↑S.card ≤ epsSeq ℓ κ D₀ 0 * ↑n)
(s : ℕ)
:
Stage 2: double exponential targets ε_j n, J phases.
theorem
Epidemics.Revisited.stage_finish
{n : ℕ}
(P : RumorProcess n)
{ℓ a c g α τ U θ : ℝ}
(hU : U ≤ g * ↑n)
(hθ : 0 ≤ θ)
(hθd : ∀ (u : ℝ), 0 ≤ u → u ≤ U → a * (u / ↑n) ^ (ℓ - 1) ≤ θ)
(hθf : ↑n ^ (-τ) ≤ θ)
(hDES : P.UpperDoubleShrinking ℓ a c g α)
(hFF : P.FastFinishing α τ)
(S : Finset (Fin n))
(hS : ↑n - ↑S.card ≤ U)
(t : ℕ)
:
Stage 3: finishing below U uninformed nodes, U ≤ g n, when the stay probability is at
most θ both under Definition 13 (where a (u/n)^{ℓ-1} ≤ θ) and under fast finishing.