3-Majority is at least as fast as Voter (BCEKMN17, Lemma 2) #
Both processes are anonymous consensus processes (Definition 1), with the process functions
alpha3M and alphaVoter, defined here as the law of the colour adopted by one agent: the
image of one uniform sample triple under majColour c, resp. of one uniform sample under c.
alphaVoter_weight,alpha3M_weight: Equations (1) and (2),α^V_a(c) = x_aandα^{3M}_a(c) = x_a (1 + x_a − ‖x‖₂²)withx = c/n.apply_ofStep_stepCol,apply_ofStep_voterStep: one uniformly random round of the round-based processesstepColandvoterStepis one step of the AC-processesalpha3MandalphaVoter(the agents' samples are independent).dominates_alpha3M_alphaVoter: the inequality proved in Lemma 2,c ⪰ c'impliesα^{3M}(c) ⪰ α^V(c').voter_le_threeMaj: Lemma 2, started from the same configuration, 3-Majority has at mostκcolours at timeTwith at least the probability that Voter has.
The process function of 3-Majority (BCEKMN17, Section 2.2): the law of majColour c s for
a uniform sample triple s.
Equations
- ThreeMajority.alpha3M c = (Dynamics.Distribution.uniform (Fin n × Fin n × Fin n)).map (ThreeMajority.majColour c)
Instances For
The 3-Majority indicator: [maj = a] = [x₂ = a][x₃ = a] + [x₁ = a] - [x₂ = x₃][x₁ = a].
The number of sample triples whose 3-Majority colour is a.
Drawing every coordinate independently from (p i).map g is applying g coordinatewise
to independent draws from the p i.
The weight of a pushed-forward uniform law is a normalized fibre count.
Equation (1) (BCEKMN17): α^V_a(c) = c_a / n.
Equation (2) (BCEKMN17): with x = c/n, α^{3M}_a(c) = x_a (1 + x_a − ‖x‖₂²).
One uniformly random round of stepCol is one step of the AC-process alpha3M
(3-Majority is an AC-process, BCEKMN17, Section 2.2).
One uniformly random round of voterStep is one step of the AC-process alphaVoter
(Voter is an AC-process, BCEKMN17, Section 2.2).
Among the sets of a given size, one of maximal x-sum is a top set: its entries are at
least the entries outside it (exchange argument).
The colour fractions of a configuration sum to one.
The inequality of the proof of Lemma 2 (BCEKMN17): 3-Majority dominates Voter,
c ⪰ c' implies α^{3M}(c) ⪰ α^V(c').
Lemma 2 (BCEKMN17): started from the same configuration c, after T rounds
3-Majority has at most κ colours with at least the probability that Voter has. Since neither
process creates colours, this is T^κ_{3M}(c) ≤st T^κ_V(c).