Two opinions from any configuration #
Binary 3-Majority reaches consensus from any configuration, including the perfectly balanced
one, within O(log n) rounds with high probability (Becchetti, Clementi, Natale, Consensus
dynamics: an overview, SIGACT News 2020, §4 Case 3, where the argument is given for the binary
median dynamics of Doerr, Goldberg, Minder, Sauerwald, Scheideler, SPAA 2011).
The gap s = |I| - (n - |I|) evolves in two stages.
- Symmetry breaking (
majority3_symmetry_breaking). Near balance the expected drift of the gap is too weak for step-by-step concentration. Instead, by the variance of one round, the gap jumps to order√nwith constant probability (jump_near_balance), and above that it grows by a constant factor except with probability exponentially small in its size (growth_far). The hitting-time bound of Doerr et al. (Claim 2.9,Dynamics.Kernel.drift_hitting_log), applied toX = ⌊|s| / (√n / 100)⌋, then shows that|s|reaches22 √(3 n log n)withinO(log n)rounds except with probability1/n. - Vanishing bias (
majority3_vanishing_bias). From a gap22 √(3 n log n), consensus follows within390 log nrounds with probability1 - 429 log n / n; a negative gap is the same statement for the complementary set.
Binary 3-Majority as a finite Markov kernel on the set of nodes holding opinion 1.
Instances For
The gap and the complement symmetry #
Exchanging the two opinions commutes with a round.
gap (step I r) = 2 ∑ᵥ Yᵥ - n for the independent {0,1} contributions Yᵥ of the
nodes.
The mean of the next gap #
A √n jump near balance (the variance of one round). If the gap is at most 4√n/25 in
absolute value and n ≥ 5, then after one round it is at least √n/5 in absolute value with
probability at least 9/64.
Growth above √n (the drift of one round, with Hoeffding's inequality). If
0 ≤ s ≤ n/2 for the gap s, then for every λ ≥ 0 the next gap exceeds 11 s/8 - 2λ except
with probability at most exp (-2λ²/n).
Symmetry breaking: the hypotheses of the hitting-time bound #
Above √n (16 ≤ X < 1000 log n, gap ≥ 0): by growth_far with λ = X √n / 3200,
X grows to at least 5X/4 except with probability exp (-X²/5120000) ≤ exp (-X/320000).
Symmetry breaking. There is C > 0 such that, for log n ≥ 40, from any configuration
I₀ the gap reaches 22 √(3 n log n) in absolute value within any t ≥ C log n rounds with
probability at least 1 - 1/n.
Consensus absorbs; the vanishing-bias stage as a kernel event #
The occupation probability of consensus, as an expectation over rounds.
The vanishing-bias stage (majority3_vanishing_bias, applied to I or to its
complement): from a gap at least 22 √(3 n log n) in absolute value, consensus holds after
10 · phases n 3 ≤ 390 log n rounds with probability at least 1 - 429 log n / n.
Binary 3-Majority from any configuration. There is C > 0 such that, for log n ≥ 40,
from any configuration I₀ (in particular from a perfectly balanced one), all nodes hold the same
opinion after any T ≥ C log n rounds with probability at least 1 - C log n / n.
Binary 3-Majority from any configuration, with high probability. There is C > 0 such
that, for log n ≥ C, from any configuration I₀ all nodes hold the same opinion after any
T ≥ C log n rounds with probability at least 1 - 1/n. It runs majority3_any_start twice:
each block fails with probability at most ε = C₀ log n / n from every configuration, and
consensus absorbs, so both fail with probability at most ε² ≤ 1/n.