Documentation

Epidemics.Revisited.LowerFinalPush

Final phase of push (EPI-8, Theorem 38 with ρ = 1) #

Round-by-round lower envelope of the number of uninformed nodes along the explicit targets g i = q_i^3 (q_i - 20), where q_i = (u e^{-i})^{1/4} = exp((ln u - i) / 4) is the fourth root of the reference level u e^{-i} and u is the initial number of uninformed nodes (pushRoot, pushTarget). The one-round lemma push_round_lower_proof at the level v = g i gives the step g (i + 1) ≤ g i / e - (g i)^{3/4} (pushTarget_step; the slack constant 20 absorbs the loss (g i)^{3/4} ≤ q_i^3 and needs only e^{1/4} ≥ 5/4 and e ≤ 3). While q_i ≥ 40, the failure probability of round i is at most 2 / q_i^2, and these sum to at most 4 e^{(t - ln u)/2}. When q_t < 40, the claimed bound 1600 e^{(t - ln u)/2} = 1600 / q_t^2 exceeds 1.

noncomputable def Epidemics.Revisited.pushTarget (q : ℝ) :

The push target as a function of the fourth root q of the reference level q^4.

Equations
Instances For
    theorem Epidemics.Revisited.pushTarget_ge_half {q : ℝ} (hq : 40 ≤ q) :
    q ^ 4 / 2 ≤ pushTarget q

    For q ≥ 40 the target is at least half the reference level.

    theorem Epidemics.Revisited.pushTarget_step {q : ℝ} (hq : 20 ≤ q) :

    The key step of the envelope: g(q e^{-1/4}) ≤ g(q) / e - g(q)^{3/4} for q ≥ 20.

    theorem Epidemics.Revisited.rpow_neg_half_le {q v : ℝ} (hq : 0 < q) (hv : q ^ 4 / 4 ≤ v) :
    v ^ (-(1 / 2)) ≤ 2 / q ^ 2

    v^{-1/2} ≤ 2 / q^2 whenever q^4 / 4 ≤ v.

    theorem Epidemics.Revisited.push_target_round {n : ℕ} {q : ℝ} (hq : 40 ≤ q) (a : Finset (Fin n)) (ha : pushTarget q ≤ ↑n - ↑a.card) :
    (((push n).K a).prob fun (b : Finset (Fin n)) => ↑n - ↑b.card < pushTarget (q / Real.exp (1 / 4))) ≤ 2 / q ^ 2

    One round along the targets: from at least g(q) uninformed nodes (q ≥ 40), fewer than g(q e^{-1/4}) stay uninformed with probability at most 2 / q^2.

    noncomputable def Epidemics.Revisited.pushRoot (L : ℝ) (i : ℕ) :

    Fourth root of the reference level after i rounds: q_i = exp((L - i) / 4), where L = ln u.

    Equations
    Instances For
      theorem Epidemics.Revisited.pushRoot_succ (L : ℝ) (i : ℕ) :
      pushRoot L (i + 1) = pushRoot L i / Real.exp (1 / 4)
      theorem Epidemics.Revisited.pushRoot_anti (L : ℝ) {i j : ℕ} (hij : i ≤ j) :
      theorem Epidemics.Revisited.two_div_pushRoot_sq (L : ℝ) (i : ℕ) :
      2 / pushRoot L i ^ 2 = 2 * Real.exp (-L / 2) * Real.exp (1 / 2) ^ i
      theorem Epidemics.Revisited.push_final_lower_explicit (n : ℕ) (S : Finset (Fin n)) (t : ℕ) :
      1 - (push n).notYet (↑n) t S ≤ 1600 * Real.exp (1 / 2 * (↑t - Real.log (↑n - ↑S.card)))

      Final phase of push with explicit constants C = 1600, κ = 1/2.