The 3-majority dynamics with k colors (Section 2) #
n anonymous nodes each support one of k colors; a coloring is a map
Config n k := Fin n → Fin k. At every round each node picks three nodes
uniformly at random (including itself, with repetitions) and recolors itself
according to the majority of the three colors it sees; if it sees three
different colors it takes the first one.
The randomness of a round is exactly that of the binary development:
ThreeMajority.Tgt3 n = Fin n → Fin n × Fin n × Fin n, one ordered triple of
samples per node, drawn uniformly. Multi-round expectations are
Dynamics.expList (Tgt3 n) T, and kernel f is the same process as a
finite Markov kernel (Dynamics.Kernel.ofStep), which is how the phase
lemma Dynamics.Kernel.nested_phases (the paper's Lemma A.4) applies.
Section 4.2 of the paper compares 3-majority with an arbitrary deterministic
3-input rule f : Fin k → Fin k → Fin k → Fin k, so the round is defined for
any such rule (stepWith f) and 3-majority is the instance f = maj3.
The 3-majority round itself is defined once, for colours of any type, as
ThreeMajority.stepCol (ThreeMajority.AnyStartModel): step, run and count are
ThreeMajority.stepCol, ThreeMajority.runCol and ThreeMajority.colourCount at colours
Fin k (step_eq_stepCol, run_eq_runCol, count_eq_colourCount).
A coloring of n nodes with k colors.
Equations
- Plurality.Config n k = (Fin n → Fin k)
Instances For
One synchronous round of the 3-input dynamics with rule f: node v
sees the colors of its three samples r v and adopts f of them.
Equations
- Plurality.stepWith f x r v = f (x (r v).1) (x (r v).2.1) (x (r v).2.2)
Instances For
One round of the 3-majority dynamics.
Equations
Instances For
The coloring after consuming a list of rounds with rule f.
Equations
- Plurality.runWith f x l = List.foldl (Plurality.stepWith f) x l
Instances For
The coloring after consuming a list of rounds of 3-majority.
Equations
Instances For
One model. The round of 3-majority is the round ThreeMajority.stepCol of
3-Majority with colours of any type, at colours Fin k: maj3 is the rule
ThreeMajority.majColour on the colours of the three samples.
The process run is ThreeMajority.runCol at colours Fin k.
Color counts #
count is the configuration vector ThreeMajority.colourCount at colours Fin k.
x is monochromatic of color j: every node supports j.
Equations
- Plurality.Mono x j = ∀ (v : Fin n), x v = j
Instances For
Equations
x is monochromatic (in some color).
Equations
- Plurality.Monochromatic x = ∃ (j : Fin k), Plurality.Mono x j
Instances For
A 3-input rule that always returns one of its inputs keeps a monochromatic coloring monochromatic: consensus is absorbing.
The Markov kernel #
Rounds exist when n ≠ 0: the instance Nonempty (Tgt3 n) for [NeZero n] is the one of
ThreeMajority.AnyStartModel.
The dynamics with rule f as a finite Markov kernel on colorings.
Equations
Instances For
Probabilities at time T for the kernel are expectations over T
independent rounds.