Documentation

Epidemics.Revisited.LowerPushPull

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.

theorem Epidemics.Revisited.pushPull_expect_card_le {n : ℕ} (S : Finset (Fin n)) :
(((pushPull n).K S).expect fun (T : Finset (Fin n)) => ↑T.card) ≤ 3 * ↑S.card

One round of push–pull at most triples the expected number of informed nodes: p_k = 1 - (1 - 1/n)^k (1 - k/n) ≤ 2k/n, so E|S'| ≤ 3|S|.

theorem Epidemics.Revisited.pushPull_expect_uninformed {n : ℕ} (S : Finset (Fin n)) :
(((pushPull n).K S).expect fun (T : Finset (Fin n)) => ↑n - ↑T.card) = (↑n - ↑S.card) * ((1 - 1 / ↑n) ^ S.card * (1 - ↑S.card / ↑n))

Expected number of uninformed nodes after one round of push–pull: E[n - |S'|] = (n - |S|)(1 - 1/n)^{|S|}(1 - |S| / n).

theorem Epidemics.Revisited.pushPull_growth_lower {n : ℕ} {m : ℝ} (hm : 0 < m) (t : ℕ) (S : Finset (Fin n)) :
1 - (pushPull n).notYet m t S ≤ 3 ^ t * ↑S.card / m

Growth phase (Theorem 27 for push–pull, first-moment form): at least m nodes are informed after t rounds with probability at most 3^t |S| / m.

theorem Epidemics.Revisited.pushPull_round_lower {n : ℕ} (S : Finset (Fin n)) :
(((pushPull n).K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < (↑n - ↑S.card) ^ 2 / (2 * Real.exp 1 * ↑n)) ≤ 4 * Real.exp 1 ^ 2 * ↑n ^ 2 / (↑n - ↑S.card) ^ 3

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³.

theorem Epidemics.Revisited.pushPull_final_lower :
∃ (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))

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}.