Documentation

Epidemics.Revisited.DoubleShrinkingAux

Phase calculus with potentials (EPI-8, double exponential shrinking) #

Generic finite-time tools for Theorem 43:

theorem Epidemics.Revisited.closed_of_superset {n : ℕ} (P : RumorProcess n) (R : Finset (Fin n) → Prop) (hR : ∀ (S T : Finset (Fin n)), R S → S ⊆ T → R T) (S T : Finset (Fin n)) :
R S → (P.K S).weight T ≠ 0 → R T

A region of states closed under informing more nodes is closed under the rounds.

theorem Epidemics.Revisited.card_le_of_subset_real {n : ℕ} {S T : Finset (Fin n)} (h : S ⊆ T) :
↑S.card ≤ ↑T.card
theorem Epidemics.Revisited.notYet_phase_le {n : ℕ} (P : RumorProcess n) (y : ℕ → ℝ) (J : ℕ) {q lam : ℝ} (hq : 0 ≤ q) (hlam : 1 ≤ lam) (hstep : ∀ j < J, ∀ (S : Finset (Fin n)), ↑n - ↑S.card ≤ y j → ((P.K S).prob fun (T : Finset (Fin n)) => y (j + 1) < ↑n - ↑T.card) ≤ q) (S : Finset (Fin n)) (hS : ↑n - ↑S.card ≤ y 0) (t : ℕ) :
P.notYet (↑n - y J) t S ≤ (q + 1 / lam) ^ t * lam ^ J

Phase calculus: from at most y 0 uninformed nodes, more than y J remain after t rounds with probability at most (q + 1/λ)^t λ^J. The core's Kernel.iterate_outside_le_of_phases with the phases A j = "at most y j uninformed nodes", closed under the rounds since the informed set only grows.

theorem Epidemics.Revisited.notYet_finish_le {n : ℕ} (P : RumorProcess n) {U θ : ℝ} (hθ : 0 ≤ θ) (hstep : ∀ (S : Finset (Fin n)), ↑n - ↑S.card ≤ U → ∀ x ∉ S, 1 - P.informProb S x ≤ θ) (S : Finset (Fin n)) (hS : ↑n - ↑S.card ≤ U) (t : ℕ) :
P.notYet (↑n) t S ≤ θ ^ t * (↑n - ↑S.card)

Finishing: if every uninformed node stays uninformed with probability at most θ in every round started with at most U uninformed nodes, then from such a state some node is still uninformed after t rounds with probability at most θ^t (n - |S|).

theorem Epidemics.Revisited.prob_deficit_gt_cheb {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) {c₀ μ z : ℝ} (hc₀ : 0 ≤ c₀) (hcov : ∀ x ∉ S, ∀ y ∉ S, x ≠ y → P.cov S x y ≤ c₀) (hμ : ((P.K S).expect fun (T : Finset (Fin n)) => ↑n - ↑T.card) ≤ μ) (hz : μ < z) :
((P.K S).prob fun (T : Finset (Fin n)) => z < ↑n - ↑T.card) ≤ (↑n - ↑S.card + c₀ * (↑n - ↑S.card) ^ 2) / (z - μ) ^ 2

Chebyshev for one round: if the expected number of uninformed nodes after the round is at most μ < z and distinct uninformed nodes have covariance at most c₀ ≥ 0, then more than z nodes stay uninformed with probability at most (u + c₀ u²) / (z - μ)², u = n - |S|.

theorem Epidemics.Revisited.prob_deficit_gt_markov {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) {μ z : ℝ} (hμ : ((P.K S).expect fun (T : Finset (Fin n)) => ↑n - ↑T.card) ≤ μ) (hz : 0 < z) :
((P.K S).prob fun (T : Finset (Fin n)) => z < ↑n - ↑T.card) ≤ μ / z

Markov for one round: more than z > 0 nodes stay uninformed with probability at most μ / z when their expected number is at most μ.

theorem Epidemics.Revisited.expect_deficit_le_of_stay {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) {s : ℝ} (h : ∀ x ∉ S, 1 - P.informProb S x ≤ s) :
((P.K S).expect fun (T : Finset (Fin n)) => ↑n - ↑T.card) ≤ (↑n - ↑S.card) * s

The expected number of uninformed nodes after a round where each uninformed node stays uninformed with probability at most s.