Documentation

Plurality.Saturation

The saturation phase (Lemmas 3.6 and 3.7) #

Once the bias is at least n/3, the number C̄ₘ = n - Cₘ of nodes that do not support the plurality color m decreases geometrically.

The paper omits the proof of Lemma 3.7; the one here uses Lemma 3.6 with the bounds s cₘ ≥ n²/9 (first regime) and s ≥ n - 2(n - cₘ) (second regime), the closed-form Chernoff upper tail Dynamics.avg_chernoff_upper_log, and Markov's inequality Dynamics.avg_markov_one. "Sufficiently large n" is made explicit as log n ≥ 40.

def Plurality.notAdopt {n k : ℕ} (x : Config n k) (m : Fin k) :
Fin n → (t : Fin n × Fin n × Fin n) → ℝ

The per-node indicator of not adopting m.

Equations
Instances For
    theorem Plurality.notAdopt_zero_one {n k : ℕ} (x : Config n k) (m : Fin k) (v : Fin n) (t : Fin n × Fin n × Fin n) :
    notAdopt x m v t = 0 ∨ notAdopt x m v t = 1
    theorem Plurality.sum_notAdopt {n k : ℕ} (x : Config n k) (m : Fin k) (r : ThreeMajority.Tgt3 n) :
    ∑ v : Fin n, notAdopt x m v (r v) = ↑n - ↑(count (step x r) m)
    theorem Plurality.sum_avg_notAdopt {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) (m : Fin k) :
    ∑ v : Fin n, Dynamics.avg (notAdopt x m v) = ↑n - mu n (count x) m
    theorem Plurality.avg_count_compl {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) (m : Fin k) :
    (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => ↑n - ↑(count (step x r) m)) = ↑n - mu n (count x) m

    The expected number of nodes not supporting m after one round.

    theorem Plurality.lemma_3_6 {n k : ℕ} (hn : 1 ≤ n) (x : Config n k) {m : Fin k} (hm : m ∈ argmaxSet (count x)) :
    ((↑n - ↑(count x m)) * (1 - ↑(count x m) ^ 2 / ↑n ^ 2) ≤ Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => ↑n - ↑(count (step x r) m)) ∧ (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => ↑n - ↑(count (step x r) m)) ≤ (↑n - ↑(count x m)) * (1 - ↑(bias (count x)) * ↑(count x m) / ↑n ^ 2)

    Lemma 3.6. For every plurality color m, (n - cₘ)(1 - cₘ²/n²) ≤ μ̄ₘ(c) ≤ (n - cₘ)(1 - s(c) cₘ/n²), where μ̄ₘ(c) = 𝔼[C̄_{m,t+1} | Cₜ = c].

    theorem Plurality.bias_ge_of_singleton {n k : ℕ} (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) :
    ↑(count x m) - (↑n - ↑(count x m)) ≤ ↑(bias (count x))

    Every color other than m has at most n - cₘ nodes, so the bias is at least cₘ - (n - cₘ).

    theorem Plurality.lemma_3_7_i {n k : ℕ} (hL : 40 ≤ Real.log ↑n) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) (hs : ↑n / 3 ≤ ↑(bias (count x))) (hu : ↑n ^ (1 / 4) * Real.log ↑n ≤ ↑n - ↑(count x m)) :
    (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if 17 / 18 * (↑n - ↑(count x m)) ≤ ↑n - ↑(count (step x r) m) then 1 else 0) ≤ 1 / ↑n ^ 2

    Lemma 3.7, first regime. If M(c) = {m}, s(c) ≥ n/3 and n - cₘ ≥ n^{1/4} log n, then P(C̄_{m,t+1} ≥ (17/18)(n - cₘ)) ≤ 1/n².

    theorem Plurality.lemma_3_7_ii {n k : ℕ} (hL : 40 ≤ Real.log ↑n) (x : Config n k) {m : Fin k} (hM : argmaxSet (count x) = {m}) (hu : ↑n - ↑(count x m) < ↑n ^ (1 / 4) * Real.log ↑n) :
    (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if 0 < ↑n - ↑(count (step x r) m) then 1 else 0) ≤ ↑n ^ (-(1 / 5)) ∧ (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑n ^ (1 / 4) * Real.log ↑n ≤ ↑n - ↑(count (step x r) m) then 1 else 0) ≤ 1 / ↑n ^ 2

    Lemma 3.7, second regime. If M(c) = {m}, s(c) ≥ n/3 and n - cₘ < n^{1/4} log n, then P(C̄_{m,t+1} > 0) ≤ n^{-1/5} and P(C̄_{m,t+1} ≥ n^{1/4} log n) ≤ 1/n².