Documentation

Epidemics.Revisited.DoubleShrinkingRound

One round in the double exponential shrinking regime (EPI-8) #

round_fail_le: one round fails to bring the number of uninformed nodes below a target z with probability at most (1 + c) n / (z - u s)² + n^{1-α} n^{-τ} / z, where s bounds the probability of staying uninformed under Definition 13. Above n^{1-α} uninformed nodes this is Chebyshev's inequality with the variance bound of Lemma 9 (Lemmas 44 and 45 of the paper); below, it is Markov's inequality with fast finishing.

Also small facts on real powers of n used throughout.

theorem Epidemics.Revisited.npow_mono {n : ℕ} (hn : 1 ≤ n) {x y : ℝ} (h : x ≤ y) :
↑n ^ x ≤ ↑n ^ y
theorem Epidemics.Revisited.npow_pos {n : ℕ} (hn : 1 ≤ n) (x : ℝ) :
0 < ↑n ^ x
theorem Epidemics.Revisited.npow_add {n : ℕ} (hn : 1 ≤ n) (x y : ℝ) :
↑n ^ (x + y) = ↑n ^ x * ↑n ^ y
theorem Epidemics.Revisited.npow_pow {n : ℕ} (x : ℝ) (k : ℕ) :
(↑n ^ x) ^ k = ↑n ^ (x * ↑k)
theorem Epidemics.Revisited.exists_le_npow (B : ℝ) {ε : ℝ} (hε : 0 < ε) :
∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → B ≤ ↑n ^ ε

Every constant is eventually below n^ε.

theorem Epidemics.Revisited.exists_le_log (X : ℝ) :
∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → X ≤ Real.log ↑n

ln n is eventually above every constant.

theorem Epidemics.Revisited.round_fail_le {n : ℕ} (P : RumorProcess n) {ℓ a c g α τ s z : ℝ} (hc : 0 ≤ c) (hDES : P.UpperDoubleShrinking ℓ a c g α) (hFF : P.FastFinishing α τ) (hn : 1 ≤ n) (S : Finset (Fin n)) (hSg : ↑n - ↑S.card ≤ g * ↑n) (hs : ↑n ^ (1 - α) ≤ ↑n - ↑S.card → a * ((↑n - ↑S.card) / ↑n) ^ (ℓ - 1) ≤ s) (hz : (↑n - ↑S.card) * s < z) (hz0 : 0 < z) :
((P.K S).prob fun (T : Finset (Fin n)) => z < ↑n - ↑T.card) ≤ (1 + c) * ↑n / (z - (↑n - ↑S.card) * s) ^ 2 + ↑n ^ (1 - α) * ↑n ^ (-τ) / z

One round of Definition 13 or of fast finishing (Lemmas 44 and 45, and Markov).

theorem Epidemics.Revisited.notYet_phase_npow {n : ℕ} (P : RumorProcess n) (y : ℕ → ℝ) (K : ℕ) {δ : ℝ} (hδ : 0 < δ) (hn : 1 ≤ n) (h2 : 2 ≤ ↑n ^ (δ / 2)) (hstep : ∀ j < K, ∀ (S : Finset (Fin n)), ↑n - ↑S.card ≤ y j → ((P.K S).prob fun (T : Finset (Fin n)) => y (j + 1) < ↑n - ↑T.card) ≤ ↑n ^ (-(2 * δ))) (S : Finset (Fin n)) (hS : ↑n - ↑S.card ≤ y 0) (s : ℕ) :
P.notYet (↑n - y K) (K + s) S ≤ 2 ^ K * ↑n ^ (-(δ / 2) * ↑s)

The phase calculus with q = n^{-2δ} and λ = n^δ: after K + s rounds, P[more than y K uninformed] ≤ 2^K n^{-δ s / 2} (when 2 ≤ n^{δ/2}).