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.
pull_prob_stuck_singleton— the startup of PULL is unpredictable [KSSV00, §2]: from one informed node the round informs nobody with probability(1 - 1/(n-1))^(n-1) ≈ 1/e.pull_avg_card_step— expected PULL growthm + u · m/(n-1): whilem ≪ nthe informed set roughly doubles in expectation.pull_avg_uninformed,pull_avg_uninformed_le— the quadratic shrinking of PULL [KSSV00, §2]: the expected number of uninformed nodes after one round is exactlyu (u - 1)/(n - 1) ≤ u² / n, i.e. the uninformed fractions = u/nsatisfies𝔼 s' ≤ s².pushPull_avg_uninformed— PUSH–PULL combines both effects: an uninformed node stays uninformed iff it pulls from an uninformed node and is pushed to by nobody, so the expected number of uninformed nodes isu (u - 1)/(n - 1) · (1 - 1/(n-1))^m(form ≪ nthis is≈ n - 3m, the tripling behindlog₃ nin [KSSV00, Thm 2.1]).
Counting identities #
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.
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].
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).
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².
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|.