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.
The push target as a function of the fourth root q of the reference level q^4.
Equations
- Epidemics.Revisited.pushTarget q = q ^ 3 * (q - 20)
Instances For
For q ≥ 40 the target is at least half the reference level.
The key step of the envelope: g(q e^{-1/4}) ≤ g(q) / e - g(q)^{3/4} for q ≥ 20.
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.
Fourth root of the reference level after i rounds: q_i = exp((L - i) / 4), where
L = ln u.
Equations
- Epidemics.Revisited.pushRoot L i = Real.exp ((L - ↑i) / 4)