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 + ρ:
- the duality
P(Hit_C(w) > t) = P(C ∩ A_t = ∅ ∣ A₀ = {w})(Theorem 4); cstepmaps nonempty sets to nonempty sets;- the BIPS failure bound
P(A_T ≠ V ∣ A₀ = {w}) ≤ ε.
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).
Union bound, pathwise: if ⋃_{t=1}^T C_t ≠ V, some vertex is missed at all the times
1, …, T.
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}).
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 ε.
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).
c > 0 and log n/c³ ≥ 1/2 under the gap hypothesis c ≥ 128 √(log n/n), c ≤ 1,
n ≥ 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².
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³.