Documentation

RumorSpread.OneRound

One-round estimates #

The only place in the development where a probability is computed rather than estimated: for u ∉ I, the probability that u is not contacted in one round is exactly (1 - 1/(n-1)) ^ |I| (avg_not_contacted), by counting round configurations coordinate-by-coordinate.

From it we derive the three estimates of Section 4 of the paper:

theorem RumorPush.card_tgt (n : ℕ) :
Fintype.card (Tgt n) = (n - 1) ^ n
theorem RumorPush.card_subtype_ne_ne {n : ℕ} {v u : Fin n} (hvu : v ≠ u) :
Fintype.card { x : Fin n // x ≠ v ∧ x ≠ u } = n - 2
theorem RumorPush.card_filter_not_contacted {n : ℕ} (I : Finset (Fin n)) (u : Fin n) (hu : u ∉ I) :
{r : Tgt n | ∀ v ∈ I, ↑(r v) ≠ u}.card = (n - 2) ^ I.card * (n - 1) ^ (n - I.card)
theorem RumorPush.avg_not_contacted {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) (u : Fin n) (hu : u ∉ I) :
(Dynamics.avg fun (r : Tgt n) => if u ∈ step I r then 0 else 1) = (1 - 1 / (↑n - 1)) ^ I.card

Contact probability: a fixed uninformed node is missed by all pushes with probability exactly (1 - 1/(n-1)) ^ |I|.

theorem RumorPush.avg_card_step {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) :
(Dynamics.avg fun (r : Tgt n) => ↑(step I r).card) = ↑I.card + (↑n - ↑I.card) * (1 - (1 - 1 / (↑n - 1)) ^ I.card)

Expected one-round growth (exact formula).

theorem RumorPush.prob_goodRound {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) (hI : I.Nonempty) :
1 / 8 ≤ Dynamics.avg fun (r : Tgt n) => if goodRound I r then 1 else 0

A good round has probability at least 1/8 (reverse Markov).

theorem RumorPush.avg_uninformed_le {n : ℕ} (hn : 2 ≤ n) (I : Finset (Fin n)) (hhalf : n ≤ 2 * I.card) :
(Dynamics.avg fun (r : Tgt n) => ↑n - ↑(step I r).card) ≤ 2 / 3 * (↑n - ↑I.card)

Contraction above one half: once |I| ≥ n/2, the expected number of uninformed nodes shrinks by a factor 2/3 in one round.