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.
The deterministic bias target after j growth rounds.
Equations
- ThreeMajority.growthBias j = 1 / 10 * (11 / 10) ^ j
Instances For
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).
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.