Documentation

RumorSpread.PullOneRound

One-round picture of PULL and PUSH–PULL #

Exact one-round expectations that make the classical picture of [KSSV00, §2] visible, with the partner of every caller uniform among the other n - 1 nodes (Tgt n). Write m = |I| for the informed and u = n - m for the uninformed nodes. An uninformed caller v pulls the rumor iff its callee lies in I, which has probability m / (n - 1), independently over the callers.

Counting identities #

theorem RumorPush.card_pullStep {n : ℕ} (I : Finset (Fin n)) (r : Tgt n) :
↑(pullStep I r).card = ↑I.card + ∑ v ∈ Iᶜ, if ↑(r v) ∈ I then 1 else 0

Size of a PULL round: I plus the uninformed callers whose callee is in I.

theorem RumorPush.uninformed_eq_sum {n : ℕ} {I S : Finset (Fin n)} (h : I ⊆ S) :
↑n - ↑S.card = ∑ v ∈ Iᶜ, if v ∈ S then 0 else 1

The uninformed count after a round S ⊇ I, as a sum over the nodes uninformed before.

theorem RumorPush.cast_card_compl {n : ℕ} {I : Finset (Fin n)} :
↑Iᶜ.card = ↑n - ↑I.card
theorem RumorPush.avg_tgt_call_mem {n : ℕ} (hn : 2 ≤ n) {v : Fin n} {I : Finset (Fin n)} (hv : v ∉ I) :
(Dynamics.avg fun (r : Tgt n) => if ↑(r v) ∈ I then 1 else 0) = ↑I.card / (↑n - 1)

A caller v ∉ I of a uniform round calls into I with probability |I|/(n-1).

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

Expected number of uninformed callers that pull the rumor in one round: (n - |I|) · |I|/(n-1).

theorem RumorPush.pull_prob_stuck_singleton {n : ℕ} (hn : 2 ≤ n) (v₀ : Fin n) :
(Dynamics.avg fun (r : Tgt n) => if pullStep {v₀} r = {v₀} then 1 else 0) = (1 - 1 / (↑n - 1)) ^ (n - 1)

PULL startup stalls with constant probability [KSSV00, §2]: from a single informed node v₀, a PULL round informs no new node (nobody calls v₀) with probability exactly (1 - 1/(n-1))^(n-1), which tends to 1/e.

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

Expected PULL growth (exact): each of the n - |I| uninformed nodes calls an informed node with probability |I|/(n-1); for |I| ≪ n the informed set roughly doubles in expectation [KSSV00, §2].

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

Quadratic shrinking of PULL, exact form [KSSV00, §2]: an uninformed node stays uninformed iff it calls one of the other u - 1 uninformed nodes, so with u = n - |I| the expected number of uninformed nodes after one PULL round is u (u - 1)/(n - 1).

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

Quadratic shrinking of PULL [KSSV00, §2]: with u = n - |I| uninformed nodes, the expected number of uninformed nodes after one PULL round is at most u² / n; equivalently the uninformed fraction s = u/n satisfies 𝔼 s' ≤ s².

theorem RumorPush.pushPull_avg_uninformed {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) :
(Dynamics.avg fun (r : Tgt n) => ↑n - ↑(pushPullStep I r).card) = (↑n - ↑I.card) * (↑n - ↑I.card - 1) / (↑n - 1) * (1 - 1 / (↑n - 1)) ^ I.card

One PUSH–PULL round, exact form [KSSV00, §2]: an uninformed node stays uninformed iff its own call goes to an uninformed node (probability (u - 1)/(n - 1)) and none of the |I| informed nodes calls it (probability (1 - 1/(n-1))^|I|, independent of the former). Hence the expected number of uninformed nodes after one round is u (u - 1)/(n - 1) · (1 - 1/(n-1))^|I|, with u = n - |I|.