Documentation

RumorSpread.PullIndep

Independence of the calls in a uniform round #

A uniform round r : Tgt n is a uniform element of the product ∀ v, {u // u ≠ v}, so the calls r v of different nodes are independent. The core's Dynamics.avg_pi_prod states this for any finite dependent product (Fubini for products of functions of the coordinates, via Fintype.prod_sum), and avg_tgt_mul_prod specializes it to a function of one call r v times a product over calls r w, w ∈ S, with v ∉ S. This covers all the probabilities needed for PULL and PUSH–PULL:

theorem RumorPush.avg_tgt_prod {n : ℕ} (g : Fin n → Fin n → ℝ) :
(Dynamics.avg fun (r : Tgt n) => ∏ v : Fin n, g v ↑(r v)) = ∏ v : Fin n, Dynamics.avg fun (y : { u : Fin n // u ≠ v }) => g v ↑y

The calls of a uniform round are independent (avg_pi_prod for Tgt n).

theorem RumorPush.nonempty_ne {n : ℕ} (hn : 2 ≤ n) (w : Fin n) :
Nonempty { u : Fin n // u ≠ w }
theorem RumorPush.card_ne {n : ℕ} (w : Fin n) :
Fintype.card { u : Fin n // u ≠ w } = n - 1
theorem RumorPush.cast_card_ne {n : ℕ} (hn : 2 ≤ n) (w : Fin n) :
↑(Fintype.card { u : Fin n // u ≠ w }) = ↑n - 1
theorem RumorPush.avg_tgt_mul_prod {n : ℕ} (hn : 2 ≤ n) {v : Fin n} {S : Finset (Fin n)} (hv : v ∉ S) (a : Fin n → ℝ) (b : Fin n → Fin n → ℝ) :
(Dynamics.avg fun (r : Tgt n) => a ↑(r v) * ∏ w ∈ S, b w ↑(r w)) = (Dynamics.avg fun (y : { u : Fin n // u ≠ v }) => a ↑y) * ∏ w ∈ S, Dynamics.avg fun (y : { u : Fin n // u ≠ w }) => b w ↑y

One call times independent other calls: for v ∉ S, the expectation of a function of the call r v times a product of functions of the calls r w, w ∈ S, factorizes.

theorem RumorPush.avg_tgt_coord {n : ℕ} (hn : 2 ≤ n) (v : Fin n) (a : Fin n → ℝ) :
(Dynamics.avg fun (r : Tgt n) => a ↑(r v)) = Dynamics.avg fun (y : { u : Fin n // u ≠ v }) => a ↑y

A single call r v of a uniform round is uniform among the other n - 1 nodes.

theorem RumorPush.avg_call_mem {n : ℕ} (hn : 2 ≤ n) {v : Fin n} {I : Finset (Fin n)} (hv : v ∉ I) :
(Dynamics.avg fun (y : { u : Fin n // u ≠ v }) => if ↑y ∈ I then 1 else 0) = ↑I.card / (↑n - 1)

A caller v ∉ I calls into I with probability |I|/(n-1).

theorem RumorPush.avg_call_not_mem {n : ℕ} (hn : 2 ≤ n) {v : Fin n} {I : Finset (Fin n)} (hv : v ∉ I) :
(Dynamics.avg fun (y : { u : Fin n // u ≠ v }) => if ↑y ∈ I then 0 else 1) = (↑n - 1 - ↑I.card) / (↑n - 1)

A caller v ∉ I calls outside I with probability (n - 1 - |I|)/(n-1).

theorem RumorPush.avg_call_ne {n : ℕ} (hn : 2 ≤ n) {v w : Fin n} (hvw : v ≠ w) :
(Dynamics.avg fun (y : { u : Fin n // u ≠ w }) => if ↑y = v then 0 else 1) = 1 - 1 / (↑n - 1)

A caller w misses a fixed node v ≠ w with probability 1 - 1/(n-1).