Documentation

RumorSpread.PullGood

The two one-round inputs of the PULL proof #

notAllOf_le_two_div (PullPhases.lean) needs two facts about the PULL step:

theorem RumorPush.pull_avg_new_sq_le {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) :
(Dynamics.avg fun (r : Tgt n) => (∑ v ∈ Iᶜ, if ↑(r v) ∈ I then 1 else 0) ^ 2) ≤ (↑n - ↑I.card) * (↑I.card / (↑n - 1)) + ((↑n - ↑I.card) * (↑I.card / (↑n - 1))) ^ 2

Second moment of the number of uninformed callers that call into I: 𝔼X² ≤ μ + μ² with μ = (n - |I|) · |I|/(n-1).

theorem RumorPush.pull_prob_goodRound {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) (hI : I.Nonempty) :
1 / 8 ≤ Dynamics.avg fun (r : Tgt n) => if goodRoundOf pullStep I r then 1 else 0

A PULL round is good with probability at least 1/8 (second-moment argument).

theorem RumorPush.pull_avg_uninformed_contract {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) (hI : n ≤ 2 * I.card) :
(Dynamics.avg fun (r : Tgt n) => ↑n - ↑(pullStep I r).card) ≤ 2 / 3 * (↑n - ↑I.card)

PULL contraction above one half: once |I| ≥ n/2, the expected number of uninformed nodes shrinks by a factor 2/3 in one round.