Documentation

ThreeMajority.AnyStartVsVoter

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.

noncomputable def ThreeMajority.alpha3M {n : ℕ} [NeZero n] {σ : Type u_1} [Fintype σ] [DecidableEq σ] (c : Fin n → σ) :

The process function of 3-Majority (BCEKMN17, Section 2.2): the law of majColour c s for a uniform sample triple s.

Equations
Instances For
    noncomputable def ThreeMajority.alphaVoter {n : ℕ} [NeZero n] {σ : Type u_1} [Fintype σ] (c : Fin n → σ) :

    The process function of Voter (BCEKMN17, Section 2.2): the law of c u for a uniform agent u.

    Equations
    Instances For
      theorem ThreeMajority.ite_majority_eq {σ : Type u_1} [DecidableEq σ] (x₁ x₂ x₃ a : σ) :
      (if (if x₂ = x₃ then x₂ else x₁) = a then 1 else 0) = (((if x₂ = a then 1 else 0) * if x₃ = a then 1 else 0) + if x₁ = a then 1 else 0) - (if x₂ = x₃ then 1 else 0) * if x₁ = a then 1 else 0

      The 3-Majority indicator: [maj = a] = [x₂ = a][x₃ = a] + [x₁ = a] - [x₂ = x₃][x₁ = a].

      theorem ThreeMajority.sum3_mul_left {n : ℕ} (f g : Fin n → ℝ) :
      ∑ _x : Fin n, ∑ y : Fin n, ∑ z : Fin n, f y * g z = ↑n * ((∑ y : Fin n, f y) * ∑ z : Fin n, g z)
      theorem ThreeMajority.sum3_first {n : ℕ} (f : Fin n → ℝ) :
      ∑ x : Fin n, ∑ _y : Fin n, ∑ _z : Fin n, f x = ↑n ^ 2 * ∑ x : Fin n, f x
      theorem ThreeMajority.sum3_mul_right {n : ℕ} (E : Fin n → Fin n → ℝ) (f : Fin n → ℝ) :
      ∑ x : Fin n, ∑ y : Fin n, ∑ z : Fin n, E y z * f x = (∑ x : Fin n, f x) * ∑ y : Fin n, ∑ z : Fin n, E y z
      theorem ThreeMajority.sum_sq_colourCount {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (c : Fin n → σ) :
      ∑ b : σ, ↑(colourCount c b) ^ 2 = ∑ u : Fin n, ∑ v : Fin n, if c u = c v then 1 else 0

      The number of ordered pairs of agents of equal colour is ∑_b c_b².

      theorem ThreeMajority.card_majColour_eq {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (c : Fin n → σ) (a : σ) :
      ↑{s : Fin n × Fin n × Fin n | majColour c s = a}.card = ↑n * ↑(colourCount c a) ^ 2 + ↑n ^ 2 * ↑(colourCount c a) - ↑(colourCount c a) * ∑ b : σ, ↑(colourCount c b) ^ 2

      The number of sample triples whose 3-Majority colour is a.

      theorem ThreeMajority.independent_map_expect {ι : Type u_2} {α : Type u_3} {β : Type u_4} [Fintype ι] [DecidableEq ι] [Fintype α] [Fintype β] (p : ι → Dynamics.Distribution α) (g : α → β) (f : (ι → β) → ℝ) :
      (Dynamics.Distribution.independent fun (i : ι) => (p i).map g).expect f = (Dynamics.Distribution.independent p).expect fun (x : ι → α) => f fun (i : ι) => g (x i)

      Drawing every coordinate independently from (p i).map g is applying g coordinatewise to independent draws from the p i.

      theorem ThreeMajority.uniform_map_weight {σ : Type u_1} [Fintype σ] [DecidableEq σ] {β : Type u_2} [Fintype β] [Nonempty β] (g : β → σ) (a : σ) :
      ((Dynamics.Distribution.uniform β).map g).weight a = ↑{b : β | g b = a}.card / ↑(Fintype.card β)

      The weight of a pushed-forward uniform law is a normalized fibre count.

      theorem ThreeMajority.alphaVoter_weight {n : ℕ} [NeZero n] {σ : Type u_1} [Fintype σ] [DecidableEq σ] (c : Fin n → σ) (a : σ) :
      (alphaVoter c).weight a = ↑(colourCount c a) / ↑n

      Equation (1) (BCEKMN17): α^V_a(c) = c_a / n.

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

      Equation (2) (BCEKMN17): with x = c/n, α^{3M}_a(c) = x_a (1 + x_a − ‖x‖₂²).

      theorem ThreeMajority.apply_ofStep_stepCol {n : ℕ} [NeZero n] {σ : Type u_1} [Fintype σ] [DecidableEq σ] (f : (Fin n → σ) → ℝ) (c : Fin n → σ) :

      One uniformly random round of stepCol is one step of the AC-process alpha3M (3-Majority is an AC-process, BCEKMN17, Section 2.2).

      theorem ThreeMajority.apply_ofStep_voterStep {n : ℕ} [NeZero n] {σ : Type u_1} [Fintype σ] (f : (Fin n → σ) → ℝ) (c : Fin n → σ) :

      One uniformly random round of voterStep is one step of the AC-process alphaVoter (Voter is an AC-process, BCEKMN17, Section 2.2).

      theorem ThreeMajority.exists_top_set {ι : Type u_2} [Finite ι] (x : ι → ℝ) (S₁ : Finset ι) :
      ∃ (S₂ : Finset ι), S₂.card = S₁.card ∧ ∑ i ∈ S₁, x i ≤ ∑ i ∈ S₂, x i ∧ ∀ i ∈ S₂, ∀ j ∉ S₂, x j ≤ x i

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

      theorem ThreeMajority.sum_colourCount_div {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (c : Fin n → σ) (hn : ↑n ≠ 0) :
      ∑ b : σ, ↑(colourCount c b) / ↑n = 1

      The colour fractions of a configuration sum to one.

      theorem ThreeMajority.sq_norm_mul_sum_le {ι : Type u_2} [Fintype ι] (x : ι → ℝ) (hx0 : ∀ (i : ι), 0 ≤ x i) (hx1 : ∑ i : ι, x i = 1) (S : Finset ι) (htop : ∀ i ∈ S, ∀ j ∉ S, x j ≤ x i) :
      (∑ j : ι, x j ^ 2) * ∑ i ∈ S, x i ≤ ∑ i ∈ S, x i ^ 2

      The key inequality of Lemma 2: on a top set S of a probability vector x, ‖x‖₂² ∑_S x ≤ ∑_S x².

      theorem ThreeMajority.iterate_eq_of_apply_eq {α : Type u_2} [Fintype α] {K K' : Dynamics.Kernel α} (h : ∀ (f : α → ℝ) (a : α), K.apply f a = K'.apply f a) (T : ℕ) (f : α → ℝ) :
      K.iterate T f = K'.iterate T f

      Two kernels with the same one-step operator have the same iterates.

      The inequality of the proof of Lemma 2 (BCEKMN17): 3-Majority dominates Voter, c ⪰ c' implies α^{3M}(c) ⪰ α^V(c').

      theorem ThreeMajority.voter_le_threeMaj {n : ℕ} [NeZero n] {σ : Type u_1} [DecidableEq σ] [Finite σ] (c : Fin n → σ) (κ T : ℕ) :
      (expList (Fin n → Fin n) T fun (l : List (Fin n → Fin n)) => if numColours (voterRun c l) ≤ κ then 1 else 0) ≤ expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ κ then 1 else 0

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