One-round lower bounds (EPI-8, Lemmas 39 and 49) #
Chebyshev on the lower tail of the number of uninformed nodes, the bound
(1 - 1/n)^k ≥ e^{-1} for k + 1 ≤ n, and the one-round lemmas for push, pull and push–pull.
theorem
Epidemics.Revisited.prob_deficit_lt_cheb
{n : ℕ}
(P : RumorProcess n)
(S : Finset (Fin n))
{c₀ μ z : ℝ}
(hc₀ : 0 ≤ c₀)
(hcov : ∀ x ∉ S, ∀ y ∉ S, x ≠ y → P.cov S x y ≤ c₀)
(hμ : μ ≤ (P.K S).expect fun (T : Finset (Fin n)) => ↑n - ↑T.card)
(hz : z < μ)
:
Lower tail of the deficit, the mirror of prob_deficit_gt_cheb. If μ ≤ E[n - |T|] and
z < μ, and distinct uninformed nodes have covariance at most c₀ ≥ 0, then
P[n - |T| < z] ≤ (u + c₀ u²) / (μ - z)² with u = n - |S|.
One round of push–pull (Lemma 49, a = 1/e): P[u' < u²/(2 e n)] ≤ 4 e² n² / u³.