Documentation

Epidemics.Revisited.DoubleShrinkingUpper

Theorem 43, upper bound (EPI-8, proof) #

The three stages of DoubleShrinkingStages are composed by the Markov property at fixed times (notYet_add_le), splitting the extra rounds r into thirds. The failure probabilities per phase are polynomially small in n, which gives the paper's tail O(n^{A' - α' r}); the number of double exponential phases is J = ⌊log_ℓ (β ln n / (2 D₀))⌋ ≤ log_ℓ ln n, and the factor 2^J of the phase calculus is a power of n.

Real powers of n #

theorem Epidemics.Revisited.inv_n_eq {n : ℕ} :
1 / ↑n = ↑n ^ (-1)
theorem Epidemics.Revisited.q_geom_le {n : ℕ} (hn : 1 ≤ n) {m m' c α τ τ' : ℝ} (hm : 0 < m) (hm' : 0 < m') (hc : 0 ≤ c) (hα : 0 ≤ α) (hτ' : τ' ≤ τ) (hτ'1 : τ' ≤ 1) (hB : (1 + c) / m ^ 2 + 1 / m' ≤ ↑n ^ (τ' / 2)) :
(1 + c) * ↑n / (m * ↑n) ^ 2 + ↑n ^ (1 - α) * ↑n ^ (-τ) / (m' * ↑n) ≤ ↑n ^ (-(τ' / 2))

Failure probability of a geometric phase.

theorem Epidemics.Revisited.q_double_le {n : ℕ} (hn : 1 ≤ n) {ε c α τ τ' β : ℝ} (hε : ↑n ^ (-β) ≤ ε) (hc : 0 ≤ c) (hβα : β ≤ α) (hβ : β ≤ 1 / 4) (hτ' : τ' ≤ τ) (hτ'1 : τ' ≤ 1 / 2) (hB : 4 * (1 + c) + 1 ≤ ↑n ^ (τ' / 2)) :
(1 + c) * ↑n / (ε * ↑n / 2) ^ 2 + ↑n ^ (1 - α) * ↑n ^ (-τ) / (ε * ↑n) ≤ ↑n ^ (-(τ' / 2))

Failure probability of a double exponential phase, when ε ≥ n^{-β}.

theorem Epidemics.Revisited.npow_eq_exp {n : ℕ} (hn : 1 ≤ n) (x : ℝ) :
↑n ^ x = Real.exp (Real.log ↑n * x)
theorem Epidemics.Revisited.J_facts {n : ℕ} {ℓ κ D₀ β : ℝ} (hℓ : 1 < ℓ) (hκ : 0 ≤ κ) (hD₀ : 0 < D₀) (hβ0 : 0 < β) (hβD : β / (2 * D₀) ≤ 1) (hn : 1 ≤ n) (hlog : 2 * D₀ / β + 2 * κ / β ≤ Real.log ↑n) (J : ℕ) (hJ : J = ⌊Real.logb ℓ (β * Real.log ↑n / (2 * D₀))⌋₊) :
↑n ^ (-β) ≤ epsSeq ℓ κ D₀ J ∧ epsSeq ℓ κ D₀ J ≤ ↑n ^ (-(β / (2 * ℓ))) ∧ ↑J ≤ Real.logb ℓ (Real.log ↑n) ∧ ↑J * Real.log ℓ ≤ Real.log ↑n

The number of double exponential phases, J = ⌊log_ℓ (β ln n / (2 D₀))⌋: the last target ε_J lies between n^{-β} and n^{-β/(2ℓ)}, and J ≤ log_ℓ ln n.

theorem Epidemics.Revisited.notYet_three_le {n : ℕ} (P : RumorProcess n) {m₁ m₂ : ℝ} (K J : ℕ) (F₁ F₂ F₃ : ℕ → ℝ) (hF₂ : ∀ (s : ℕ), 0 ≤ F₂ s) (hF₃ : ∀ (s : ℕ), 0 ≤ F₃ s) (S : Finset (Fin n)) (h1 : ∀ (s : ℕ), P.notYet m₁ (K + s) S ≤ F₁ s) (h2 : ∀ (T : Finset (Fin n)), m₁ ≤ ↑T.card → ∀ (s : ℕ), P.notYet m₂ (J + s) T ≤ F₂ s) (h3 : ∀ (T : Finset (Fin n)), m₂ ≤ ↑T.card → ∀ (s : ℕ), P.notYet (↑n) s T ≤ F₃ s) (r : ℕ) :
P.notYet (↑n) (K + J + r) S ≤ F₁ (r / 3) + F₂ (r / 3) + F₃ (r - 2 * (r / 3))

Three stages in sequence, the extra rounds r split into thirds.

theorem Epidemics.Revisited.three_terms_le {n : ℕ} (hn : 1 ≤ n) {K : ℕ} {A₂ ω δ τ₃ : ℝ} (hω : 0 < ω) (hωδ : ω ≤ δ / 2) (hωτ : ω ≤ τ₃) {J : ℕ} (hJ : 2 ^ J ≤ ↑n ^ A₂) (r : ℕ) :
2 ^ K * ↑n ^ (-(δ / 2) * ↑(r / 3)) + 2 ^ J * ↑n ^ (-(δ / 2) * ↑(r / 3)) + (↑n ^ (-τ₃)) ^ (r - 2 * (r / 3)) * ↑n ≤ (2 ^ K + 2) * ↑n ^ (max A₂ 1 + 2 * ω / 3 - ω / 3 * ↑r)

The exponent bookkeeping of the three stages.

theorem Epidemics.Revisited.double_shrinking_tail_core {n : ℕ} (P : RumorProcess n) {ℓ a c g α τ lam μ a₁ κ D₀ β τ' δ σ τ₃ ω A₂ : ℝ} (K : ℕ) (hℓ : 1 < ℓ) (ha : 0 ≤ a) (hc : 0 ≤ c) (hg : 0 < g) (hα : 0 < α) (hlam : lam = a * g ^ (ℓ - 1)) (hlamμ : lam < μ) (hμ1 : μ < 1) (hμ0 : 0 < μ) (haa₁ : a ≤ a₁) (ha₁0 : 0 < a₁) (hκ0 : 0 ≤ κ) (hκeq : Real.log (2 * a₁) = κ * (ℓ - 1)) (hD₀1 : 1 ≤ D₀) (hε0g : epsSeq ℓ κ D₀ 0 ≤ g) (hgK : g * μ ^ K ≤ epsSeq ℓ κ D₀ 0) (hβ0 : 0 < β) (hβα : β ≤ α) (hβ4 : β ≤ 1 / 4) (hτ'τ : τ' ≤ τ) (hτ'2 : τ' ≤ 1 / 2) (hδ0 : 0 < δ) (h2δ : -(2 * δ) = -(τ' / 2)) (hσ : σ = β * (ℓ - 1) / (4 * ℓ)) (hτ₃τ : τ₃ ≤ τ) (hτ₃σ : τ₃ ≤ σ) (hω0 : 0 < ω) (hωδ : ω ≤ δ / 2) (hωτ : ω ≤ τ₃) (hA₂ : A₂ = Real.log 2 / Real.log ℓ) (hn1 : 1 ≤ n) (h2 : 2 ≤ ↑n ^ (δ / 2)) (hB1 : (1 + c) / (g * μ ^ K * (μ - lam)) ^ 2 + 1 / (g * μ ^ K) ≤ ↑n ^ (τ' / 2)) (hB2 : 4 * (1 + c) + 1 ≤ ↑n ^ (τ' / 2)) (hlog : 2 * D₀ / β + 2 * κ / β ≤ Real.log ↑n) (ha₁n : a₁ ≤ ↑n ^ σ) (hDES : P.UpperDoubleShrinking ℓ a c g α) (hFF : P.FastFinishing α τ) (S : Finset (Fin n)) (hS : ↑n - ↑S.card ≤ g * ↑n) :
∃ J ≤ ⌈Real.logb ℓ (Real.log ↑n)⌉₊, ∀ (r' : ℕ), P.notYet (↑n) (K + J + r') S ≤ (2 ^ K + 2) * ↑n ^ (max A₂ 1 + 2 * ω / 3 - ω / 3 * ↑r')

Theorem 43 for one value of n, given the constants of the three stages: after K + J + r rounds, with J ≤ ⌈log_ℓ ln n⌉, the tail is at most (2^K + 2) n^{max A₂ 1 + 2ω/3 - (ω/3) r}.

theorem Epidemics.Revisited.double_shrinking_tail_main {ℓ a c g α τ : ℝ} (hℓ : 1 < ℓ) (ha : 0 ≤ a) (hc : 0 ≤ c) (hg : 0 < g) (hα : 0 < α) (hag : a * g ^ (ℓ - 1) < 1) (hτ : 0 < τ) :
∃ (C : ℝ) (A' : ℝ) (α' : ℝ), 1 ≤ C ∧ 0 ≤ A' ∧ 0 < α' ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (P : RumorProcess n), P.UpperDoubleShrinking ℓ a c g α → P.FastFinishing α τ → ∀ (S : Finset (Fin n)), ↑n - ↑S.card ≤ g * ↑n → ∀ (r : ℕ), P.notYet (↑n) (⌈Real.logb ℓ (Real.log ↑n)⌉₊ + r) S ≤ C * ↑n ^ (A' - α' * ↑r)

Theorem 43, tail, in the main case g > 0, α > 0.