Documentation

RumorSpread.Growth

Growth phase #

While the informed set has size ≤ n/2, each round multiplies it by 9/8 with probability ≥ 1/8 (prob_goodRound). The exponential-moment bound expList_half_pow_goodCount — 𝔼[(1/2)^(good rounds)] ≤ (15/16)^T — is the only concentration tool of the development: one induction over rounds replaces both the stochastic domination by a binomial and the Chernoff bound.

phase1 concludes: if (9/8)^L ≥ n, the probability that the informed set is still ≤ n/2 after T₁ rounds is at most 2^L · (15/16)^T₁.

theorem RumorPush.avg_half_pow_good {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) (hI : I.Nonempty) :
(Dynamics.avg fun (r : Tgt n) => (1 / 2) ^ if goodRound I r then 1 else 0) ≤ 15 / 16

Per-round exponential moment of the good-round indicator.

theorem RumorPush.expList_half_pow_goodCount {n : ℕ} (hn : 2 ≤ n) (T : ℕ) (I : Finset (Fin n)) :
I.Nonempty → (Dynamics.expList (Tgt n) T fun (l : List (Tgt n)) => (1 / 2) ^ goodCount I l) ≤ (15 / 16) ^ T

Exponential-moment bound for adaptive trials: 𝔼[(1/2) ^ (number of good rounds in T rounds)] ≤ (15/16) ^ T.

theorem RumorPush.phase1 {n : ℕ} (hn : 2 ≤ n) (v₀ : Fin n) (L T₁ : ℕ) (hL : ↑n ≤ (9 / 8) ^ L) :
(Dynamics.expList (Tgt n) T₁ fun (l : List (Tgt n)) => if 2 * (run {v₀} l).card ≤ n then 1 else 0) ≤ 2 ^ L * (15 / 16) ^ T₁

Phase 1: if (9/8)^L ≥ n, then after T₁ rounds the informed set is still ≤ n/2 with probability at most 2^L · (15/16)^T₁.