The push, pull and push–pull protocols: computations (EPI-8, instances) #
- The uniform calls are independent and uniform coordinates (
prob_calls_forall), so the events "xstays uninformed" and "xandystay uninformed" are products of one-coordinate events and their probabilities are explicit. covis rewritten through the "uninformed" events by inclusion–exclusion (cov_eq).- Elementary inequalities: the second-order Bonferroni bound
(1 - x)^k ≤ 1 - k x + (k x)² / 2ande^t ≤ 1 + 2ton[0, 1].
theorem
Epidemics.Revisited.cov_eq
{n : ℕ}
(P : RumorProcess n)
(S : Finset (Fin n))
(x y : Fin n)
:
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)
:
Push #
Pull #
Push–pull #
Elementary inequalities #
One-round probabilities and covariances #
The conditions #
theorem
Epidemics.Revisited.push_upperGrowth_proof
{n : ℕ}
:
(push n).UpperGrowth 1 (1 / 2) 0 0 (1 / 2)
theorem
Epidemics.Revisited.push_upperShrinking_proof
{n : ℕ}
:
(push n).UpperShrinking 1 (2 / Real.exp 1) 0 (1 / 2)
theorem
Epidemics.Revisited.pull_upperDoubleShrinking_proof
{n : ℕ}
:
(pull n).UpperDoubleShrinking 2 1 0 (1 / 2) (1 / 2)
theorem
Epidemics.Revisited.pull_fastFinishing_proof
{n : ℕ}
:
(pull n).FastFinishing (1 / 2) (1 / 2)
theorem
Epidemics.Revisited.pushPull_upperGrowth_proof
{n : ℕ}
:
(pushPull n).UpperGrowth 2 (3 / 4) 0 0 (1 / 2)
theorem
Epidemics.Revisited.pushPull_upperDoubleShrinking_proof
{n : ℕ}
:
(pushPull n).UpperDoubleShrinking 2 1 0 (1 / 2) (1 / 2)
theorem
Epidemics.Revisited.pushPull_fastFinishing_proof
{n : ℕ}
:
(pushPull n).FastFinishing (1 / 2) (1 / 2)