Documentation

Epidemics.CobraCoverGrowth

One round of BIPS: expected growth and concentration (EPI-4) #

Cooper, Radzik, Rivera, PODC 2016 (arXiv:1602.05768), Section 3 (Lemma 1) and the one-round facts used in Sections 4 and 5.

Given the infected set A, one BIPS round (bipsStep v A) infects the source v and, independently, every other vertex u that samples a neighbour in A among its k samples, which happens with probability 1 - (1 - d_A(u)/r)^k on an r-regular graph. Hence:

The deterministic facts bipsStep_mono (monotonicity in the infected set, the "standard coupling argument" of Lemma 4), bipsStep_univ (the fully infected state is absorbing on a graph without isolated vertices) and source_mem_bipsStep are proved here.

theorem Epidemics.source_mem_bipsStep {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} (v : V) (A : Finset V) (ρ : Choices G k) :
v ∈ bipsStep v A ρ

The source is infected after every BIPS round.

theorem Epidemics.bipsStep_mono {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} (v : V) {A B : Finset V} (h : A ⊆ B) (ρ : Choices G k) :
bipsStep v A ρ ⊆ bipsStep v B ρ

One BIPS round is monotone in the infected set (pathwise coupling: same samples).

theorem Epidemics.bipsStep_univ {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} (v : V) (hk : 1 ≤ k) (ρ : Choices G k) :

If k ≥ 1, the fully infected state is absorbing.

theorem Epidemics.bips_expected_growth {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (hk : 2 ≤ k) (v : V) (A : Finset V) :
↑A.card * (1 + (1 - Dynamics.lambdaG G r ^ 2) * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : Choices G k) => ↑(bipsStep v A ρ).card

Lemma 1 (Section 3; inequalities (3) to (7)). On an r-regular graph (r > 0) with λ = lambdaG G r, one round of BIPS with k ≥ 2 samples per vertex from the infected set A gives E(|A_{t+1}| ∣ A_t = A) ≥ |A| (1 + (1 - λ²)(1 - |A|/n)). The paper assumes G connected, λ < 1 and k = 2; the bound holds for every regular graph, every k ≥ 2 and every set A (it need not contain the source).

theorem Epidemics.bips_mgf_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} [DecidableRel G.Adj] (v : V) (A : Finset V) (φ : ℝ) :
(Dynamics.avg fun (ρ : Choices G k) => Real.exp (-φ * ↑(bipsStep v A ρ).card)) ≤ Real.exp (-(1 - Real.exp (-φ)) * Dynamics.avg fun (ρ : Choices G k) => ↑(bipsStep v A ρ).card)

One-round moment generating function (computation (12) in the proof of Lemma 2): the vertices are infected independently given A, so for every real φ, E(e^{-φ |A'|}) = ∏ᵤ (1 - (1 - e^{-φ}) P(u ∈ A')) ≤ exp(-(1 - e^{-φ}) E|A'|).

theorem Epidemics.bips_chernoff_lower {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} [DecidableRel G.Adj] (v : V) (A : Finset V) {δ μ : ℝ} (hδ0 : 0 < δ) (hδ1 : δ < 1) (hμ : μ ≤ Dynamics.avg fun (ρ : Choices G k) => ↑(bipsStep v A ρ).card) :
(Dynamics.avg fun (ρ : Choices G k) => if ↑(bipsStep v A ρ).card ≤ (1 - δ) * μ then 1 else 0) ≤ Real.exp (-(δ ^ 2 * μ / 2))

Chernoff lower tail for one BIPS round (used in (18) of Lemma 3 and in the proof of Lemma 4): if μ ≤ E|A'| and 0 < δ < 1, then P(|A'| ≤ (1 - δ) μ) ≤ exp(-δ² μ / 2).