Documentation

Epidemics.Revisited.LowerFinal

Final-phase lower bounds for pull and push–pull (EPI-8, Theorem 48) #

Round-by-round lower envelopes of the number of uninformed nodes (reach_le_envelope, from envelope_seq_le). Pull and push–pull use the double exponential targets g i = 2 n (1/4)^{2^i} and g i = 2 e n (1/(4e))^{2^i}, so that g 0 = n / 2 and g (i+1) = g i ^ 2 / (2 n) (resp. g i ^ 2 / (2 e n)): the paper's ε_{j+1} = E(ε_j)/2 of Lemma 49 with a = 1 (resp. a = 1/e). While g i ≥ n^{7/8} (that is, for i ≤ log₂ ln n - 5) a round fails with probability at most 4 n^{-5/8} (resp. 4 e² n^{-5/8}), and t ≤ log₂ ln n ≤ 16 n^{1/8} such rounds fail with probability O(n^{-1/2}). The exponential final phase of push is in LowerFinalPush.

Real comparisons used by every final phase #

theorem Epidemics.Revisited.logb_two_le_two_mul {x : ℝ} (hx : 0 < x) :
Real.logb 2 x ≤ 2 * x

log₂ x ≤ 2 x for x > 0, from ln x ≤ x and ln 2 ≥ 1/2.

theorem Epidemics.Revisited.log_le_eight_rpow {n : ℕ} (hn : 0 < ↑n) :
Real.log ↑n ≤ 8 * ↑n ^ (1 / 8)
theorem Epidemics.Revisited.t_le_sixteen_rpow {n t : ℕ} (hn : 0 < ↑n) (hlog : 0 < Real.log ↑n) (ht : ↑t ≤ Real.logb 2 (Real.log ↑n)) :
↑t ≤ 16 * ↑n ^ (1 / 8)
theorem Epidemics.Revisited.quarter_pow_ge {n i : ℕ} (hn : 0 < ↑n) (hlog : 0 ≤ Real.log ↑n) (hi : 2 ^ i ≤ Real.log ↑n / 32) :
↑n ^ (-(1 / 8)) ≤ (1 / 4) ^ 2 ^ i

(1/4)^{2^i} ≥ n^{-1/8} once 2^i ≤ ln n / 32.

theorem Epidemics.Revisited.inv_four_exp_pow_ge {n i : ℕ} (hn : 0 < ↑n) (hlog : 0 ≤ Real.log ↑n) (hi : 2 ^ i ≤ Real.log ↑n / 32) :
↑n ^ (-(1 / 8)) ≤ (1 / (4 * Real.exp 1)) ^ 2 ^ i
theorem Epidemics.Revisited.two_pow_le_log_div {n t i : ℕ} (hlog : 0 < Real.log ↑n) (ht : ↑t + 5 ≤ Real.logb 2 (Real.log ↑n)) (hi : i ≤ t) :
2 ^ i ≤ Real.log ↑n / 32

2^i ≤ ln n / 32 for every i ≤ t, once t + 5 ≤ log₂ ln n.

theorem Epidemics.Revisited.n_sq_div_cube_le {n : ℕ} {u : ℝ} (hn : 0 < ↑n) (hu : ↑n ^ (7 / 8) ≤ u) :
↑n ^ 2 / u ^ 3 ≤ ↑n ^ (-(5 / 8))
theorem Epidemics.Revisited.one_sub_below_le_deficit {n : ℕ} {g : ℝ} (hg : 0 < g) (T : Finset (Fin n)) :
1 - below (↑n) T ≤ if ↑n - ↑T.card < g then 1 else 0
theorem Epidemics.Revisited.reach_le_envelope {n : ℕ} (P : RumorProcess n) (g δ : ℕ → ℝ) (hδ : ∀ (i : ℕ), 0 ≤ δ i) (hstep : ∀ (i : ℕ) (a : Finset (Fin n)), g i ≤ ↑n - ↑a.card → ((P.K a).prob fun (b : Finset (Fin n)) => ↑n - ↑b.card < g (i + 1)) ≤ δ i) (t : ℕ) (S : Finset (Fin n)) (hstart : g 0 ≤ ↑n - ↑S.card) (hgt : 0 < g t) :
1 - P.notYet (↑n) t S ≤ ∑ i ∈ Finset.range t, δ i

All-informed is contained in V < g t whenever g t > 0, so the reach probability is at most the envelope sum.

Pull: g i = 2 n (1/4)^{2^i} #

noncomputable def Epidemics.Revisited.pullTarget (n i : ℕ) :
Equations
Instances For
    theorem Epidemics.Revisited.pullTarget_pos {n : ℕ} (hn : 0 < n) (i : ℕ) :
    theorem Epidemics.Revisited.pullTarget_succ {n : ℕ} (hn : n ≠ 0) (i : ℕ) :
    pullTarget n (i + 1) = pullTarget n i ^ 2 / (2 * ↑n)
    theorem Epidemics.Revisited.pullTarget_ge_rpow {n i : ℕ} (hn : 0 < ↑n) (hlog : 0 ≤ Real.log ↑n) (hi : 2 ^ i ≤ Real.log ↑n / 32) :
    ↑n ^ (7 / 8) ≤ pullTarget n i
    noncomputable def Epidemics.Revisited.pullFail (n i : ℕ) :
    Equations
    Instances For
      theorem Epidemics.Revisited.pull_step {n : ℕ} (hn : 0 < n) (i : ℕ) (a : Finset (Fin n)) (ha : pullTarget n i ≤ ↑n - ↑a.card) :
      (((pull n).K a).prob fun (b : Finset (Fin n)) => ↑n - ↑b.card < pullTarget n (i + 1)) ≤ pullFail n i
      theorem Epidemics.Revisited.pull_final_lower_explicit (n : ℕ) (hn : 3 ≤ n) (S : Finset (Fin n)) (hS : 2 * S.card ≤ n) (t : ℕ) (ht : ↑t + 5 ≤ Real.logb 2 (Real.log ↑n)) :
      1 - (pull n).notYet (↑n) t S ≤ 128 * ↑n ^ (-(1 / 2))

      Final phase of pull with explicit constants C = 128, r₀ = 5, N = 3.

      Push–pull: g i = 2 e n (1/(4e))^{2^i} #

      noncomputable def Epidemics.Revisited.pushPullTarget (n i : ℕ) :
      Equations
      Instances For
        theorem Epidemics.Revisited.pushPullTarget_succ {n : ℕ} (hn : n ≠ 0) (i : ℕ) :
        pushPullTarget n (i + 1) = pushPullTarget n i ^ 2 / (2 * Real.exp 1 * ↑n)
        theorem Epidemics.Revisited.pushPullTarget_ge_rpow {n i : ℕ} (hn : 0 < ↑n) (hlog : 0 ≤ Real.log ↑n) (hi : 2 ^ i ≤ Real.log ↑n / 32) :
        ↑n ^ (7 / 8) ≤ pushPullTarget n i
        noncomputable def Epidemics.Revisited.pushPullFail (n i : ℕ) :
        Equations
        Instances For
          theorem Epidemics.Revisited.pushPull_step {n : ℕ} (hn : 0 < n) (i : ℕ) (a : Finset (Fin n)) (ha : pushPullTarget n i ≤ ↑n - ↑a.card) :
          (((pushPull n).K a).prob fun (b : Finset (Fin n)) => ↑n - ↑b.card < pushPullTarget n (i + 1)) ≤ pushPullFail n i
          theorem Epidemics.Revisited.pushPull_final_lower_explicit (n : ℕ) (hn : 3 ≤ n) (S : Finset (Fin n)) (hS : 2 * S.card ≤ n) (t : ℕ) (ht : ↑t + 5 ≤ Real.logb 2 (Real.log ↑n)) :
          1 - (pushPull n).notYet (↑n) t S ≤ 128 * Real.exp 1 ^ 2 * ↑n ^ (-(1 / 2))

          Final phase of push–pull with explicit constants C = 128 e², r₀ = 5, N = 3.

          theorem Epidemics.Revisited.pull_final_lower_proof :
          ∃ (C : ℝ) (r₀ : ℕ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), 2 * S.card ≤ n → ∀ (t : ℕ), ↑t + ↑r₀ ≤ Real.logb 2 (Real.log ↑n) → 1 - (pull n).notYet (↑n) t S ≤ C * ↑n ^ (-(1 / 2))
          theorem Epidemics.Revisited.pushPull_final_lower_proof :
          ∃ (C : ℝ) (r₀ : ℕ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), 2 * S.card ≤ n → ∀ (t : ℕ), ↑t + ↑r₀ ≤ Real.logb 2 (Real.log ↑n) → 1 - (pushPull n).notYet (↑n) t S ≤ C * ↑n ^ (-(1 / 2))