One round of BIPS with branching factor 1 + p/q (EPI-4, Corollary 1) #
A round of the coin processes is Choices G 2 × (V → Fin q): two neighbour samples and a coin
per vertex. Regrouping by vertex (coinEquiv) gives the product of the per-vertex samples
CoinSample G q u = (Fin 2 → G.neighborSet u) × Fin q, so the vertices are independent. Vertex
u uses its first sample, and also its second one when its coin is < p (coinTgt), so with
P = d_A(u)/r and ρ = p/q it meets A with probability
1 - (1 - P)(1 - ρ P) = (1 + ρ) P - ρ P² (coin_hit_prob). As in Lemma 1, the spectral bound
∑_u P_u² ≤ λ² |A| + (1 - λ²) |A|²/n gives Corollary 1 (coin_expected_growth).
The samples of one vertex u in a round of the coin processes.
Equations
- Epidemics.CoinSample G q u = ((Fin 2 → ↑(G.neighborSet u)) × Fin q)
Instances For
Regrouping a round of the coin processes by vertex.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The neighbours used by u given its samples: the first one, and the second one when the
coin is < p.
Instances For
Meeting A with the targets: first sample in A, or coin < p and second sample in A,
written as 1 - m₀ + m₀ h₁ c with m₀ = 1_{first ∉ A}, h₁ = 1_{second ∈ A},
c = 1_{coin < p}.
Infection probability of a vertex u ≠ v with branching factor 1 + ρ, ρ = p/q:
(1 + ρ) P - ρ P² with P = d_A(u)/r.
Corollary 1 (Section 3), for the target-set form of BIPS with branching factor
1 + p/q: E|A'| ≥ |A| (1 + ρ (1 - λ²)(1 - |A|/n)) with ρ = p/q.
The rate of Theorem 3: c = min 1 (ρ₀ (1 - max λ₀ 0)) satisfies 0 < c ≤ 1 and
c ≤ ρ (1 - λ²) whenever ρ ≥ ρ₀ and 0 ≤ λ ≤ λ₀.