Phase calculus with potentials (EPI-8, double exponential shrinking) #
Generic finite-time tools for Theorem 43:
closed_of_superset: a region closed under informing more nodes is closed under the rounds, so the core's contraction on a closed region (Dynamics.Kernel.iterate_le_pow_of_closed) applies: a potential that contracts byθin one round on the region contracts byθ^tintrounds.notYet_phase_le: a phase calculus (the core'sDynamics.Kernel.iterate_outside_le_of_phases). Given thresholdsy 0, …, y Jon the number of uninformed nodes, if from at mosty juninformed nodes one round fails to reach at mosty (j + 1)with probability at mostq, then from at mosty 0uninformed nodes, more thany Jremain aftertrounds with probability at most(q + 1/λ)^t λ^J, for everyλ ≥ 1. The potential isλ^{J - j}in phasej(the last phase reached), and0from phaseJon; it replaces the stochastic domination by sums of geometric variables (Lemma 47).notYet_finish_le: if every uninformed node stays uninformed with probability at mostθ, then the expected number of uninformed nodes contracts byθper round, and by Markov's inequality some node is still uninformed aftertrounds with probability at mostθ^t (n - |S|).prob_deficit_gt_chebandprob_deficit_gt_markov: the one-round failure probabilities, by Chebyshev's inequality with the variance bound of Lemma 9, or by Markov's inequality.
Phase calculus: from at most y 0 uninformed nodes, more than y J remain after t rounds
with probability at most (q + 1/λ)^t λ^J. The core's Kernel.iterate_outside_le_of_phases
with the phases A j = "at most y j uninformed nodes", closed under the rounds since the
informed set only grows.
Finishing: if every uninformed node stays uninformed with probability at most θ in every
round started with at most U uninformed nodes, then from such a state some node is still
uninformed after t rounds with probability at most θ^t (n - |S|).
Chebyshev for one round: if the expected number of uninformed nodes after the round is at
most μ < z and distinct uninformed nodes have covariance at most c₀ ≥ 0, then more than z
nodes stay uninformed with probability at most (u + c₀ u²) / (z - μ)², u = n - |S|.
Markov for one round: more than z > 0 nodes stay uninformed with probability at most
μ / z when their expected number is at most μ.
The expected number of uninformed nodes after a round where each uninformed node stays
uninformed with probability at most s.