Documentation

Epidemics.Revisited.DoubleShrinkingStages

The three stages of Theorem 43, for one value of n (EPI-8) #

  1. Geometric stage (stage_geom): from at most g n uninformed nodes to at most g₀ n, with targets g μ^j n, μ = (1 + a g^{ℓ-1}) / 2 < 1, in a constant number K of phases. The paper uses Lemma 19 here, which gives the expectation O(1) but a tail whose rate does not depend on n; the per-round Chebyshev bound gives failure probability O(1/n) per phase.
  2. Double exponential stage (stage_double): targets ε_{j+1} = 2 a₁ ε_j^ℓ, written in closed form ε_j = exp (-(κ + ℓ^j D₀)) with κ (ℓ - 1) = ln (2 a₁), for J phases (Observation 3, Corollary 46 and Lemma 47 of the paper).
  3. Finishing stage (stage_finish): below ε_J n uninformed nodes every uninformed node stays uninformed with probability at most θ, so all are informed after t rounds 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 : ℕ) :
P.notYet (↑n - g * μ ^ K * ↑n) (K + s) S ≤ 2 ^ K * ↑n ^ (-(δ / 2) * ↑s)

Stage 1: geometric targets g μ^j n.

noncomputable def Epidemics.Revisited.epsSeq (ℓ κ D₀ : ℝ) (j : ℕ) :

The closed form of the double exponential targets.

Equations
Instances For
    theorem Epidemics.Revisited.epsSeq_pos (ℓ κ D₀ : ℝ) (j : ℕ) :
    0 < epsSeq ℓ κ D₀ j
    theorem Epidemics.Revisited.epsSeq_anti {ℓ κ D₀ : ℝ} (hℓ : 1 ≤ ℓ) (hD₀ : 0 ≤ D₀) {j k : ℕ} (hjk : j ≤ k) :
    epsSeq ℓ κ D₀ k ≤ epsSeq ℓ κ D₀ j
    theorem Epidemics.Revisited.epsSeq_succ {ℓ κ D₀ a₁ : ℝ} (ha₁ : 0 < a₁) (hκ : Real.log (2 * a₁) = κ * (ℓ - 1)) (j : ℕ) :
    epsSeq ℓ κ D₀ (j + 1) = 2 * a₁ * epsSeq ℓ κ D₀ j ^ ℓ

    ε_{j+1} = 2 a₁ ε_j^ℓ.

    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 : ℕ) :
    P.notYet (↑n - epsSeq ℓ κ D₀ J * ↑n) (J + s) S ≤ 2 ^ J * ↑n ^ (-(δ / 2) * ↑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 : ℕ) :
    P.notYet (↑n) t S ≤ θ ^ t * ↑n

    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.