One round of BIPS (EPI-4) #
Independence of the samples in Choices G k, the probability that one BIPS round infects a given
vertex, and the resulting expression for the expected size. These are the one-round inputs of
Lemma 1 and of the moment generating function (computations (3) to (5) and (12)).
Independence over vertices. A uniform round ρ : Choices G k samples the vertices
independently, so an average of a product of one-vertex observables factors.
Independence over the k samples of one vertex.
On an r-regular graph with r > 0 every neighbour set is nonempty, so rounds exist.
A one-vertex observable has the same average in the full round as on its own samples.
One neighbour of u, drawn uniformly, lies outside A with probability 1 - d_A(u) / r.
d_A(u) / r ∈ [0, 1].
∑_u d_A(u) / r = |A|.
Hitting A with at least one of k samples is 1 minus the product of the misses.
Probability that u belongs to bipsStep v A. It is 1 for the source and
1 - (1 - d_A(u) / r) ^ k otherwise.
E|A'| = ∑_u P(u ∈ A'), with no regularity hypothesis.
The uniform average on an empty type is zero.
E(e^{-φ B}) = 1 - (1 - e^{-φ}) P(B) for an event B on a nonempty finite space.