Documentation

Plurality.Growth

Growth of the bias in one round (Lemmas 3.3, 3.4, 3.5) #

Fix a coloring x with a unique plurality color m, and write c = count x, s = s(c), α = α(c), γ = γ(c).

theorem Plurality.n_mul_avg_adopt {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) (j : Fin k) :
↑n * Dynamics.avg (adopt maj3 x j) = mu n (count x) j

n times the probability of adopting j is μⱼ(c).

theorem Plurality.avg_adopt_nonneg {n k : ℕ} (x : Config n k) (j : Fin k) :
theorem Plurality.avg_adopt_le_one {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) (j : Fin k) :
theorem Plurality.maxc_pos {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) :
1 ≤ maxc (count x)
theorem Plurality.bias_pos {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) :
1 ≤ bias (count x)

A unique plurality color has a positive bias.

structure Plurality.Setting {k : ℕ} (n : ℕ) (x : Config n k) (m : Fin k) :

The shorthand facts about c_m, s, α, γ used throughout.

Instances For
    theorem Plurality.Setting.cm_eq {n k : ℕ} {x : Config n k} {m : Fin k} (hS : Setting n x m) :
    count x m = maxc (count x)
    theorem Plurality.Setting.alpha_nonneg {n k : ℕ} {x : Config n k} {m : Fin k} (_hS : Setting n x m) :
    0 ≤ alpha n (count x)
    theorem Plurality.Setting.alpha_le_quarter {n k : ℕ} {x : Config n k} {m : Fin k} (_hS : Setting n x m) :
    alpha n (count x) ≤ 1 / 4
    theorem Plurality.Setting.alpha_le_bias {n k : ℕ} {x : Config n k} {m : Fin k} (_hS : Setting n x m) :
    alpha n (count x) ≤ ↑(bias (count x)) / ↑n
    theorem Plurality.Setting.gamma_nonneg {n k : ℕ} {x : Config n k} {m : Fin k} (hS : Setting n x m) :
    0 ≤ gamma n (count x)
    theorem Plurality.Setting.gamma_le {n k : ℕ} {x : Config n k} {m : Fin k} (hS : Setting n x m) :
    gamma n (count x) ≤ 1 / 8
    theorem Plurality.lemma_3_3 {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) {m j : Fin k} (hM : argmaxSet (count x) = {m}) (hj : j ≠ m) :
    (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑(count (step x r) m) - ↑(count (step x r) j) ≤ ↑(bias (count x)) * (1 + gamma n (count x) + ↑(count x m) * alpha n (count x) / (2 * ↑(bias (count x)))) then 1 else 0) ≤ Real.exp (-(↑(count x m) * alpha n (count x) ^ 2 / 25))

    Lemma 3.3 (increasing rate of the bias). If M(c) = {m} then for every other color j, P(C_{m,t+1} - C_{j,t+1} ≤ s(c)(1 + γ(c) + c_m α(c)/(2 s(c)))) ≤ exp(-c_m α(c)²/25).

    theorem Plurality.lemma_3_4 {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) :
    (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑(count (step x r) m) ≤ ↑(count x m) * (1 + gamma n (count x) + alpha n (count x) / 2) then 1 else 0) ≤ Real.exp (-(↑(count x m) * alpha n (count x) ^ 2 / 11))

    Lemma 3.4. If M(c) = {m} then P(C_{m,t+1} ≤ c_m (1 + γ(c) + α(c)/2)) ≤ exp(-c_m α(c)²/11).

    theorem Plurality.lemma_3_5 {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) {lam : ℝ} (hlam0 : 0 < lam) (hlam1 : lam ≤ 2 / 3) (hcm0 : lam * ↑n ≤ ↑(count x m)) (hcm1 : ↑(count x m) ≤ 2 / 3 * ↑n) (hs : 22 * √(1 / lam * ↑n * Real.log ↑n) ≤ ↑(bias (count x))) :
    (∀ (j : Fin k), j ≠ m → (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑(count (step x r) m) - ↑(count (step x r) j) ≤ ↑(bias (count x)) * (1 + lam / 6) then 1 else 0) ≤ 1 / ↑n ^ 2) ∧ (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑(count (step x r) m) ≤ ↑(count x m) then 1 else 0) ≤ 1 / ↑n ^ 2

    Lemma 3.5 (large plurality and large bias). If M(c) = {m}, 0 < λ ≤ 2/3, λ n ≤ c_m ≤ (2/3) n and s(c) ≥ 22 √((1/λ) n log n), then for every other color j, P(C_{m,t+1} - C_{j,t+1} ≤ s(c)(1 + λ/6)) ≤ 1/n², and P(C_{m,t+1} ≤ c_m) ≤ 1/n².