Documentation

Epidemics.CobraCoverIndep

Independent coordinates of a uniform round (EPI-4, Corollary 1 and Theorem 3) #

Under the uniform distribution on a finite dependent product (u : V) → Ω u, the coordinates are independent: averages of products factor, and an observable of one coordinate has the same average as on that coordinate alone (the core's Dynamics.avg_pi_prod and Dynamics.avg_pi_eval, in Dynamics.Uniform). Consequently, the number N of coordinates u whose value satisfies an event X u has the moment generating function bound E e^{-φ N} ≤ exp(-(1 - e^{-φ}) E N) (pi_count_mgf_le), the computation (12) of the paper, and E N = ∑_u P(X u) (avg_pi_count). Choices G k is the case Ω u = Fin k → G.neighborSet u (avg_choices_prod, bips_mgf_le).

theorem Epidemics.card_filter_pi_eq_sum {V : Type u_1} [Fintype V] {Ω : V → Type u_2} (X : (u : V) → Ω u → Prop) [(u : V) → DecidablePred (X u)] (ω : (u : V) → Ω u) :
↑{u : V | X u (ω u)}.card = ∑ u : V, if X u (ω u) then 1 else 0

The number of coordinates whose value satisfies its event, as a sum of indicators.

theorem Epidemics.avg_pi_count {V : Type u_1} [Fintype V] [DecidableEq V] {Ω : V → Type u_2} [(u : V) → Fintype (Ω u)] [∀ (u : V), Nonempty (Ω u)] (X : (u : V) → Ω u → Prop) [(u : V) → DecidablePred (X u)] :
(Dynamics.avg fun (ω : (u : V) → Ω u) => ↑{u : V | X u (ω u)}.card) = ∑ u : V, Dynamics.avg fun (a : Ω u) => if X u a then 1 else 0

Expected count: E N = ∑_u P(X u).

theorem Epidemics.pi_count_mgf_le {V : Type u_1} [Fintype V] [DecidableEq V] {Ω : V → Type u_2} [(u : V) → Fintype (Ω u)] (X : (u : V) → Ω u → Prop) [(u : V) → DecidablePred (X u)] (φ : ℝ) :
(Dynamics.avg fun (ω : (u : V) → Ω u) => Real.exp (-φ * ↑{u : V | X u (ω u)}.card)) ≤ Real.exp (-(1 - Real.exp (-φ)) * Dynamics.avg fun (ω : (u : V) → Ω u) => ↑{u : V | X u (ω u)}.card)

Moment generating function of a count of independent events (computation (12)): E e^{-φ N} = ∏_u (1 - (1 - e^{-φ}) P(X u)) ≤ exp(-(1 - e^{-φ}) E N).