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):
- Push. With
a = ⌊log₂ n⌋,b = ⌊ln n⌋andt* = a + b - r, splitt* ≤ s + τwiths = a - ⌈r/2⌉andτ = b - ⌊r/2⌋. The growth phase reachesn / 2withinsrounds with probability at most2^{s+1} / n ≤ 2 · 2^{-r/2}, and from fewer thann / 2informed nodes,push_final_lower_explicitbounds the probability of informing everybody withinτrounds by1600 e^{(τ - ln(n/2))/2} = O(e^{-(ln 2 / 4) r}). - Pull and push–pull (
double_tail_generic, growth factorρ = 2or3). Witha = ⌊log_ρ n⌋,d = ⌊log₂ ln n⌋, splitτ = d - r₀(the range of the final phase) ands = t* - τ. The first term is at most2 ρ^{r₀} 2^{-r/2}and the secondC n^{-1/2}, which isO(e^{-(ln 2 / 4) r})because a positivet*forcesr ≤ 2 log₂ n. - Expectations (
sum_notYet_ge_of_tail, the mirror ofsum_notYet_le_of_tail): an exponential lower tail beforet₀gives∑_{t < R} P[T > t] ≥ t₀ - A / (1 - e^{-κ})for everyR ≥ t₀, andt₀ ≥ X + Y - 2fort₀ = ⌊X⌋ + ⌊Y⌋.
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)
:
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)
:
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 #
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)))
:
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}.