Documentation

RumorSpread.PullPhases

The two-phase argument for an arbitrary inflationary spreading step #

The PUSH proof (Growth.lean, Saturation.lean, Main.lean) only uses two one-round facts about step: a round is good (grows the informed set by 9/8, or starts above n/2) with probability ≥ 1/8, and above n/2 the expected number of uninformed nodes contracts by 2/3. This file runs the same argument for any step f : Finset (Fin n) → α → Finset (Fin n) that is inflationary (I ⊆ f I a), driven by i.i.d. uniform rounds a : α, with trajectories l.foldl f I:

It is instantiated for PULL in PullMain.lean.

def RumorPush.goodRoundOf {n : ℕ} {α : Type u_1} (f : Finset (Fin n) → α → Finset (Fin n)) (I : Finset (Fin n)) (a : α) :

A round a is good for the step f if it multiplies the informed set by at least 9/8, or if more than half of the nodes are already informed (goodRound for a general step).

Equations
Instances For
    @[implicit_reducible]
    instance RumorPush.instDecidableGoodRoundOf {n : ℕ} {α : Type u_1} (f : Finset (Fin n) → α → Finset (Fin n)) (I : Finset (Fin n)) (a : α) :
    Equations
    def RumorPush.goodCountOf {n : ℕ} {α : Type u_1} (f : Finset (Fin n) → α → Finset (Fin n)) (I : Finset (Fin n)) :
    List α → ℕ

    The number of good rounds along a trajectory of the step f.

    Equations
    Instances For
      @[simp]
      theorem RumorPush.goodCountOf_nil {n : ℕ} {α : Type u_1} (f : Finset (Fin n) → α → Finset (Fin n)) (I : Finset (Fin n)) :
      theorem RumorPush.goodCountOf_cons {n : ℕ} {α : Type u_1} (f : Finset (Fin n) → α → Finset (Fin n)) (I : Finset (Fin n)) (a : α) (l : List α) :
      goodCountOf f I (a :: l) = (if goodRoundOf f I a then 1 else 0) + goodCountOf f (f I a) l
      theorem RumorPush.pow_goodCountOf_mul_card_le {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (I : Finset (Fin n)) (l : List α) (h : 2 * (List.foldl f I l).card ≤ n) :
      (9 / 8) ^ goodCountOf f I l * ↑I.card ≤ ↑(List.foldl f I l).card

      Deterministic growth: if the final informed set is at most n/2, each good round multiplied the informed set by 9/8 (as pow_goodCount_mul_card_le_card_run).

      theorem RumorPush.avg_half_pow_goodOf {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] [Nonempty α] {I : Finset (Fin n)} (hgood : 1 / 8 ≤ Dynamics.avg fun (a : α) => if goodRoundOf f I a then 1 else 0) :
      (Dynamics.avg fun (a : α) => (1 / 2) ^ if goodRoundOf f I a then 1 else 0) ≤ 15 / 16

      Per-round exponential moment of the good-round indicator.

      theorem RumorPush.expList_half_pow_goodCountOf {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] [Nonempty α] (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (hgood : ∀ (I : Finset (Fin n)), I.Nonempty → 1 / 8 ≤ Dynamics.avg fun (a : α) => if goodRoundOf f I a then 1 else 0) (T : ℕ) (I : Finset (Fin n)) :
      I.Nonempty → (Dynamics.expList α T fun (l : List α) => (1 / 2) ^ goodCountOf f I l) ≤ (15 / 16) ^ T

      Exponential-moment bound for adaptive trials (as expList_half_pow_goodCount): 𝔼[(1/2) ^ (number of good rounds in T rounds)] ≤ (15/16) ^ T.

      theorem RumorPush.phase1Of {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] [Nonempty α] (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (hgood : ∀ (I : Finset (Fin n)), I.Nonempty → 1 / 8 ≤ Dynamics.avg fun (a : α) => if goodRoundOf f I a then 1 else 0) (v₀ : Fin n) (L T₁ : ℕ) (hL : ↑n ≤ (9 / 8) ^ L) :
      (Dynamics.expList α T₁ fun (l : List α) => if 2 * (List.foldl f {v₀} l).card ≤ n then 1 else 0) ≤ 2 ^ L * (15 / 16) ^ T₁

      Phase 1 (as phase1): if (9/8)^L ≥ n, then after T₁ rounds the informed set is still ≤ n/2 with probability at most 2^L · (15/16)^T₁.

      theorem RumorPush.saturationOf {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (hsat : ∀ (I : Finset (Fin n)), n ≤ 2 * I.card → (Dynamics.avg fun (a : α) => ↑n - ↑(f I a).card) ≤ 2 / 3 * (↑n - ↑I.card)) (T : ℕ) (I : Finset (Fin n)) :
      n ≤ 2 * I.card → (Dynamics.expList α T fun (l : List α) => ↑n - ↑(List.foldl f I l).card) ≤ (2 / 3) ^ T * (↑n - ↑I.card)

      Phase 2 (as saturation): starting above half, the expected number of uninformed nodes after T further rounds is at most (2/3)^T · (n - |I|).

      theorem RumorPush.notAllOf_le {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] [Nonempty α] (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (hgood : ∀ (I : Finset (Fin n)), I.Nonempty → 1 / 8 ≤ Dynamics.avg fun (a : α) => if goodRoundOf f I a then 1 else 0) (hsat : ∀ (I : Finset (Fin n)), n ≤ 2 * I.card → (Dynamics.avg fun (a : α) => ↑n - ↑(f I a).card) ≤ 2 / 3 * (↑n - ↑I.card)) (v₀ : Fin n) (L T₁ T₂ : ℕ) (hL : ↑n ≤ (9 / 8) ^ L) :
      (Dynamics.expList α (T₁ + T₂) fun (l : List α) => if List.foldl f {v₀} l = Finset.univ then 0 else 1) ≤ 2 ^ L * (15 / 16) ^ T₁ + (2 / 3) ^ T₂ * ↑n

      Gluing the two phases (as prNotAllInformed_le).

      theorem RumorPush.notAllOf_antitone {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] [Nonempty α] (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (I : Finset (Fin n)) {T T' : ℕ} (h : T ≤ T') :
      (Dynamics.expList α T' fun (l : List α) => if List.foldl f I l = Finset.univ then 0 else 1) ≤ Dynamics.expList α T fun (l : List α) => if List.foldl f I l = Finset.univ then 0 else 1

      More rounds never hurt: for an inflationary step, the probability that not all nodes are informed is antitone in the number of rounds.

      theorem RumorPush.rounds_le_ceil_160 {n : ℕ} (hn : 2 ≤ n) :

      The round count of push_informs_all_whp is at most ⌈160 log n⌉.

      theorem RumorPush.notAllOf_le_two_div {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} [Fintype α] [Nonempty α] (hn : 2 ≤ n) (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (hgood : ∀ (I : Finset (Fin n)), I.Nonempty → 1 / 8 ≤ Dynamics.avg fun (a : α) => if goodRoundOf f I a then 1 else 0) (hsat : ∀ (I : Finset (Fin n)), n ≤ 2 * I.card → (Dynamics.avg fun (a : α) => ↑n - ↑(f I a).card) ≤ 2 / 3 * (↑n - ↑I.card)) (v₀ : Fin n) :
      (Dynamics.expList α ⌈160 * Real.log ↑n⌉₊ fun (l : List α) => if List.foldl f {v₀} l = Finset.univ then 0 else 1) ≤ 2 / ↑n

      The two-phase theorem for a general step: if good rounds have probability ≥ 1/8 and the expected uninformed count contracts by 2/3 above half, then after ⌈160 log n⌉ rounds started from one informed node, not all nodes are informed with probability at most 2/n.