Generic one-step growth engine, small phase (EPI-4, Lemma 2) #
Lemmas 2 to 4 use only a round-driven set process with a persistent source, an MGF bound, and a
linear growth lower bound E|A'| ≥ |A| (1 + c (1 - |A|/n)) for some 0 < c ≤ 1. This file proves
the small-set phase with c in place of 1 - λ. The large phase is in CobraCoverEngineLarge
and the end phase is in CobraCoverEngineEnd.
The state of a round-driven process after the rounds l, starting from A.
Equations
- Epidemics.roundRun step A l = List.foldl step A l
Instances For
E(e^{-φ |A_t|} 1_{|A_s| ≤ m for all s < t}), for the process step started at A.
Equations
- One or more equations did not get rendered due to their size.
Instances For
P(|A_s| ≤ m for every s ≤ t).
Equations
- Epidemics.smallProb step m t A = Dynamics.expList R t fun (l : List R) => if ∀ s ≤ t, (Epidemics.roundRun step A (List.take s l)).card ≤ m then 1 else 0
Instances For
While the set stays of size at most m, the failure probability is at most e^{φ m} times
the weighted expectation. Only φ ≥ 0 is used.
One round from a set of size in 1, …, m multiplies the Laplace weight by at most
e^{φ - x}.
While |A| ≥ 1, the weighted expectation contracts by e^{φ - x} at every round.
Lemma 2, abstract form. A round-driven process with a persistent source, the BIPS
moment bound and relative growth 1 + c (1 - |A|/n) exceeds size m ≤ n/2 within
T ≥ 13 m/c + 24 C log n/c² rounds, except with probability n^{-C}.