Documentation

Epidemics.Revisited.LowerPull

Lower bound for pull on K_n: the two phases (EPI-8, Theorem 52) #

Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version arXiv:2303.11150), Theorem 52 (lower bound): pull needs log₂ n + log₂ ln n - O(1) rounds.

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

One round of pull at most doubles the expected number of informed nodes: E|S'| = |S| + (n - |S|) |S| / n ≤ 2|S|.

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

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

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

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

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

One round of the final phase (Lemma 49 for pull, ℓ = 2, a = 1): with u = n - |S| uninformed nodes, fewer than u² / (2n) nodes stay uninformed with probability at most 4 n² / u³.

theorem Epidemics.Revisited.pull_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 - (pull n).notYet (↑n) t S ≤ C * ↑n ^ (-(1 / 2))

Final phase (Theorem 48 for pull, ℓ = 2): from at least n / 2 uninformed nodes, pull informs all nodes within log₂ ln n - r₀ rounds with probability at most C n^{-1/2}.