The general upper bound (Theorem 3.8) #
If m is the unique plurality color, c_m ≥ n/λ for some λ ≥ 3 and the
bias is at least Λ = 22 √(λ n log n), then 3-majority reaches consensus on
m within O(λ log n) rounds with high probability.
The proof runs the chain through nested phases and applies
Dynamics.Kernel.nested_phases (the paper's Lemma A.4) to kernel maj3.
- Growth phases
growthSet i: eitherc_m > 2n/3, ormis the unique plurality color withc_m ≥ n/λand bias at leastΛ (1 + 1/(6λ))^i. Lemma 3.5 moves the chain from phaseitoi + 1, applied to every other color that currently has a node (colors without nodes stay empty). OnceΛ (1 + 1/(6λ))^i > nthe second alternative is impossible, so the chain hasc_m > 2n/3. - Saturation phases
satSet j: fewer thanmax ((n/3)(17/18)^j, n^{1/4} log n)nodes disagree withm. By Lemma 3.7 this threshold shrinks by17/18per round down ton^{1/4} log n. - Consensus
monoSet: from belown^{1/4} log ndissenters, one round reaches consensus except with probabilityn^{-1/5}(Lemma 3.7).
Differences from the paper #
- The paper's saturation sets also require
s(c) ≥ n/3, which Lemma 3.7 does not show is preserved. Here the saturation sets only boundn - c_m < n/3, which already implies a unique plurality color ands(c) ≥ n/3(of_dissent_lt). - The paper charges each growth round
1/n², but Lemma 3.5 bounds the failure against one competing color, so a round needs a union bound over all of them. Only colors that currently have a node matter (the others stay empty), and there are fewer thann - c_mof them, so a round fails with probability at most1/n. The final failure probability is thereforeO(λ log n / n)instead ofO(λ log n / n²). - The hypothesis
λ < √nof the paper is not needed for the proof. It only makes the bias hypothesis satisfiable (Λ ≤ n) and the bound nontrivial. - "Sufficiently large
n" islog n ≥ 40, andk ≥ 2excludes the trivial single-color case.
The phases #
Growth phase i: c_m > 2n/3, or m is the unique plurality color with at
least n/λ nodes and bias at least Λ (1 + 1/(6λ))^i.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Saturation phase j: fewer than max ((n/3)(17/18)^j) (n^{1/4} log n)
nodes disagree with m.
Equations
Instances For
Consensus on m.
Equations
- Plurality.monoSet n m = {x : Plurality.Config n k | Plurality.Mono x m}
Instances For
Bookkeeping for one round #
Counting facts #
Saturation phases #
Growth phases #
One growth round (Lemma 3.5 and a union bound over the colors that
have nodes). From growth phase i, the chain is in growth phase i + 1 after
one round except with probability 1/n.
Theorem 3.8 #
The total number of phases, T = T₁ + T₂ + 1; the process runs for 10 T rounds.
Equations
- Plurality.phases n lam = Plurality.growthPhases n lam + Plurality.satPhases n + 1
Instances For
Theorem 3.8 (the general upper bound). Let λ ≥ 3, log n ≥ 40 and
k ≥ 2. If m is the unique plurality color of x, c_m ≥ n/λ and
s(c) ≥ 22 √(λ n log n), then after 10 T rounds, where
T = phases n λ ≤ 13 λ log n (phases_le), every node supports m with
probability at least 1 - 11 T / n.
Theorem 3.8, O(λ log n) form. Under the hypotheses of theorem_3_8,
consensus on m holds after 10 T ≤ 130 λ log n rounds with probability at
least 1 - 143 λ log n / n.