Lower bound for push on K_n: the two phases (EPI-8, Theorem 51) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version
arXiv:2303.11150), Theorem 51 (lower bound): push needs log₂ n + ln n - O(1) rounds.
- Growth (the role of Theorem 27 with
γ = 1): every informed node informs at most one new node per round, so the expected number of informed nodes at most doubles per round (push_expect_card_le), and at leastmnodes are informed aftertrounds with probability at most2^t |S| / m(push_growth_lower). - Final phase (the role of Theorem 38 with
ρ = 1): an uninformed node stays uninformed in a round with probability(1 - 1/n)^{|S|} ≥ e^{-1}(push_expect_uninformed), and the numberuof uninformed nodes concentrates, so that it falls belowv / e - v^{3/4}(any4 ≤ v ≤ u) in one round with probability at mostv^{-1/2}(push_round_lower). Hence informing all ofuuninformed nodes withinln u - rrounds has probability at mostC e^{-κ r}(push_final_lower).
theorem
Epidemics.Revisited.push_round_lower
{n : ℕ}
(S : Finset (Fin n))
{v : ℝ}
(hv : 4 ≤ v)
(hvu : v ≤ ↑n - ↑S.card)
:
One round of the final phase (Lemma 39 for push, with A = 1, B = 1/4), at any level
v ∈ [4, u]: with u = n - |S| uninformed nodes, fewer than v / e - v^{3/4} nodes stay
uninformed with probability at most v^{-1/2}.
Final phase (Theorem 38 for push, ρ = 1): from u = n - |S| uninformed nodes, push
informs all nodes within t rounds with probability at most C e^{κ (t - ln u)}, that is,
P[T(|S|, n) ≤ ln u - r] ≤ C e^{-κ r}. Uniform in n and in the starting set.