Documentation

Epidemics.CobraCoverUnion

From the infection time to the cover time (EPI-4, Theorems 1 and 3) #

Cooper, Radzik, Rivera, PODC 2016 (arXiv:1602.05768), proof of Theorem 1 and equation (1).

The argument only uses three facts about a COBRA-like step cstep and a family of BIPS-like steps bstep w (source w), so it is stated once for both branching factors k and 1 + ρ:

Cover time. ⋃_{t=1}^T C_t ≠ V iff some w is missed at the times 1, …, T. For a fixed w, splitting off the first round, missing w at the times 1, …, T₀ + 1 from D is not hitting w within T₀ rounds from C₁ = cstep D ρ ≠ ∅, which by duality has probability P(C₁ ∩ A_{T₀} = ∅) ≤ P(A_{T₀} ≠ V) ≤ ε; the union bound over w gives n ε (cover_fail_le).

Expectation (equation (1)). After s rounds COBRA restarts from the nonempty set C_s, so P(cov > s + T₀ + 1) ≤ n ε P(cov > s); with n ε ≤ 1/2 every partial tail sum is at most 2 (T₀ + 1) (cover_tail_sum_le).

theorem Epidemics.List.take_append_length_add {α : Type u_1} (l₁ l₂ : List α) (t : ℕ) :
List.take (l₁.length + t) (l₁ ++ l₂) = l₁ ++ List.take t l₂
theorem Epidemics.not_cover_le_sum {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] (cstep : Finset V → R → Finset V) (D : Finset V) (T : ℕ) (l : List R) :
(if ((Finset.Icc 1 T).biUnion fun (s : ℕ) => roundRun cstep D (List.take s l)) = Finset.univ then 0 else 1) ≤ ∑ w : V, if w ∉ (Finset.Icc 1 T).biUnion fun (s : ℕ) => roundRun cstep D (List.take s l) then 1 else 0

Union bound, pathwise: if ⋃_{t=1}^T C_t ≠ V, some vertex is missed at all the times 1, …, T.

theorem Epidemics.roundRun_nonempty {V : Type u_1} {R : Type u_2} (cstep : Finset V → R → Finset V) (hne : ∀ (D : Finset V) (ρ : R), D.Nonempty → (cstep D ρ).Nonempty) {D : Finset V} (hD : D.Nonempty) (l : List R) :
(roundRun cstep D l).Nonempty
theorem Epidemics.miss_le {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] [Nonempty R] (cstep : Finset V → R → Finset V) (bstep : V → Finset V → R → Finset V) (hdual : ∀ (w : V) (C : Finset V) (t : ℕ), (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, w ∉ roundRun cstep C (List.take s l) then 1 else 0) = Dynamics.expList R t fun (l : List R) => if C ∩ roundRun (bstep w) {w} l = ∅ then 1 else 0) (hne : ∀ (D : Finset V) (ρ : R), D.Nonempty → (cstep D ρ).Nonempty) (w : V) {T₀ : ℕ} {ε : ℝ} (hfail : (Dynamics.expList R T₀ fun (l : List R) => if roundRun (bstep w) {w} l = Finset.univ then 0 else 1) ≤ ε) {D : Finset V} (hD : D.Nonempty) :
(Dynamics.expList R (T₀ + 1) fun (l : List R) => if w ∉ (Finset.Icc 1 (T₀ + 1)).biUnion fun (s : ℕ) => roundRun cstep D (List.take s l) then 1 else 0) ≤ ε

One vertex. By the first-round split and the duality, COBRA from a nonempty D misses w at all the times 1, …, T₀ + 1 with probability at most P(A_{T₀} ≠ V ∣ A₀ = {w}).

theorem Epidemics.cover_fail_le {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] [Nonempty R] (cstep : Finset V → R → Finset V) (bstep : V → Finset V → R → Finset V) (hdual : ∀ (w : V) (C : Finset V) (t : ℕ), (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, w ∉ roundRun cstep C (List.take s l) then 1 else 0) = Dynamics.expList R t fun (l : List R) => if C ∩ roundRun (bstep w) {w} l = ∅ then 1 else 0) (hne : ∀ (D : Finset V) (ρ : R), D.Nonempty → (cstep D ρ).Nonempty) {T₀ : ℕ} {ε : ℝ} (hfail : ∀ (w : V), (Dynamics.expList R T₀ fun (l : List R) => if roundRun (bstep w) {w} l = Finset.univ then 0 else 1) ≤ ε) {D : Finset V} (hD : D.Nonempty) :
(Dynamics.expList R (T₀ + 1) fun (l : List R) => if ((Finset.Icc 1 (T₀ + 1)).biUnion fun (s : ℕ) => roundRun cstep D (List.take s l)) = Finset.univ then 0 else 1) ≤ ↑(Fintype.card V) * ε

Cover time, union bound (proof of Theorem 1): if P(A_{T₀} ≠ V ∣ A₀ = {w}) ≤ ε for every w, COBRA from a nonempty D has ⋃_{t=1}^{T₀+1} C_t ≠ V with probability at most n ε.

theorem Epidemics.cover_tail_sum_le {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] [Nonempty R] (cstep : Finset V → R → Finset V) (bstep : V → Finset V → R → Finset V) (hdual : ∀ (w : V) (C : Finset V) (t : ℕ), (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, w ∉ roundRun cstep C (List.take s l) then 1 else 0) = Dynamics.expList R t fun (l : List R) => if C ∩ roundRun (bstep w) {w} l = ∅ then 1 else 0) (hne : ∀ (D : Finset V) (ρ : R), D.Nonempty → (cstep D ρ).Nonempty) {T₀ : ℕ} {ε : ℝ} (hfail : ∀ (w : V), (Dynamics.expList R T₀ fun (l : List R) => if roundRun (bstep w) {w} l = Finset.univ then 0 else 1) ≤ ε) (hhalf : ↑(Fintype.card V) * ε ≤ 1 / 2) {D : Finset V} (hD : D.Nonempty) (H : ℕ) :
(∑ s ∈ Finset.range H, Dynamics.expList R s fun (l : List R) => if ((Finset.Icc 1 s).biUnion fun (t : ℕ) => roundRun cstep D (List.take t l)) = Finset.univ then 0 else 1) ≤ 2 * (↑T₀ + 1)

Restarting COBRA (equation (1)): under the hypotheses of cover_fail_le and n ε ≤ 1/2, every partial tail sum ∑_{s < H} P(⋃_{t=1}^s C_t ≠ V) is at most 2 (T₀ + 1).

theorem Epidemics.gap_pos_and_half {V : Type u_1} [Fintype V] {c : ℝ} (hc1 : c ≤ 1) (hn2 : 2 ≤ Fintype.card V) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ c) :
0 < c ∧ 1 / 2 ≤ Real.log ↑(Fintype.card V) / c ^ 3

c > 0 and log n/c³ ≥ 1/2 under the gap hypothesis c ≥ 128 √(log n/n), c ≤ 1, n ≥ 2.

theorem Epidemics.cover_fail_le_log {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] [Nonempty R] (cstep : Finset V → R → Finset V) (bstep : V → Finset V → R → Finset V) (hdual : ∀ (w : V) (C : Finset V) (t : ℕ), (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, w ∉ roundRun cstep C (List.take s l) then 1 else 0) = Dynamics.expList R t fun (l : List R) => if C ∩ roundRun (bstep w) {w} l = ∅ then 1 else 0) (hne : ∀ (D : Finset V) (ρ : R), D.Nonempty → (cstep D ρ).Nonempty) {c : ℝ} (hP : ∀ (w : V), GrowthProcess (bstep w) w c) (hc1 : c ≤ 1) (hn2 : 2 ≤ Fintype.card V) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ c) {D : Finset V} (hD : D.Nonempty) {T : ℕ} (hT : 60002 * Real.log ↑(Fintype.card V) / c ^ 3 ≤ ↑T) :
(Dynamics.expList R T fun (l : List R) => if ((Finset.Icc 1 T).biUnion fun (s : ℕ) => roundRun cstep D (List.take s l)) = Finset.univ then 0 else 1) ≤ 3 / ↑(Fintype.card V) ^ 2

Cover time (generic form of Theorems 1 and 3, probability bound): if every bstep w is a growth process with rate c ≥ 128 √(log n/n), then for T ≥ 60002 log n/c³ COBRA from a nonempty D has ⋃_{t=1}^T C_t ≠ V with probability at most 3/n².

theorem Epidemics.cover_tail_sum_le_log {V : Type u_1} {R : Type u_2} [Fintype V] [DecidableEq V] [Fintype R] [Nonempty R] (cstep : Finset V → R → Finset V) (bstep : V → Finset V → R → Finset V) (hdual : ∀ (w : V) (C : Finset V) (t : ℕ), (Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, w ∉ roundRun cstep C (List.take s l) then 1 else 0) = Dynamics.expList R t fun (l : List R) => if C ∩ roundRun (bstep w) {w} l = ∅ then 1 else 0) (hne : ∀ (D : Finset V) (ρ : R), D.Nonempty → (cstep D ρ).Nonempty) {c : ℝ} (hP : ∀ (w : V), GrowthProcess (bstep w) w c) (hc1 : c ≤ 1) (hn2 : 2 ≤ Fintype.card V) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ c) {D : Finset V} (hD : D.Nonempty) (H : ℕ) :
(∑ s ∈ Finset.range H, Dynamics.expList R s fun (l : List R) => if ((Finset.Icc 1 s).biUnion fun (t : ℕ) => roundRun cstep D (List.take t l)) = Finset.univ then 0 else 1) ≤ 130000 * Real.log ↑(Fintype.card V) / c ^ 3

Cover time in expectation (generic form of Theorems 1 and 3, equation (1)): under the hypotheses of cover_fail_le_log, every partial tail sum ∑_{s < H} P(⋃_{t=1}^s C_t ≠ V) is at most 130000 log n/c³.