Documentation

Epidemics.Revisited.LowerPush

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.

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

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

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

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

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

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

theorem Epidemics.Revisited.push_round_lower {n : ℕ} (S : Finset (Fin n)) {v : ℝ} (hv : 4 ≤ v) (hvu : v ≤ ↑n - ↑S.card) :
(((push n).K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < v / Real.exp 1 - v ^ (3 / 4)) ≤ v ^ (-(1 / 2))

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

theorem Epidemics.Revisited.push_final_lower :
∃ (C : ℝ) (κ : ℝ), 0 < κ ∧ ∀ (n : ℕ) (S : Finset (Fin n)) (t : ℕ), 1 - (push n).notYet (↑n) t S ≤ C * Real.exp (κ * (↑t - Real.log (↑n - ↑S.card)))

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.