Final-phase lower bounds for pull and push–pull (EPI-8, Theorem 48) #
Round-by-round lower envelopes of the number of uninformed nodes (reach_le_envelope, from
envelope_seq_le). Pull and push–pull use the double exponential targets
g i = 2 n (1/4)^{2^i} and g i = 2 e n (1/(4e))^{2^i}, so that g 0 = n / 2 and
g (i+1) = g i ^ 2 / (2 n) (resp. g i ^ 2 / (2 e n)): the paper's ε_{j+1} = E(ε_j)/2 of
Lemma 49 with a = 1 (resp. a = 1/e). While g i ≥ n^{7/8} (that is, for
i ≤ log₂ ln n - 5) a round fails with probability at most 4 n^{-5/8} (resp.
4 e² n^{-5/8}), and t ≤ log₂ ln n ≤ 16 n^{1/8} such rounds fail with probability
O(n^{-1/2}). The exponential final phase of push is in LowerFinalPush.
Real comparisons used by every final phase #
theorem
Epidemics.Revisited.reach_le_envelope
{n : ℕ}
(P : RumorProcess n)
(g δ : ℕ → ℝ)
(hδ : ∀ (i : ℕ), 0 ≤ δ i)
(hstep :
∀ (i : ℕ) (a : Finset (Fin n)),
g i ≤ ↑n - ↑a.card → ((P.K a).prob fun (b : Finset (Fin n)) => ↑n - ↑b.card < g (i + 1)) ≤ δ i)
(t : ℕ)
(S : Finset (Fin n))
(hstart : g 0 ≤ ↑n - ↑S.card)
(hgt : 0 < g t)
:
All-informed is contained in V < g t whenever g t > 0, so the reach probability is at
most the envelope sum.