Documentation

Epidemics.CobraCoverRound

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)).

theorem Epidemics.avg_choices_prod {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ℕ} (f : (u : V) → (Fin k → ↑(G.neighborSet u)) → ℝ) :
(Dynamics.avg fun (ρ : Choices G k) => ∏ u : V, f u (ρ u)) = ∏ u : V, Dynamics.avg (f u)

Independence over vertices. A uniform round ρ : Choices G k samples the vertices independently, so an average of a product of one-vertex observables factors.

theorem Epidemics.avg_pow_samples {α : Type u_2} [Fintype α] (k : ℕ) (g : α → ℝ) :
(Dynamics.avg fun (σ : Fin k → α) => ∏ i : Fin k, g (σ i)) = Dynamics.avg g ^ k

Independence over the k samples of one vertex.

theorem Epidemics.choices_nonempty_of_regular {V : Type u_1} [Fintype V] {G : SimpleGraph V} [DecidableRel G.Adj] {r k : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) :

On an r-regular graph with r > 0 every neighbour set is nonempty, so rounds exist.

theorem Epidemics.avg_choices_depends {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ℕ} (u : V) (g : (Fin k → ↑(G.neighborSet u)) → ℝ) (hne : Nonempty (Choices G k)) :
(Dynamics.avg fun (ρ : Choices G k) => g (ρ u)) = Dynamics.avg g

A one-vertex observable has the same average in the full round as on its own samples.

theorem Epidemics.avg_neighbor_miss {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (u : V) (A : Finset V) :
(Dynamics.avg fun (w : ↑(G.neighborSet u)) => if ↑w ∈ A then 0 else 1) = 1 - ↑(G.neighborFinset u ∩ A).card / ↑r

One neighbour of u, drawn uniformly, lies outside A with probability 1 - d_A(u) / r.

theorem Epidemics.neighbor_frac_mem {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (u : V) (A : Finset V) :
0 ≤ ↑(G.neighborFinset u ∩ A).card / ↑r ∧ ↑(G.neighborFinset u ∩ A).card / ↑r ≤ 1

d_A(u) / r ∈ [0, 1].

theorem Epidemics.sum_neighbor_frac {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (A : Finset V) :
∑ u : V, ↑(G.neighborFinset u ∩ A).card / ↑r = ↑A.card

∑_u d_A(u) / r = |A|.

theorem Epidemics.hit_eq_one_sub_prod {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {k : ℕ} (u : V) (A : Finset V) (σ : Fin k → ↑(G.neighborSet u)) :
(if ∃ (i : Fin k), ↑(σ i) ∈ A then 1 else 0) = 1 - ∏ i : Fin k, if ↑(σ i) ∈ A then 0 else 1

Hitting A with at least one of k samples is 1 minus the product of the misses.

theorem Epidemics.bips_infect_prob {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r k : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (v u : V) (A : Finset V) :
(Dynamics.avg fun (ρ : Choices G k) => if u ∈ bipsStep v A ρ then 1 else 0) = if u = v then 1 else 1 - (1 - ↑(G.neighborFinset u ∩ A).card / ↑r) ^ k

Probability that u belongs to bipsStep v A. It is 1 for the source and 1 - (1 - d_A(u) / r) ^ k otherwise.

theorem Epidemics.bipsStep_card_eq_sum {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ℕ} (v : V) (A : Finset V) (ρ : Choices G k) :
↑(bipsStep v A ρ).card = ∑ u : V, if u ∈ bipsStep v A ρ then 1 else 0

|bipsStep v A ρ| = ∑_u 1_{u ∈ bipsStep v A ρ}.

theorem Epidemics.bips_expected_card {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ℕ} (v : V) (A : Finset V) :
(Dynamics.avg fun (ρ : Choices G k) => ↑(bipsStep v A ρ).card) = ∑ u : V, Dynamics.avg fun (ρ : Choices G k) => if u ∈ bipsStep v A ρ then 1 else 0

E|A'| = ∑_u P(u ∈ A'), with no regularity hypothesis.

theorem Epidemics.avg_eq_zero_of_isEmpty {α : Type u_2} [Fintype α] [IsEmpty α] (f : α → ℝ) :

The uniform average on an empty type is zero.

theorem Epidemics.avg_exp_bernoulli {α : Type u_2} [Fintype α] [Nonempty α] (φ : ℝ) (p : α → Prop) [DecidablePred p] :
(Dynamics.avg fun (a : α) => Real.exp (-φ * if p a then 1 else 0)) = 1 - (1 - Real.exp (-φ)) * Dynamics.avg fun (a : α) => if p a then 1 else 0

E(e^{-φ B}) = 1 - (1 - e^{-φ}) P(B) for an event B on a nonempty finite space.