Documentation

ThreeMajority.Growth

Growth phase #

While the opinion-1 fraction x is in [3/5, 3/4] (i.e. bias β = x - 1/2 ∈ [1/10, 1/4]), the majority map amplifies the bias by a factor ≥ 5/4 per round in expectation (Corollary growth, folded into the numeric argument below); growth_round shows this is realized with probability ≥ 1 - exp(-c₁n) even with only a guaranteed 11/10 factor of slack. growth_fail_le glues 10 such rounds by induction (exactly the expList-conditioning idiom of the push protocol's Main.lean), taking the bias from 1/10 to strictly above 1/4 (opinion-1 fraction > 3/4) except with probability ≤ 10 exp(-c₁n).

Unlike the push protocol's growth phase (informed sets only grow, so a counting argument over "good rounds" suffices), the 3-majority count is not monotone in the round index, so every round genuinely needs the Chernoff bound (Dynamics.avg_chernoff_lower_log) — there is no way to get by with a purely combinatorial argument here.

noncomputable def ThreeMajority.growthBias (j : ℕ) :

The deterministic bias target after j growth rounds.

Equations
Instances For
    theorem ThreeMajority.growth_round {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) {β : ℝ} (hβ0 : 1 / 10 ≤ β) (hβ1 : β ≤ 1 / 4) (hI : ↑n * (1 / 2 + β) ≤ ↑I.card) :
    (avg fun (r : Tgt3 n) => if ↑(step I r).card ≤ ↑n * (1 / 2 + 11 / 10 * β) then 1 else 0) ≤ Real.exp (-(1 / 10 ^ 7) * ↑n)

    Single growth round: starting from opinion-1 fraction ≥ 1/2+β (β the current bias, 1/10 ≤ β ≤ 1/4), the probability of failing to reach the next bias target (guaranteed growth factor 11/10, comfortably below the true drift factor 5/4) is at most exp(-n/10^7).

    theorem ThreeMajority.growth_fail_le {n : ℕ} (hn : 1 ≤ n) (j i : ℕ) :
    i + j ≤ 10 → ∀ (I : Finset (Fin n)), ↑n * (1 / 2 + growthBias i) ≤ ↑I.card → (expList (Tgt3 n) j fun (l : List (Tgt3 n)) => if ↑n * (1 / 2 + growthBias (i + j)) ≤ ↑(run I l).card then 0 else 1) ≤ ↑j * Real.exp (-(1 / 10 ^ 7) * ↑n)

    Union bound over j growth rounds, starting from bias growthBias i (offset i, with i + j ≤ 10 so the bias never leaves [1/10, 1/4]): the probability of failing to reach the bias target growthBias (i+j) is at most j · exp(-n/10⁷). Mirrors the expList-conditioning idiom of the push protocol's Main.lean/Growth.lean.

    theorem ThreeMajority.growth_phase1 {n : ℕ} (hn : 1 ≤ n) (I₀ : Finset (Fin n)) (hI₀ : ↑n * (3 / 5) ≤ ↑I₀.card) :
    (expList (Tgt3 n) 10 fun (l : List (Tgt3 n)) => if ↑n * (3 / 4) ≤ ↑(run I₀ l).card then 0 else 1) ≤ 10 * Real.exp (-(1 / 10 ^ 7) * ↑n)

    Phase 1: starting from opinion-1 fraction ≥ 3/5, after 10 rounds the opinion-1 fraction exceeds 3/4, except with probability ≤ 10 · exp(-n/10⁷).