Documentation

Epidemics.Revisited.LowerTotal

Total time: lower tails and expectations (EPI-8, Theorems 51 to 53, lower bounds) #

The two phases are joined at a fixed time with reach_add_le (m' = n / 2):

When t* = 0, the reach probability is 0, since one informed node is not everybody.

From lower tails to expectations #

theorem Epidemics.Revisited.sum_notYet_ge_of_tail {n : ℕ} (P : RumorProcess n) {m A κ : ℝ} (hA : 0 ≤ A) (hκ : 0 < κ) (t₀ : ℕ) (S : Finset (Fin n)) (h : ∀ (r : ℕ), 1 - P.notYet m (t₀ - r) S ≤ A * Real.exp (-κ * ↑r)) {R : ℕ} (hR : t₀ ≤ R) :
↑t₀ - A / (1 - Real.exp (-κ)) ≤ ∑ t ∈ Finset.range R, P.notYet m t S

Mirror of sum_notYet_le_of_tail: if finishing r rounds before t₀ has probability at most A e^{-κ r}, every partial sum of the tail series with at least t₀ terms is at least t₀ - A / (1 - e^{-κ}).

theorem Epidemics.Revisited.lower_expect_of_tail (Pf : (n : ℕ) → RumorProcess n) (X Y : ℕ → ℝ) {A κ : ℝ} (hA : 0 ≤ A) (hκ : 0 < κ) (N : ℕ) (htail : ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (r : ℕ), 1 - (Pf n).notYet (↑n) (⌊X n⌋₊ + ⌊Y n⌋₊ - r) S ≤ A * Real.exp (-κ * ↑r)) (hX : ∀ (n : ℕ), N ≤ n → 0 ≤ X n) (hY : ∀ (n : ℕ), N ≤ n → 0 ≤ Y n) :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (R : ℕ), X n + Y n ≤ ↑R → X n + Y n - B ≤ ∑ t ∈ Finset.range R, (Pf n).notYet (↑n) t S

Expectation form of a lower tail at time ⌊X⌋ + ⌊Y⌋: every partial sum of the tail series with at least X + Y terms is at least X + Y - B.

Real-number helpers #

theorem Epidemics.Revisited.pow_floor_logb_le {ρ x : ℝ} (hρ : 1 < ρ) (hx : 1 ≤ x) :

r ≤ 2 log₂ x gives (ln 2 / 2) r ≤ ln x.

theorem Epidemics.Revisited.inv_le_exp_of_log {x r : ℝ} (hx : 0 < x) (h : Real.log 2 / 2 * r ≤ Real.log x) :
1 / x ≤ Real.exp (-(Real.log 2 / 2) * r)
theorem Epidemics.Revisited.rpow_neg_half_le_exp {x r : ℝ} (hx : 0 < x) (h : Real.log 2 / 2 * r ≤ Real.log x) :
x ^ (-(1 / 2)) ≤ Real.exp (-(Real.log 2 / 4) * r)
theorem Epidemics.Revisited.div_half_le_of_mul {x p q K e : ℝ} (hx : 0 < x) (hp : 0 ≤ p) (he : 0 ≤ e) (hpq : p * q ≤ x * K) (hqe : 1 ≤ q * e) :
p / (x / 2) ≤ 2 * K * e

p / (x / 2) ≤ 2 K e from p q ≤ x K and q e ≥ 1.

theorem Epidemics.Revisited.exp_le_pow_of_half {ρ r : ℝ} {k : ℕ} (hρ : 2 ≤ ρ) (hk : r / 2 ≤ ↑k) :
Real.exp (Real.log 2 / 2 * r) ≤ ρ ^ k

exp((ln 2 / 2) r) ≤ ρ^k whenever ρ ≥ 2 and k ≥ r / 2.

theorem Epidemics.Revisited.one_sub_notYet_zero {n : ℕ} {P : RumorProcess n} (hn : 2 ≤ n) {S : Finset (Fin n)} (hS : S.card = 1) :
1 - P.notYet (↑n) 0 S = 0

One informed node out of n ≥ 2 is not everybody.

Pull and push–pull: double exponential final phase #

theorem Epidemics.Revisited.double_tail_generic (Pf : (n : ℕ) → RumorProcess n) {ρ C : ℝ} (hρ : 2 ≤ ρ) (hC : 0 ≤ C) (r₀ N₀ : ℕ) (hgrowth : ∀ (n : ℕ) (m : ℝ), 0 < m → ∀ (t : ℕ) (S : Finset (Fin n)), 1 - (Pf n).notYet m t S ≤ ρ ^ t * ↑S.card / m) (hfinal : ∀ (n : ℕ), N₀ ≤ n → ∀ (S : Finset (Fin n)), 2 * S.card ≤ n → ∀ (t : ℕ), ↑t + ↑r₀ ≤ Real.logb 2 (Real.log ↑n) → 1 - (Pf n).notYet (↑n) t S ≤ C * ↑n ^ (-(1 / 2))) :
∃ (A : ℝ) (κ : ℝ), 0 ≤ A ∧ 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (r : ℕ), 1 - (Pf n).notYet (↑n) (⌊Real.logb ρ ↑n⌋₊ + ⌊Real.logb 2 (Real.log ↑n)⌋₊ - r) S ≤ A * Real.exp (-κ * ↑r)

Lower tail for a protocol whose growth multiplies the expected number of informed nodes by at most ρ ≥ 2 and whose final phase (from at least n / 2 uninformed nodes, within log₂ ln n - r₀ rounds) succeeds with probability at most C n^{-1/2}.

theorem Epidemics.Revisited.pull_tail_explicit :
∃ (A : ℝ) (κ : ℝ), 0 ≤ A ∧ 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (r : ℕ), 1 - (pull n).notYet (↑n) (⌊Real.logb 2 ↑n⌋₊ + ⌊Real.logb 2 (Real.log ↑n)⌋₊ - r) S ≤ A * Real.exp (-κ * ↑r)
theorem Epidemics.Revisited.pushPull_tail_explicit :
∃ (A : ℝ) (κ : ℝ), 0 ≤ A ∧ 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (r : ℕ), 1 - (pushPull n).notYet (↑n) (⌊Real.logb 3 ↑n⌋₊ + ⌊Real.logb 2 (Real.log ↑n)⌋₊ - r) S ≤ A * Real.exp (-κ * ↑r)

Push: exponential final phase #

theorem Epidemics.Revisited.push_tail_explicit :
∃ (A : ℝ) (κ : ℝ), 0 ≤ A ∧ 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (r : ℕ), 1 - (push n).notYet (↑n) (⌊Real.logb 2 ↑n⌋₊ + ⌊Real.log ↑n⌋₊ - r) S ≤ A * Real.exp (-κ * ↑r)

Expectations #

theorem Epidemics.Revisited.push_expect_explicit :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (R : ℕ), Real.logb 2 ↑n + Real.log ↑n ≤ ↑R → Real.logb 2 ↑n + Real.log ↑n - B ≤ ∑ t ∈ Finset.range R, (push n).notYet (↑n) t S
theorem Epidemics.Revisited.logb_log_nonneg {n : ℕ} (hn : 3 ≤ n) :

log₂ ln n ≥ 0 for n ≥ 3.

theorem Epidemics.Revisited.pull_expect_explicit :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (R : ℕ), Real.logb 2 ↑n + Real.logb 2 (Real.log ↑n) ≤ ↑R → Real.logb 2 ↑n + Real.logb 2 (Real.log ↑n) - B ≤ ∑ t ∈ Finset.range R, (pull n).notYet (↑n) t S
theorem Epidemics.Revisited.pushPull_expect_explicit :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.card = 1 → ∀ (R : ℕ), Real.logb 3 ↑n + Real.logb 2 (Real.log ↑n) ≤ ↑R → Real.logb 3 ↑n + Real.logb 2 (Real.log ↑n) - B ≤ ∑ t ∈ Finset.range R, (pushPull n).notYet (↑n) t S