Documentation

Plurality.ClearMajority

Theorem 4.8 (a): a solver must follow the clear majority #

Consider two colors r ≠ b and only these two colors present, with fractions x and y = 1 - x. Under a 3-input rule f, a node adopts r with probability x³ + Δ_r x² y + (3 - Δ_b) x y², where Δ_r = majCount f r b and Δ_b = majCount f b r. Hence

p(x) - x = x y (x (Δ_r - 2) + y (2 - Δ_b)).

If Δ_r ≤ 2 ≤ Δ_b this is ≤ 0 in every state, so the number of red nodes is a supermartingale, its expectation never exceeds its initial value, and from 5n/8 red nodes (bias n/4) the probability that all nodes are red at any time is at most 5/8 (not_solver_of_drift). No optional stopping is needed.

theorem_4_8_a: a (n/4, 1/4)-solver has, for every pair of colors, either Δ_r = Δ_b = 3 (it follows the clear majority on that pair) or Δ_r, Δ_b ≤ 1.

The remaining case. The paper's proof also claims the case Δ_r, Δ_b ≤ 1, but it only checks the supermartingale inequality when red is the majority. In this case p(x) - x > 0 when red is the minority: the process is pulled towards an interior point x* = (2 - Δ_b)/(4 - Δ_r - Δ_b), and which color eventually wins depends on how the process leaves that point, which is not addressed. That case is left open here.

theorem Plurality.majCount_le {k : ℕ} (f : Rule k) (r b : Fin k) :
majCount f r b ≤ 3
def Plurality.twoColor {k : ℕ} (n : ℕ) (r b : Fin k) (a : ℕ) :
Config n k

The coloring with the first a nodes colored r and the others b.

Equations
Instances For
    theorem Plurality.count_twoColor_left {n k : ℕ} {r b : Fin k} (hrb : r ≠ b) {a : ℕ} (ha : a ≤ n) :
    count (twoColor n r b a) r = a
    theorem Plurality.count_twoColor_right {n k : ℕ} {r b : Fin k} (hrb : r ≠ b) {a : ℕ} (ha : a ≤ n) :
    count (twoColor n r b a) b = n - a
    def Plurality.Supp2 {n k : ℕ} (r b : Fin k) (y : Config n k) :

    Every node supports r or b.

    Equations
    Instances For
      theorem Plurality.Supp2.stepWith {n k : ℕ} {f : Rule k} (hf : Conservative f) {r b : Fin k} {y : Config n k} (hy : Supp2 r b y) (t : ThreeMajority.Tgt3 n) :
      theorem Plurality.Supp2.count_eq_zero {n k : ℕ} {r b : Fin k} {y : Config n k} (hy : Supp2 r b y) {c : Fin k} (hr : c ≠ r) (hb : c ≠ b) :
      count y c = 0
      theorem Plurality.sum_eq_two {k : ℕ} {r b : Fin k} (hrb : r ≠ b) {F : Fin k → ℝ} (hF : ∀ (c : Fin k), c ≠ r → c ≠ b → F c = 0) :
      ∑ c : Fin k, F c = F r + F b
      theorem Plurality.ite_comp {k : ℕ} {f : Rule k} {r b u v w : Fin k} (hrb : r ≠ b) (h : f u v w = r ∨ f u v w = b) :
      (if f u v w = r then 1 else 0) = 1 - if f u v w = b then 1 else 0
      theorem Plurality.expected_red_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) {r b : Fin k} (hrb : r ≠ b) (hr : majCount f r b ≤ 2) (hb : 2 ≤ majCount f b r) {y : Config n k} (hy : Supp2 r b y) :
      (Dynamics.avg fun (t : ThreeMajority.Tgt3 n) => ↑(count (stepWith f y t) r)) ≤ ↑(count y r)

      The red drift. With only r and b present and Δ_r ≤ 2 ≤ Δ_b, the expected number of red nodes does not increase in one round.

      theorem Plurality.expected_red_le_iter {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) {r b : Fin k} (hrb : r ≠ b) (hr : majCount f r b ≤ 2) (hb : 2 ≤ majCount f b r) (T : ℕ) (y : Config n k) :
      Supp2 r b y → (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => ↑(count (runWith f y l) r)) ≤ ↑(count y r)

      The red count is a supermartingale: its expectation after T rounds is at most its initial value.

      theorem Plurality.not_solver_of_drift {n k : ℕ} (h8 : 8 ∣ n) (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) {r b : Fin k} (hrb : r ≠ b) (hr : majCount f r b ≤ 2) (hb : 2 ≤ majCount f b r) :
      ¬Solver f n (↑n / 4) (1 / 4)

      If Δ_r ≤ 2 ≤ Δ_b, the rule is not an (n/4, 1/4)-solver. From 5n/8 red and 3n/8 blue nodes, all nodes are red at time T with probability at most 5/8, for every T.

      theorem Plurality.theorem_4_8_a {n k : ℕ} (h8 : 8 ∣ n) (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) (hS : Solver f n (↑n / 4) (1 / 4)) {r b : Fin k} (hrb : r ≠ b) :
      majCount f r b = 3 ∧ majCount f b r = 3 ∨ majCount f r b ≤ 1 ∧ majCount f b r ≤ 1

      Theorem 4.8 (a), proved cases. If f is an (n/4, 1/4)-solver (with 8 ∣ n), then for every pair of distinct colors either f follows the clear majority on that pair (Δ_r = Δ_b = 3) or Δ_r, Δ_b ≤ 1. The paper claims that the second alternative is also impossible; see the module docstring.