BIPS as a growth process (EPI-4, Theorems 1 and 2) #
BIPS with source v satisfies the hypotheses (H1)–(H5) of GrowthProcess with rate
c = 1 - λ: the source is persistent (source_mem_bipsStep), the moment generating function
bound is bips_mgf_le, Lemma 1 (bips_expected_growth) gives growth with 1 - λ² ≥ 1 - λ,
and BIPS is monotone with V absorbing. Theorems 1 and 2 are then the generic
GrowthProcess.fail_le, GrowthProcess.tail_sum_le_log, cover_fail_le_log and
cover_tail_sum_le_log with c = 1 - λ.
theorem
Epidemics.bips_growthProcess
{V : Type u_1}
[Fintype V]
[DecidableEq V]
{G : SimpleGraph V}
[DecidableRel G.Adj]
{k r : ℕ}
(hreg : G.IsRegularOfDegree r)
(hr : 0 < r)
(hk : 2 ≤ k)
(hlam : Dynamics.lambdaG G r < 1)
(v : V)
:
GrowthProcess (bipsStep v) v (1 - Dynamics.lambdaG G r)
BIPS is a growth process with rate 1 - λ (for k ≥ 2 and λ < 1).
theorem
Epidemics.lambdaG_lt_one_of_gap
{V : Type u_1}
[Fintype V]
[DecidableEq V]
{G : SimpleGraph V}
[DecidableRel G.Adj]
[Nonempty V]
{r : ℕ}
(hreg : G.IsRegularOfDegree r)
(hr : 0 < r)
(hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ 1 - Dynamics.lambdaG G r)
:
The gap hypothesis 128 √(log n/n) ≤ 1 - λ gives λ < 1 and 1 - λ ≤ 1 (n ≥ 2).