Documentation

Plurality.Corollaries

Corollaries 3.10, 3.11 and 3.12 #

Three choices of λ in Theorem 3.8 (theorem_3_8_bigO).

theorem Plurality.le_mul_maxc {n k : ℕ} (x : Config n k) :
n ≤ k * maxc (count x)

Pigeonhole: the plurality color has at least n/k nodes.

noncomputable def Plurality.lamK (n k : ℕ) :

The parameter λ = min {2k, (n / log n)^{1/3}} of Corollary 3.10.

Equations
Instances For
    theorem Plurality.corollary_3_10 {n k : ℕ} (hL : 40 ≤ Real.log ↑n) (hk : 2 ≤ k) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) (hs : 22 * √(lamK n k * ↑n * Real.log ↑n) ≤ ↑(bias (count x))) :
    ↑(10 * phases n (lamK n k)) ≤ 130 * lamK n k * Real.log ↑n ∧ 1 - 143 * lamK n k * Real.log ↑n / ↑n ≤ Dynamics.expList (ThreeMajority.Tgt3 n) (10 * phases n (lamK n k)) fun (l : List (ThreeMajority.Tgt3 n)) => if Mono (run x l) m then 1 else 0

    Corollary 3.10. Let log n ≥ 40 and k ≥ 2, and write λ = min {2k, (n / log n)^{1/3}}. If m is the unique plurality color and s(c) ≥ 22 √(λ n log n), then after at most 130 λ log n rounds all nodes support m with probability at least 1 - 143 λ log n / n.

    theorem Plurality.corollary_3_11 {n k : ℕ} (hL : 40 ≤ Real.log ↑n) (hk : 2 ≤ k) {ℓ : ℕ} (hℓ : 1 ≤ ℓ) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) (hcm : ↑n / Real.log ↑n ^ ℓ ≤ ↑(count x m)) (hs : 22 * √(↑n * Real.log ↑n ^ (ℓ + 1)) ≤ ↑(bias (count x))) :
    ↑(10 * phases n (Real.log ↑n ^ ℓ)) ≤ 130 * Real.log ↑n ^ (ℓ + 1) ∧ 1 - 143 * Real.log ↑n ^ (ℓ + 1) / ↑n ≤ Dynamics.expList (ThreeMajority.Tgt3 n) (10 * phases n (Real.log ↑n ^ ℓ)) fun (l : List (ThreeMajority.Tgt3 n)) => if Mono (run x l) m then 1 else 0

    Corollary 3.11. Let log n ≥ 40, k ≥ 2 and ℓ ≥ 1. If m is the unique plurality color, c_m ≥ n / log^ℓ n and s(c) ≥ 22 √(n log^{ℓ+1} n), then after at most 130 log^{ℓ+1} n rounds all nodes support m with probability at least 1 - 143 log^{ℓ+1} n / n.

    theorem Plurality.corollary_3_12 {n k : ℕ} (hL : 40 ≤ Real.log ↑n) (hk : 2 ≤ k) {β : ℝ} (hβ : 3 ≤ β) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) (hcm : ↑n / β ≤ ↑(count x m)) (hs : 22 * √(β * ↑n * Real.log ↑n) ≤ ↑(bias (count x))) :
    ↑(10 * phases n β) ≤ 130 * β * Real.log ↑n ∧ 1 - 143 * β * Real.log ↑n / ↑n ≤ Dynamics.expList (ThreeMajority.Tgt3 n) (10 * phases n β) fun (l : List (ThreeMajority.Tgt3 n)) => if Mono (run x l) m then 1 else 0

    Corollary 3.12. Let log n ≥ 40, k ≥ 2 and β ≥ 3. If m is the unique plurality color, c_m ≥ n/β and s(c) ≥ 22 √(β n log n), then after at most 130 β log n rounds all nodes support m with probability at least 1 - 143 β log n / n. For a constant β this is O(log n) rounds.

    Two opinions from a vanishing bias #

    theorem Plurality.majority3_vanishing_bias {n : ℕ} (hL : 40 ≤ Real.log ↑n) (I₀ : Finset (Fin n)) (hs : 22 * √(3 * ↑n * Real.log ↑n) ≤ ↑I₀.card - (↑n - ↑I₀.card)) :
    ↑(10 * phases n 3) ≤ 390 * Real.log ↑n ∧ 1 - 429 * Real.log ↑n / ↑n ≤ Dynamics.expList (ThreeMajority.Tgt3 n) (10 * phases n 3) fun (l : List (ThreeMajority.Tgt3 n)) => if ThreeMajority.run I₀ l = Finset.univ then 1 else 0

    3-Majority with two opinions from a vanishing bias (the k = 2, λ = 3 case of theorem_3_8_bigO, transferred to the binary process ThreeMajority.run through colorSet_run): if the nodes of I₀ outnumber the others by at least 22 √(3 n log n) (a fraction 1/2 + O(√(log n / n))) and log n ≥ 40, then after O(log n) rounds, at most 390 log n, every node holds the opinion of I₀ with probability at least 1 - 429 log n / n.