Documentation

Epidemics.Revisited.ProtocolsAux

The push, pull and push–pull protocols: computations (EPI-8, instances) #

theorem Epidemics.Revisited.prob_calls_forall {n : ℕ} (A : Fin n → Finset (Fin n)) :
((calls n).prob fun (c : Fin n → Fin n) => ∀ (v : Fin n), c v ∈ A v) = ∏ v : Fin n, ↑(A v).card / ↑n

Product formula for the uniform calls: the coordinates are independent and uniform.

theorem Epidemics.Revisited.cov_eq {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) (x y : Fin n) :
P.cov S x y = ((P.K S).prob fun (T : Finset (Fin n)) => x ∉ T ∧ y ∉ T) - ((P.K S).prob fun (T : Finset (Fin n)) => x ∉ T) * (P.K S).prob fun (T : Finset (Fin n)) => y ∉ T

The covariance of the "informed" indicators equals that of the "uninformed" ones.

theorem Epidemics.Revisited.informProb_eq {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) (x : Fin n) :
P.informProb S x = 1 - (P.K S).prob fun (T : Finset (Fin n)) => x ∉ T
theorem Epidemics.Revisited.prod_ite_mem_const {n : ℕ} (S : Finset (Fin n)) (f : ℝ) :
(∏ v : Fin n, if v ∈ S then f else 1) = f ^ S.card
theorem Epidemics.Revisited.prod_ite_eq_const {n : ℕ} (x : Fin n) (f : ℝ) :
(∏ v : Fin n, if v = x then f else 1) = f
theorem Epidemics.Revisited.n_pos_of_mem {n : ℕ} (x : Fin n) :
0 < ↑n
theorem Epidemics.Revisited.card_erase_erase_cast {n : ℕ} {x y : Fin n} (hxy : x ≠ y) :
↑((Finset.univ.erase x).erase y).card = ↑n - 2

Push #

theorem Epidemics.Revisited.not_mem_pushRound {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) (c : Fin n → Fin n) :
x ∉ pushRound S c ↔ ∀ (v : Fin n), c v ∈ if v ∈ S then Finset.univ.erase x else Finset.univ
theorem Epidemics.Revisited.not_mem_pushRound₂ {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (c : Fin n → Fin n) :
x ∉ pushRound S c ∧ y ∉ pushRound S c ↔ ∀ (v : Fin n), c v ∈ if v ∈ S then (Finset.univ.erase x).erase y else Finset.univ
theorem Epidemics.Revisited.push_prob_not_mem {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(((push n).K S).prob fun (T : Finset (Fin n)) => x ∉ T) = (1 - 1 / ↑n) ^ S.card
theorem Epidemics.Revisited.push_prob_not_mem₂ {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(((push n).K S).prob fun (T : Finset (Fin n)) => x ∉ T ∧ y ∉ T) = (1 - 2 / ↑n) ^ S.card

Pull #

theorem Epidemics.Revisited.not_mem_pullRound {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) (c : Fin n → Fin n) :
x ∉ pullRound S c ↔ ∀ (v : Fin n), c v ∈ if v = x then Finset.univ \ S else Finset.univ
theorem Epidemics.Revisited.forall_and_mem {n : ℕ} (A B : Fin n → Finset (Fin n)) (c : Fin n → Fin n) :
((∀ (v : Fin n), c v ∈ A v) ∧ ∀ (v : Fin n), c v ∈ B v) ↔ ∀ (v : Fin n), c v ∈ A v ∩ B v
theorem Epidemics.Revisited.card_univ_div {n : ℕ} (hn : 0 < ↑n) :
↑Finset.univ.card / ↑n = 1
theorem Epidemics.Revisited.pull_prob_not_mem {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(((pull n).K S).prob fun (T : Finset (Fin n)) => x ∉ T) = 1 - ↑S.card / ↑n
theorem Epidemics.Revisited.pull_prob_not_mem₂ {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(((pull n).K S).prob fun (T : Finset (Fin n)) => x ∉ T ∧ y ∉ T) = (1 - ↑S.card / ↑n) ^ 2

Push–pull #

theorem Epidemics.Revisited.not_mem_pushPullRound {n : ℕ} (S : Finset (Fin n)) (x : Fin n) (c : Fin n → Fin n) :
x ∉ pushPullRound S c ↔ x ∉ pushRound S c ∧ x ∉ pullRound S c
theorem Epidemics.Revisited.pushPull_prob_not_mem {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(((pushPull n).K S).prob fun (T : Finset (Fin n)) => x ∉ T) = (1 - 1 / ↑n) ^ S.card * (1 - ↑S.card / ↑n)
theorem Epidemics.Revisited.pushPull_prob_not_mem₂ {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(((pushPull n).K S).prob fun (T : Finset (Fin n)) => x ∉ T ∧ y ∉ T) = (1 - 2 / ↑n) ^ S.card * (1 - ↑S.card / ↑n) ^ 2

Elementary inequalities #

theorem Epidemics.Revisited.two_le_of_ne {n : ℕ} {x y : Fin n} (hxy : x ≠ y) :
2 ≤ n
theorem Epidemics.Revisited.one_sub_pow_le_quad {x : ℝ} (hx0 : 0 ≤ x) (hx1 : x ≤ 1) (k : ℕ) :
(1 - x) ^ k ≤ 1 - ↑k * x + (↑k * x) ^ 2 / 2

Second-order Bonferroni: (1 - x)^k ≤ 1 - k x + (k x)² / 2 for 0 ≤ x ≤ 1.

theorem Epidemics.Revisited.exp_le_one_add_two_mul {t : ℝ} (ht0 : 0 ≤ t) (ht1 : t ≤ 1) :
Real.exp t ≤ 1 + 2 * t

e^t ≤ 1 + 2t on [0, 1].

theorem Epidemics.Revisited.push_stay_le {n k : ℕ} (hn : 0 < ↑n) (hk : ↑k ≤ ↑n) :
(1 - 1 / ↑n) ^ k ≤ Real.exp (-1) + 2 / Real.exp 1 * ((↑n - ↑k) / ↑n)

Push, shrinking regime: (1 - 1/n)^k ≤ e^{-1} + (2/e)((n - k)/n) for k ≤ n.

One-round probabilities and covariances #

theorem Epidemics.Revisited.push_informProb_proof {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(push n).informProb S x = 1 - (1 - 1 / ↑n) ^ S.card
theorem Epidemics.Revisited.pull_informProb_proof {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(pull n).informProb S x = ↑S.card / ↑n
theorem Epidemics.Revisited.pushPull_informProb_proof {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(pushPull n).informProb S x = 1 - (1 - 1 / ↑n) ^ S.card * (1 - ↑S.card / ↑n)
theorem Epidemics.Revisited.two_pow_le {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hxy : x ≠ y) :
(1 - 2 / ↑n) ^ S.card ≤ ((1 - 1 / ↑n) ^ S.card) ^ 2
theorem Epidemics.Revisited.push_cov_nonpos_proof {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(push n).cov S x y ≤ 0
theorem Epidemics.Revisited.pull_cov_eq_zero_proof {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(pull n).cov S x y = 0
theorem Epidemics.Revisited.pushPull_cov_nonpos_proof {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(pushPull n).cov S x y ≤ 0

The conditions #

theorem Epidemics.Revisited.card_le_n {n : ℕ} (S : Finset (Fin n)) :
↑S.card ≤ ↑n
theorem Epidemics.Revisited.push_upperGrowth_proof {n : ℕ} :
(push n).UpperGrowth 1 (1 / 2) 0 0 (1 / 2)
theorem Epidemics.Revisited.frac_le_rpow {n : ℕ} {u : ℝ} (hn : 0 < ↑n) (hu : u ≤ ↑n ^ (1 - 1 / 2)) :
u / ↑n ≤ ↑n ^ (-(1 / 2))
theorem Epidemics.Revisited.pushPull_stay_le {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
1 - (pushPull n).informProb S x ≤ (↑n - ↑S.card) / ↑n