Saturation phase #
Once the informed set has size ≥ n/2 (which persists by monotonicity), the
expected number of uninformed nodes contracts by a factor 2/3 per round
(avg_uninformed_le); iterating gives saturation. Combined with Markov's
inequality — which here is just a pointwise bound pushed through
expList_le_expList — this finishes the proof in Main.lean.