Documentation

Plurality.Binary

Two colors: the existing binary 3-majority development #

For k = 2 the 3-majority round step is literally the two-opinion process of ThreeMajority: the set of nodes of color 1 evolves by ThreeMajority.step, round by round and for every realization of the samples (colorSet_step, colorSet_run). The one-round bridge is the bridge ThreeMajority.stepCol_bool of the model with colours of any type, through step_eq_stepCol and the renaming of the colors Fin 2 as Bool. The binary consensus theorem ThreeMajority.majority3_consensus_whp therefore holds for two colors as stated, through colorSet_run and mono_one_iff_colorSet: from a 60% majority, 3-majority with two colors reaches the majority color within O(log n) rounds with probability 1 - O(1/n).

This is the k = 2 instance of the paper's Corollary 3.12 (large plurality, λ = Θ(1)), obtained by reusing the existing statement rather than by re-proving it.

def Plurality.colorSet {n k : ℕ} (x : Config n k) (j : Fin k) :

The set of nodes of a given color.

Equations
Instances For
    theorem Plurality.card_colorSet {n k : ℕ} (x : Config n k) (j : Fin k) :
    (colorSet x j).card = count x j

    One round. The color-1 set evolves by the binary 3-majority step: the bridge ThreeMajority.stepCol_bool, with the colors Fin 2 renamed as Bool.

    theorem Plurality.colorSet_run {n : ℕ} (x : Config n 2) (l : List (ThreeMajority.Tgt3 n)) :

    Every trajectory. The color-1 set evolves by ThreeMajority.run.

    Two colors from a vanishing bias #

    def Plurality.ofSet {n : ℕ} (I : Finset (Fin n)) :
    Config n 2

    The two-color configuration with color 1 exactly on I.

    Equations
    Instances For
      theorem Plurality.colorSet_ofSet {n : ℕ} (I : Finset (Fin n)) :
      colorSet (ofSet I) 1 = I
      theorem Plurality.count_ofSet_one {n : ℕ} (I : Finset (Fin n)) :
      count (ofSet I) 1 = I.card
      theorem Plurality.count_ofSet_zero {n : ℕ} (I : Finset (Fin n)) :
      count (ofSet I) 0 = n - I.card