One-round estimates #
The only place in the development where a probability is computed rather
than estimated: for u ∉ I, the probability that u is not contacted in one
round is exactly (1 - 1/(n-1)) ^ |I| (avg_not_contacted), by counting
round configurations coordinate-by-coordinate.
From it we derive the three estimates of Section 4 of the paper:
avg_card_step— the exact expected size ofstep I r;prob_goodRound— a good round has probability≥ 1/8(expected growth + reverse Markov);avg_uninformed_le— above half, the expected number of uninformed nodes contracts by2/3.