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:
avg_tgt_coord— a single call is uniform among the othern - 1nodes;avg_call_mem,avg_call_not_mem— a callerv ∉ Icalls intoIwith probability|I|/(n-1);avg_call_ne— a callerwmisses a fixed nodev ≠ wwith probability1 - 1/(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 → ℝ)
:
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.