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:
- Lemma 1 (
bips_expected_growth):E|A'| ≥ |A| (1 + (1 - λ²)(1 - |A|/n))fork ≥ 2(the paper statesk = 2; more samples only help, since1 - (1 - p)^k ≥ 1 - (1 - p)²). - the moment generating function of
|A'|is dominated by the Poisson one (bips_mgf_le), as for every sum of independent{0,1}variables (the computation (12) in the proof of Lemma 2); - the multiplicative Chernoff lower tail (
bips_chernoff_lower, used in (18) and in the proof of Lemma 4).
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.
The source is infected after every BIPS round.
One BIPS round is monotone in the infected set (pathwise coupling: same samples).
If k ≥ 1, the fully infected state is absorbing.
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).
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'|).
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).