The three phases chained, for an abstract growth process (EPI-4, Theorems 2 and 3) #
GrowthProcess step src c collects what the proofs of Lemmas 2 to 4 use about one round of a
set process: the source src is always in the next set (H1), the moment generating function
bound of bips_mgf_le (H2), the growth bound E|A'| ≥ |A| (1 + c (1 - |A|/n)) of Lemma 1
(H3), monotonicity in the current set (H4), and univ is absorbing (H5). BIPS satisfies it with
c = 1 - λ (Theorem 2) and BIPS with branching factor 1 + ρ with c = ρ₀ (1 - λ₀)
(Theorem 3).
From {src}, Lemma 2 reaches size m = ⌈4000 log n/c²⌉₊, Lemma 3 then reaches 9n/10 and
Lemma 4 infects every vertex; the phases are chained at their first hitting times
(round_first_hit). Under c ≥ 128 √(log n/n) the three lengths add up to 60000 log n/c³
(phase_schedule), and the failure probability is ≤ 3/n³ (GrowthProcess.fail_le). Restarting
from the current set every ⌈60000 log n/c³⌉₊ rounds bounds the tail sums of the infection
time (GrowthProcess.tail_sum_le_log), the paper's equation (1).
Chernoff lower tail from the moment generating function (the computation of
bips_chernoff_lower, for any real observable X of one round): if
E e^{-ψ X} ≤ exp(-(1 - e^{-ψ}) E X) for every ψ, μ ≤ E X and 0 < δ < 1, then
P(X ≤ (1 - δ) μ) ≤ exp(-δ² μ/2).
The one-round hypotheses of the generic phase lemmas: (H1) the source is always in the next
set, (H2) the moment generating function bound, (H3) growth E|A'| ≥ |A| (1 + c (1 - |A|/n)),
(H4) monotonicity, (H5) univ is absorbing.
Instances For
The Chernoff lower tail (H2'), from the moment generating function bound.
The three phases chained (proof of Theorem 2, generic form). If
c ≥ 128 √(log n/n) and T ≥ 60000 log n/c³, the process started from {src} has not covered
V at time T with probability at most 3/n³.
Restarting (equation (1), generic form): if from {src} the failure probability at
time T₀ > 0 is at most 1/2, then every partial tail sum
∑_{s < H} P(A_s ≠ V) is at most 2 T₀. From a state A ∋ src the process dominates the one
restarted from {src}, so P(A_{s + T₀} ≠ V) ≤ P(A_s ≠ V)/2.
The gap hypothesis c ≥ 128 √(log n/n) with c ≤ 1 forces n ≥ 16385 (so 3/n² ≤ 1/2
in the restarting arguments).
Tail sums of the infection time (generic form of Theorem 2 in expectation): under
c ≥ 128 √(log n/n), every partial sum ∑_{s < H} P(A_s ≠ V) from {src} is at most
130000 log n/c³.