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.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)
:
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 : ℕ)
:
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}).