Documentation

Epidemics.CobraCover

The BIPS infection time and the COBRA cover time on expanders (EPI-4, Theorems 1 and 2) #

Cooper, Radzik, Rivera, The coalescing-branching random walk on expanders and the dual epidemic process, PODC 2016 (arXiv:1602.05768), Theorems 1 and 2.

Let G be an n-vertex r-regular graph whose random walk has absolute second eigenvalue λ (lambdaG G r), with 1 - λ ≫ √(log n / n), i.e. 1 - λ ≥ C₀ √(log n / n) for a suitably large constant C₀ (the paper's footnote to Theorem 1), and let k ≥ 2.

Finite form. "With probability 1 - O(f)" is ∃ C, P(failure) ≤ C f with C independent of the graph, of n, r, k and the vertices. An expectation E τ of a time τ is written through its tail sum E τ = ∑_{s ≥ 0} P(τ > s), bounded uniformly over all partial sums s < H. The event "A_s = V" for BIPS is persistent (bipsStep_univ), so P(infec(v) > s) = P(A_s ≠ V).

theorem Epidemics.bips_infection_time :
∃ (C₀ : ℝ) (C : ℝ), ∀ {V : Type u_1} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r k : ℕ), G.IsRegularOfDegree r → 0 < r → 2 ≤ k → C₀ * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ 1 - Dynamics.lambdaG G r → ∀ (v : V) (T : ℕ), C * Real.log ↑(Fintype.card V) / (1 - Dynamics.lambdaG G r) ^ 3 ≤ ↑T → (Dynamics.expList (Choices G k) T fun (l : List (Choices G k)) => if bipsRun v {v} l = Finset.univ then 0 else 1) ≤ C / ↑(Fintype.card V) ^ 3

Theorem 2 (Section 1; proved in Sections 3 to 5), probability bound. There are constants C₀, C such that for every r-regular graph (r > 0) on n vertices with 1 - λ ≥ C₀ √(log n / n), every k ≥ 2, every source v and every T ≥ C log n/(1 - λ)³, BIPS with source v from A₀ = {v} has not infected all vertices at time T with probability at most C / n³. (The paper assumes G connected and k = 2; 1 - λ > 0 forces connectivity.)

theorem Epidemics.bips_infection_time_expectation :
∃ (C₀ : ℝ) (C : ℝ), ∀ {V : Type u_1} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r k : ℕ), G.IsRegularOfDegree r → 0 < r → 2 ≤ k → C₀ * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ 1 - Dynamics.lambdaG G r → ∀ (v : V) (H : ℕ), (∑ s ∈ Finset.range H, Dynamics.expList (Choices G k) s fun (l : List (Choices G k)) => if bipsRun v {v} l = Finset.univ then 0 else 1) ≤ C * Real.log ↑(Fintype.card V) / (1 - Dynamics.lambdaG G r) ^ 3

Theorem 2 (Section 1), expectation bound Infec(G) = O(log n/(1 - λ)³): under the same hypotheses, every partial tail sum ∑_{s < H} P(infec(v) > s) = ∑_{s < H} P(A_s ≠ V) (that is, E min (infec(v), H)) is at most C log n/(1 - λ)³.

theorem Epidemics.cobra_cover_time :
∃ (C₀ : ℝ) (C : ℝ), ∀ {V : Type u_1} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r k : ℕ), G.IsRegularOfDegree r → 0 < r → 2 ≤ k → C₀ * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ 1 - Dynamics.lambdaG G r → ∀ (u : V) (T : ℕ), C * Real.log ↑(Fintype.card V) / (1 - Dynamics.lambdaG G r) ^ 3 ≤ ↑T → (Dynamics.expList (Choices G k) T fun (l : List (Choices G k)) => if ((Finset.Icc 1 T).biUnion fun (s : ℕ) => cobraRun {u} (List.take s l)) = Finset.univ then 0 else 1) ≤ C / ↑(Fintype.card V) ^ 2

Theorem 1 (Section 1), probability bound. There are constants C₀, C such that for every r-regular graph (r > 0) on n vertices with 1 - λ ≥ C₀ √(log n / n), every k ≥ 2, every start vertex u and every T ≥ C log n/(1 - λ)³, COBRA started from {u} fails to visit every vertex at the times 1, …, T (⋃_{t=1}^T C_t ≠ V, i.e. cov(u) > T) with probability at most C / n². (The paper assumes G connected and k = 2.)

theorem Epidemics.cobra_cover_time_expectation :
∃ (C₀ : ℝ) (C : ℝ), ∀ {V : Type u_1} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r k : ℕ), G.IsRegularOfDegree r → 0 < r → 2 ≤ k → C₀ * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ 1 - Dynamics.lambdaG G r → ∀ (u : V) (H : ℕ), (∑ s ∈ Finset.range H, Dynamics.expList (Choices G k) s fun (l : List (Choices G k)) => if ((Finset.Icc 1 s).biUnion fun (t : ℕ) => cobraRun {u} (List.take t l)) = Finset.univ then 0 else 1) ≤ C * Real.log ↑(Fintype.card V) / (1 - Dynamics.lambdaG G r) ^ 3

Theorem 1 (Section 1), expectation bound COV(G) = max_u E cov(u) = O(log n/(1 - λ)³): under the same hypotheses, every partial tail sum ∑_{s < H} P(cov(u) > s) = ∑_{s < H} P(⋃_{t=1}^s C_t ≠ V) is at most C log n/(1 - λ)³.