The two-phase argument for an arbitrary inflationary spreading step #
The PUSH proof (Growth.lean, Saturation.lean, Main.lean) only uses two one-round facts about
step: a round is good (grows the informed set by 9/8, or starts above n/2) with
probability ≥ 1/8, and above n/2 the expected number of uninformed nodes contracts by 2/3.
This file runs the same argument for any step f : Finset (Fin n) → α → Finset (Fin n) that is
inflationary (I ⊆ f I a), driven by i.i.d. uniform rounds a : α, with trajectories
l.foldl f I:
pow_goodCountOf_mul_card_le— deterministic growth along good rounds;expList_half_pow_goodCountOf—𝔼[(1/2)^(good rounds)] ≤ (15/16)^T;phase1Of,saturationOf— the two phases;notAllOf_le— gluing, asprNotAllInformed_le;notAllOf_antitone— more rounds never hurt;notAllOf_le_two_div— with the constants ofMain.lean, all nodes are informed after⌈160 log n⌉rounds with probability≥ 1 - 2/n.
It is instantiated for PULL in PullMain.lean.
A round a is good for the step f if it multiplies the informed set by at least 9/8,
or if more than half of the nodes are already informed (goodRound for a general step).
Instances For
The number of good rounds along a trajectory of the step f.
Equations
- RumorPush.goodCountOf f I [] = 0
- RumorPush.goodCountOf f I (a :: l) = (if RumorPush.goodRoundOf f I a then 1 else 0) + RumorPush.goodCountOf f (f I a) l
Instances For
Deterministic growth: if the final informed set is at most n/2, each good round
multiplied the informed set by 9/8 (as pow_goodCount_mul_card_le_card_run).
Exponential-moment bound for adaptive trials (as expList_half_pow_goodCount):
𝔼[(1/2) ^ (number of good rounds in T rounds)] ≤ (15/16) ^ T.
Phase 1 (as phase1): 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₁.
Phase 2 (as saturation): starting above half, the expected number of uninformed
nodes after T further rounds is at most (2/3)^T · (n - |I|).
Gluing the two phases (as prNotAllInformed_le).
More rounds never hurt: for an inflationary step, the probability that not all nodes are informed is antitone in the number of rounds.
The two-phase theorem for a general step: if good rounds have probability ≥ 1/8 and
the expected uninformed count contracts by 2/3 above half, then after ⌈160 log n⌉ rounds
started from one informed node, not all nodes are informed with probability at most 2/n.