One round of 3-Majority with many colours (BCNPT16, Lemma 2.1; roadmap MAJ-12 (a)) #
Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many opinions,
SODA 2016, arXiv:1508.06782 (BCNPT16 below), Section 2, for the model stepCol of
ThreeMajority.AnyStartModel (an agent adopts the colour of its second and third samples if they
agree, and the colour of its first sample otherwise: the rule of BCNPT16, Section 2).
adoptInd c a v s: agentvadopts colourawith the sample triples. In a uniformly random round the agents' triples are independent, so the new support ofais the sum∑ v, adoptInd c a v (r v)of independent{0,1}variables (colourCount_stepCol_eq_sum), each with meanx_a (1 + x_a − ‖x‖₂²),x = c/n(avg_adoptInd). This is the form consumed by the Chernoff boundsDynamics.avg_chernoff_*and by anti-concentration.avg_colourCount_stepCol,avg_colourCount_stepCol_le: Lemma 2.1 (BCNPT16, Equation (1)),𝔼[C_a'] = c_a (1 + c_a/n − ∑_b c_b²/n²) ≤ c_a (1 + c_a/n − 1/|W|)withWthe set of remaining colours.
The model, unfolded #
These three equations are pinned with the statements of roadmap MAJ-12 (a), so that the meaning
of numColours, colourCount and stepCol is frozen together with the statements using them.
The number of colours of a configuration.
The support of colour a.
One round of 3-Majority: agent v with samples r v = (s₁, s₂, s₃) adopts the colour of
s₂ if s₂ and s₃ agree, and the colour of s₁ otherwise (BCNPT16, Section 2).
Agent v's indicator of adopting colour a in a round where its sample triple is s
(the agent index is not used: all agents follow the same rule).
Equations
- ThreeMajority.adoptInd c a x✝ s = if ThreeMajority.majColour c s = a then 1 else 0
Instances For
The support of colour a after one round is the sum of the agents' adoption indicators.
3-Majority never creates a colour along a trajectory.
The number of colours never increases along a trajectory.
If a colour of x has died, fewer colours remain.
The probability that one agent adopts colour a: x_a (1 + x_a − ‖x‖₂²) with x = c/n
(BCNPT16, proof of Lemma 2.1 in Appendix A; Equation (2) of BCEKMN17, alpha3M_weight).
Lemma 2.1 (BCNPT16, Equation (1), equality): the expected support of colour a after
one round is c_a (1 + c_a/n − ∑_b c_b²/n²).
The supports of the remaining colours add up to n.
∑_b c_b² ≥ n² / |W| for the set W of remaining colours (Cauchy–Schwarz).
Lemma 2.1 (BCNPT16, Equation (1), inequality): the expected support of colour a after
one round is at most c_a (1 + c_a/n − 1/|W|), where |W| is the number of remaining colours.
Colours below the average n/|W| shrink in expectation.
An event of the round-based kernel of 3-Majority, as an expList over the rounds.
"Fewer than j colours" is absorbing for the round-based kernel of 3-Majority.