The two one-round inputs of the PULL proof #
notAllOf_le_two_div (PullPhases.lean) needs two facts about the PULL step:
pull_prob_goodRound— a PULL round is good (grows the informed set by9/8, or starts aboven/2) with probability≥ 1/8. Unlike PUSH, a PULL round can inform many more than|I|new nodes, so the reverse-Markov argument ofprob_goodRounddoes not apply. We use a second moment instead: the numberXof uninformed callers that call intoIhas meanμ = (n - m) m/(n-1) ≥ max(m/2, 1/2)and, the calls being pairwise independent,𝔼X² ≤ μ + μ²(pull_avg_new_sq_le, from the sharedDynamics.avg_sq_sum_le_of_pairwise). The shared one-sided Paley–Zygmund boundDynamics.avg_pz_one_sidedatθ = 1/4then givesP(X > μ/4) ≥ (9/16) μ²/(μ + μ²) ≥ 3/16, andX > μ/4 ≥ |I|/8makes the round good.pull_avg_uninformed_contract— above half, the expected uninformed count contracts by2/3(from the exact formulapull_avg_uninformed; the true factor is≤ 1/2).
Second moment of the number of uninformed callers that call into I:
𝔼X² ≤ μ + μ² with μ = (n - |I|) · |I|/(n-1).