The symmetry-breaking stage (BCNPT16, Lemma 3.3; roadmap MAJ-12 (a)) #
Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many opinions,
SODA 2016, arXiv:1508.06782 (BCNPT16 below), Section 3. From a configuration with j colours,
the smallest support c_π drifts down by Ξ΄ βn / j^{3/2} per round (Equation (3)) as long as
every colour has more than n/j β 16 β(j n log n) agents, and one round overshoots below
n/j β 64 β(j n log n) with probability at most 1/nΒ² (Equation (6), Lemma B.1). The additive
drift lemma (hitProb_additive_drift, Lemma 3.2) then gives Lemma 3.3: within
O(jΒ² β(log n)) rounds, with probability at least 1/2, some colour falls to
n/j β 16 β(j n log n) agents or dies.
BrokenSymmetry j x: the exit condition of the stage forjcolours.min_count_drift: Equation (3) (Hypothesis 1 of Lemma 3.2 forY = βn/jβ β c_π).min_count_overshoot: Equation (6) (Hypothesis 2 of Lemma 3.2; Lemma B.1), in one-step form.symmetry_breaking: Lemma 3.3, as a hitting probability of the round-based kernel.
Equation (6) is a Chernoff lower tail at n/j β 64 β(j n log n) with mean at least
n/j β 32 β(j n log n) (le_avg_colourCount_stepCol_of_forall_lt) and a union bound over the
colours. Equation (3) has two cases: far from uniform, Lemma 2.1 for the smallest colour
(Equation (5)); near uniform, the paper's Central Limit Theorem step (Equation (4)) is replaced by
the pointwise bound min_a C_a' β€ n/j β (1/(2j)) β_a |C_a' β n/j| (inf'_colourCount_le) and the
anti-concentration πΌ|C_a' β n/j| β₯ (9/256) Ο_a (avg_abs_colourCount_stepCol_sub_ge,
PaleyβZygmund) with Ο_aΒ² β₯ n/(4j) (sum_variance_adoptInd_ge).
The paper assumes nothing on j in Lemma 3.3, but its proof uses c_π β₯ n/(2j) whenever
c_π > n/j β β(j n log n), which needs jΒ³ log n = O(n); the statements here assume
C jΒ³ log n β€ n (implied by the standing assumption j β€ n^{1/3 β Ξ΅} of Section 3 for large
n). The threshold is 16 β(j n log n) instead of β(j n log n), for the dropping stage
(Lemma 3.4, dropping_stage1).
The exit condition of the symmetry-breaking stage for j colours (BCNPT16, Lemma 3.3, with
the threshold 16 β(j n log n)): fewer than j colours remain, or at most j colours remain
and one of them has between 1 and n/j β 16 β(j n log n) agents.
Equations
- One or more equations did not get rendered due to their size.
Instances For
BrokenSymmetry unfolded. (Pinned, so that the definition is frozen together with the
statements that use it.)
A configuration of n β₯ 1 agents has a colour.
The smallest support among the colours of x, at most the average n / numColours x.
The potential of the symmetry-breaking stage for j colours.
Equations
- ThreeMajority.breakPotential j y = if ThreeMajority.numColours y < j then βn / βj else βn / βj - (Finset.image y Finset.univ).inf' β― fun (a : Fin n) => β(ThreeMajority.colourCount y a)
Instances For
After rounds from x with j colours, the potential is n/j minus the smallest support
among the colours of x (dead colours count 0).
Outside BrokenSymmetry j, a configuration with at most j colours has exactly j colours,
all above the threshold.
Equation (3) (BCNPT16, proof of Lemma 3.3, Hypothesis 1 of Lemma 3.2): there are
constants Ξ΄ > 0 and C such that, for every configuration x with j β₯ 2 colours,
C jΒ³ log n β€ n and every colour above n/j β 16 β(j n log n) agents, the smallest support
among the colours of x decreases in expectation by at least Ξ΄ βn / j^{3/2} in one round
(a colour that dies counts with support 0).
Equation (6) (BCNPT16, proof of Lemma 3.3, Hypothesis 2 of Lemma 3.2; Lemma B.1), in
one-step form: there is C such that, for every configuration x with j β₯ 2 colours,
C jΒ³ log n β€ n and every colour above n/j β 16 β(j n log n) agents, after one round some
colour of x is below n/j β 64 β(j n log n) agents with probability at most 1/nΒ².
Lemma 3.3 (BCNPT16, symmetry-breaking stage): there is C such that, from every
configuration c with j β₯ 2 colours and C jΒ³ log n β€ n, 3-Majority reaches
BrokenSymmetry j (some colour falls to n/j β 16 β(j n log n) agents, or dies) within any
t β₯ C jΒ² β(log n) rounds with probability at least 1/2.