Documentation

ThreeMajority.ManyOpinionsExpect

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).

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.

theorem ThreeMajority.colourCount_eq_card_filter {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (a : σ) :
colourCount c a = {v : Fin n | c v = a}.card

The support of colour a.

theorem ThreeMajority.stepCol_apply {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (r : Tgt3 n) (v : Fin n) :
stepCol c r v = if c (r v).2.1 = c (r v).2.2 then c (r v).2.1 else c (r v).1

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).

def ThreeMajority.adoptInd {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (a : σ) :
Fin n → (s : Fin n × Fin n × Fin n) → ℝ

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
Instances For
    theorem ThreeMajority.adoptInd_zero_one {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (a : σ) (v : Fin n) (s : Fin n × Fin n × Fin n) :
    adoptInd c a v s = 0 ∨ adoptInd c a v s = 1
    theorem ThreeMajority.colourCount_stepCol_eq_sum {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (a : σ) (r : Tgt3 n) :
    ↑(colourCount (stepCol c r) a) = ∑ v : Fin n, adoptInd c a v (r v)

    The support of colour a after one round is the sum of the agents' adoption indicators.

    theorem ThreeMajority.image_runCol_subset {n : ℕ} {σ : Type u_1} [DecidableEq σ] (x : Fin n → σ) (l : List (Tgt3 n)) :

    3-Majority never creates a colour along a trajectory.

    theorem ThreeMajority.numColours_runCol_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] (x : Fin n → σ) (l : List (Tgt3 n)) :

    The number of colours never increases along a trajectory.

    theorem ThreeMajority.numColours_runCol_lt_of_dead {n : ℕ} {σ : Type u_1} [DecidableEq σ] (x : Fin n → σ) (l : List (Tgt3 n)) {a : σ} (ha : 0 < colourCount x a) (h0 : colourCount (runCol x l) a = 0) :

    If a colour of x has died, fewer colours remain.

    theorem ThreeMajority.avg_adoptInd {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] [NeZero n] (c : Fin n → σ) (a : σ) (v : Fin n) :
    avg (adoptInd c a v) = ↑(colourCount c a) / ↑n * (1 + ↑(colourCount c a) / ↑n - ∑ b : σ, (↑(colourCount c b) / ↑n) ^ 2)

    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).

    theorem ThreeMajority.avg_colourCount_stepCol {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] [NeZero n] (c : Fin n → σ) (a : σ) :
    (avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)) = ↑(colourCount c a) * (1 + ↑(colourCount c a) / ↑n - ∑ b : σ, (↑(colourCount c b) / ↑n) ^ 2)

    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²).

    theorem ThreeMajority.sum_image_colourCount {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) :
    ∑ b ∈ Finset.image c Finset.univ, ↑(colourCount c b) = ↑n

    The supports of the remaining colours add up to n.

    theorem ThreeMajority.sq_le_numColours_mul_sum_sq {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] (c : Fin n → σ) :
    ↑n ^ 2 ≤ ↑(numColours c) * ∑ b : σ, ↑(colourCount c b) ^ 2

    ∑_b c_b² ≥ n² / |W| for the set W of remaining colours (Cauchy–Schwarz).

    theorem ThreeMajority.avg_colourCount_stepCol_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] [Finite σ] (c : Fin n → σ) (a : σ) :
    (avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)) ≤ ↑(colourCount c a) * (1 + ↑(colourCount c a) / ↑n - 1 / ↑(numColours c))

    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.

    theorem ThreeMajority.event_ofStep_stepCol {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] [NeZero n] (P : (Fin n → σ) → Prop) [DecidablePred P] (T : ℕ) (x : Fin n → σ) :
    (Dynamics.Kernel.ofStep stepCol).event P T x = expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if P (runCol x l) then 1 else 0

    An event of the round-based kernel of 3-Majority, as an expList over the rounds.

    theorem ThreeMajority.prob_ofStep_numColours_lt {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] [NeZero n] (j : ℕ) (x : Fin n → σ) (hx : numColours x < j) :
    ((Dynamics.Kernel.ofStep stepCol x).prob fun (y : Fin n → σ) => numColours y < j) = 1

    "Fewer than j colours" is absorbing for the round-based kernel of 3-Majority.