Lower bound for push–pull on K_n: the two phases (EPI-8, Theorem 53) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version
arXiv:2303.11150), Theorem 53 (lower bound): push–pull needs log₃ n + log₂ ln n - O(1)
rounds.
- Growth (the role of Theorem 27 with
γ = 2): an uninformed node is informed with probability1 - (1 - 1/n)^{|S|} (1 - |S|/n) ≤ 2 |S| / n, so the expected number of informed nodes at most triples per round (pushPull_expect_card_le), and at leastmnodes are informed aftertrounds with probability at most3^t |S| / m(pushPull_growth_lower). - Final phase (the role of Theorem 48 with
ℓ = 2): withuuninformed nodes, each stays uninformed with probability(u/n)(1 - 1/n)^{n-u} ≥ u / (e n)(pushPull_expect_uninformed), and fewer thanu² / (2 e n)stay uninformed with probability at most4 e² n² / u³(pushPull_round_lower). From at leastn / 2uninformed nodes, informing everybody withinlog₂ ln n - r₀rounds has probabilityO(n^{-1/2})(pushPull_final_lower).
Expected number of uninformed nodes after one round of push–pull:
E[n - |S'|] = (n - |S|)(1 - 1/n)^{|S|}(1 - |S| / n).
One round of the final phase (Lemma 49 for push–pull, ℓ = 2, a = 1/e): with
u = n - |S| uninformed nodes, fewer than u² / (2 e n) nodes stay uninformed with
probability at most 4 e² n² / u³.
Final phase (Theorem 48 for push–pull, ℓ = 2): from at least n / 2 uninformed nodes,
push–pull informs all nodes within log₂ ln n - r₀ rounds with probability at most
C n^{-1/2}.