COBRA with branching factor 1 + ρ (EPI-4, Corollary 1 and Theorem 3) #
Cooper, Radzik, Rivera, PODC 2016 (arXiv:1602.05768), Corollary 1 (Section 3) and Theorem 3 (Section 1).
In COBRA with expected branching factor 1 + ρ, each informed vertex pushes to one uniformly
random neighbour and, with probability ρ, to a second one (chosen with replacement); in the dual
BIPS each vertex other than the source contacts one random neighbour and, with probability ρ, a
second one. Here ρ = p/q is rational: a round (CoinChoices G q) gives every vertex two
neighbour samples and a uniform coin in Fin q, and the vertex uses its second sample iff its
coin is < p (coinTargets). Both processes read the same rounds.
cobraCoin_bips_duality: the duality of Theorem 4 for these processes (same proof).- Corollary 1 (
bipsCoin_expected_growth):E(|A_{t+1}| ∣ A_t = A) ≥ |A| (1 + ρ (1 - λ²)(1 - |A|/n)), since a vertexxis infected with probability1 - (1 - P(x, A))(1 - ρ P(x, A)) = (1 + ρ) P(x, A) - ρ P(x, A)². bipsCoin_infection_time: the analogue of Theorem 2 (constantλandρ).- Theorem 3 (
cobra_cover_time_branching,cobra_cover_time_branching_expectation): forλ ≤ λ₀ < 1andρ ≥ ρ₀ > 0constant, the cover time isO(log n)w.h.p. and in expectation.
One round of the branching-factor-1 + p/q processes: two neighbour samples per vertex
(Choices G 2) and one coin per vertex, uniform in Fin q. Under the uniform distribution all
samples and coins are independent.
Equations
- Epidemics.CoinChoices G q = (Epidemics.Choices G 2 × (V → Fin q))
Instances For
The neighbours used by the vertex x in the round ρ: its first sample, and also its second
sample when its coin is < p (probability p/q). COBRA pushes to these vertices, and BIPS
contacts them.
Equations
Instances For
One round of COBRA with branching factor 1 + p/q: every vertex of D pushes to its
coinTargets.
Equations
- Epidemics.cobraCoinStep p D ρ = D.biUnion (Epidemics.coinTargets p ρ)
Instances For
COBRA with branching factor 1 + p/q after the rounds l (first round first), from C.
Equations
- Epidemics.cobraCoinRun p C l = List.foldl (Epidemics.cobraCoinStep p) C l
Instances For
One round of BIPS with branching factor 1 + p/q and persistent source v: a vertex is
infected next iff it is v or one of its coinTargets is in the current infected set A.
Equations
- Epidemics.bipsCoinStep p v A ρ = insert v {u : V | ∃ y ∈ Epidemics.coinTargets p ρ u, y ∈ A}
Instances For
BIPS with branching factor 1 + p/q and source v after the rounds l, from A₀.
Equations
- Epidemics.bipsCoinRun p v A₀ l = List.foldl (Epidemics.bipsCoinStep p v) A₀ l
Instances For
Theorem 4 for branching factor 1 + p/q: P(Hit_C(v) > t ∣ C₀ = C) = P(C ∩ A_t = ∅ ∣ A₀ = {v}) for COBRA and BIPS with branching factor 1 + p/q. Same proof as
cobra_bips_duality: pathwise, COBRA from C along r₁, …, r_t visits v iff BIPS from {v}
along r_t, …, r₁ infects a vertex of C.
Corollary 1 (Section 3). On an r-regular graph (r > 0), for 0 ≤ ρ = p/q ≤ 1, one
round of BIPS with branching factor 1 + ρ from the infected set A gives
E(|A_{t+1}| ∣ A_t = A) ≥ |A| (1 + ρ (1 - λ²)(1 - |A|/n)).
BIPS with branching factor 1 + p/q and source w is a growth process (GrowthProcess)
with every rate c ≤ (p/q)(1 - λ²): source, moment generating function (tgtBips_mgf_le),
Corollary 1, monotonicity, V absorbing.
Theorem 2 for branching factor 1 + ρ (the BIPS half of Theorem 3, "the proof of
Theorem 3 follows from the proof of Theorem 1, by using Corollary 1"). For constants
λ₀ < 1 and ρ₀ > 0 there are C and N such that on every r-regular graph (r > 0) with
n ≥ N vertices and λ ≤ λ₀, for ρ = p/q ∈ [ρ₀, 1], every source v and every
T ≥ C log n, BIPS with branching factor 1 + ρ from {v} has not infected all vertices at
time T with probability at most C / n³.
Theorem 3 (Section 1), probability bound. For constants λ₀ < 1 and ρ₀ > 0 there are
C and N such that on every r-regular graph (r > 0) with n ≥ N vertices and λ ≤ λ₀,
for ρ = p/q ∈ [ρ₀, 1], every start vertex u and every T ≥ C log n, COBRA with branching
factor 1 + ρ from {u} fails to visit every vertex at the times 1, …, T with probability at
most C / n². (The paper assumes G connected; λ < 1 forces it.)
Theorem 3 (Section 1), expectation bound: under the same hypotheses, every partial tail
sum ∑_{s < H} P(cov(u) > s) of the cover time of COBRA with branching factor 1 + ρ is at most
C log n.