Documentation

Epidemics.Revisited.LowerRound

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 < μ) :
((P.K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < z) ≤ (↑n - ↑S.card + c₀ * (↑n - ↑S.card) ^ 2) / (μ - z) ^ 2

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|.

theorem Epidemics.Revisited.one_sub_inv_pow_ge_exp_neg {n k : ℕ} (hk : k + 1 ≤ n) :
Real.exp (-1) ≤ (1 - 1 / ↑n) ^ k

(1 - 1/n)^k ≥ e^{-1} whenever k + 1 ≤ n (Corollary 17, for 1 ≤ u uninformed nodes, so the exponent n - u is at most n - 1).

theorem Epidemics.Revisited.exp_le_two_mul_fourth {v : ℝ} (hv : 4 ≤ v) :
Real.exp 1 ≤ 2 * v ^ (1 / 4)

v ≥ 4 gives v^{1/4} ≥ √2 ≥ e / 2.

theorem Epidemics.Revisited.push_level_algebra {v w : ℝ} (hv : 4 ≤ v) (hw : 0 ≤ w) :
(v + w) / (w / Real.exp 1 + v ^ (3 / 4)) ^ 2 ≤ v ^ (-(1 / 2))

With a = v^{1/4} and w ≥ 0, (v + w) / (w/e + v^{3/4})² ≤ v^{-1/2}.

theorem Epidemics.Revisited.push_round_lower_proof {n : ℕ} (S : Finset (Fin n)) {v : ℝ} (hv : 4 ≤ v) (hvu : v ≤ ↑n - ↑S.card) :
(((push n).K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < v / Real.exp 1 - v ^ (3 / 4)) ≤ v ^ (-(1 / 2))

One round of push (Lemma 39): P[u' < v/e - v^{3/4}] ≤ v^{-1/2} for 4 ≤ v ≤ u.

theorem Epidemics.Revisited.prob_deficit_neg_eq_zero {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) :
((P.K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < 0) = 0

The event n - |T| < 0 is impossible.

theorem Epidemics.Revisited.pull_round_lower_proof {n : ℕ} (S : Finset (Fin n)) :
(((pull n).K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < (↑n - ↑S.card) ^ 2 / (2 * ↑n)) ≤ 4 * ↑n ^ 2 / (↑n - ↑S.card) ^ 3

One round of pull (Lemma 49, a = 1): P[u' < u²/(2n)] ≤ 4 n² / u³.

theorem Epidemics.Revisited.pushPull_round_lower_proof {n : ℕ} (S : Finset (Fin n)) :
(((pushPull n).K S).prob fun (T : Finset (Fin n)) => ↑n - ↑T.card < (↑n - ↑S.card) ^ 2 / (2 * Real.exp 1 * ↑n)) ≤ 4 * Real.exp 1 ^ 2 * ↑n ^ 2 / (↑n - ↑S.card) ^ 3

One round of push–pull (Lemma 49, a = 1/e): P[u' < u²/(2 e n)] ≤ 4 e² n² / u³.