Documentation

Plurality.Upper

The general upper bound (Theorem 3.8) #

If m is the unique plurality color, c_m ≥ n/λ for some λ ≥ 3 and the bias is at least Λ = 22 √(λ n log n), then 3-majority reaches consensus on m within O(λ log n) rounds with high probability.

The proof runs the chain through nested phases and applies Dynamics.Kernel.nested_phases (the paper's Lemma A.4) to kernel maj3.

Differences from the paper #

The phases #

def Plurality.growthSet (n : ℕ) {k : ℕ} (m : Fin k) (lam Λ : ℝ) (i : ℕ) :
Set (Config n k)

Growth phase i: c_m > 2n/3, or m is the unique plurality color with at least n/λ nodes and bias at least Λ (1 + 1/(6λ))^i.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    def Plurality.satSet (n : ℕ) {k : ℕ} (m : Fin k) (j : ℕ) :
    Set (Config n k)

    Saturation phase j: fewer than max ((n/3)(17/18)^j) (n^{1/4} log n) nodes disagree with m.

    Equations
    Instances For
      def Plurality.monoSet (n : ℕ) {k : ℕ} (m : Fin k) :
      Set (Config n k)

      Consensus on m.

      Equations
      Instances For

        Bookkeeping for one round #

        Counting facts #

        theorem Plurality.count_add_count_le {n k : ℕ} (x : Config n k) {j m : Fin k} (hj : j ≠ m) :
        count x j + count x m ≤ n
        theorem Plurality.count_step_eq_zero {n k : ℕ} (x : Config n k) {j : Fin k} (hj : count x j = 0) (r : ThreeMajority.Tgt3 n) :
        count (step x r) j = 0

        A color without nodes stays without nodes.

        theorem Plurality.argmaxSet_eq_of_lt {k : ℕ} {c : Fin k → ℕ} {m : Fin k} (h : ∀ (j : Fin k), j ≠ m → c j < c m) :
        theorem Plurality.le_bias_of_gap {k : ℕ} {c : Fin k → ℕ} {m : Fin k} {g : ℝ} (hg : 0 < g) (hgm : g ≤ ↑(c m)) (h : ∀ (j : Fin k), j ≠ m → ↑(c j) + g ≤ ↑(c m)) :
        argmaxSet c = {m} ∧ g ≤ ↑(bias c)

        If m leads every other color by at least g > 0 (and has at least g nodes), then m is the unique plurality color and the bias is at least g.

        theorem Plurality.of_dissent_lt {n k : ℕ} (x : Config n k) {m : Fin k} (hu : ↑n - ↑(count x m) < ↑n / 3) :
        argmaxSet (count x) = {m} ∧ ↑n / 3 ≤ ↑(bias (count x))

        If fewer than a third of the nodes disagree with m, then m is the unique plurality color and the bias is at least n/3.

        theorem Plurality.quarter_log_le_third {n : ℕ} (hL : 40 ≤ Real.log ↑n) :
        ↑n ^ (1 / 4) * Real.log ↑n ≤ ↑n / 3

        n^{1/4} log n ≤ n/3 for log n ≥ 40.

        Saturation phases #

        theorem Plurality.satSet_sub {n k : ℕ} (hL : 40 ≤ Real.log ↑n) (m : Fin k) (j : ℕ) :
        satSet n m j ⊆ {x : Config n k | ↑n - ↑(count x m) < ↑n / 3}
        theorem Plurality.satSet_succ_sub {n k : ℕ} (m : Fin k) (j : ℕ) :
        satSet n m (j + 1) ⊆ satSet n m j
        theorem Plurality.sat_step {n k : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (m : Fin k) (j : ℕ) {x : Config n k} (hx : x ∈ satSet n m j) :
        1 - 1 / ↑n ^ 2 ≤ (kernel maj3 x).prob fun (x : Config n k) => x ∈ satSet n m (j + 1)

        One saturation round. From satSet j, the chain is in satSet (j+1) after one round except with probability 1/n² (Lemma 3.7).

        theorem Plurality.mono_step {n k : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (m : Fin k) {x : Config n k} (hx : ↑n - ↑(count x m) < ↑n ^ (1 / 4) * Real.log ↑n) :
        1 - ↑n ^ (-(1 / 5)) ≤ (kernel maj3 x).prob fun (x : Config n k) => x ∈ monoSet n m

        The last round. Below n^{1/4} log n dissenters, one round reaches consensus except with probability n^{-1/5} (Lemma 3.7).

        theorem Plurality.mono_stay {n k : ℕ} [NeZero n] (m : Fin k) {x : Config n k} (hx : x ∈ monoSet n m) :
        1 ≤ (kernel maj3 x).prob fun (x : Config n k) => x ∈ monoSet n m

        Growth phases #

        theorem Plurality.growthSet_succ_sub {n k : ℕ} (m : Fin k) {lam Λ : ℝ} (hlam : 0 < lam) (hΛ : 0 ≤ Λ) (i : ℕ) :
        growthSet n m lam Λ (i + 1) ⊆ growthSet n m lam Λ i
        theorem Plurality.growthSet_sub_of_lt {n k : ℕ} (m : Fin k) {lam Λ : ℝ} {i : ℕ} (hi : ↑n < Λ * (1 + 1 / lam / 6) ^ i) :
        growthSet n m lam Λ i ⊆ satSet n m 0

        Once the target bias exceeds n, only the alternative c_m > 2n/3 is left.

        theorem Plurality.satSet_zero_sub {n k : ℕ} (m : Fin k) (lam Λ : ℝ) (i : ℕ) (hL : 40 ≤ Real.log ↑n) :
        satSet n m 0 ⊆ growthSet n m lam Λ i
        theorem Plurality.growth_step {n k : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (hk : 2 ≤ k) (m : Fin k) {lam Λ : ℝ} (hlam : 3 ≤ lam) (hΛ : 22 * √(lam * ↑n * Real.log ↑n) ≤ Λ) (i : ℕ) {x : Config n k} (hx : x ∈ growthSet n m lam Λ i) :
        1 - 1 / ↑n ≤ (kernel maj3 x).prob fun (x : Config n k) => x ∈ growthSet n m lam Λ (i + 1)

        One growth round (Lemma 3.5 and a union bound over the colors that have nodes). From growth phase i, the chain is in growth phase i + 1 after one round except with probability 1/n.

        Theorem 3.8 #

        noncomputable def Plurality.growthPhases (n : ℕ) (lam : ℝ) :

        The number T₁ of growth phases: enough for (1 + 1/(6λ))^{T₁} ≥ n.

        Equations
        Instances For
          noncomputable def Plurality.satPhases (n : ℕ) :

          The number T₂ of saturation phases: enough for (18/17)^{T₂ - 1} ≥ n.

          Equations
          Instances For
            noncomputable def Plurality.phases (n : ℕ) (lam : ℝ) :

            The total number of phases, T = T₁ + T₂ + 1; the process runs for 10 T rounds.

            Equations
            Instances For
              theorem Plurality.sub_one_div_le_log {q : ℝ} (hq : 0 < q) :
              (q - 1) / q ≤ Real.log q

              log q ≥ (q - 1)/q for q > 0.

              theorem Plurality.phases_le {n : ℕ} (hL : 40 ≤ Real.log ↑n) {lam : ℝ} (hlam : 3 ≤ lam) :
              ↑(phases n lam) ≤ 13 * lam * Real.log ↑n

              The number of phases is O(λ log n): T ≤ 13 λ log n.

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

              Theorem 3.8 (the general upper bound). Let λ ≥ 3, log n ≥ 40 and k ≥ 2. If m is the unique plurality color of x, c_m ≥ n/λ and s(c) ≥ 22 √(λ n log n), then after 10 T rounds, where T = phases n λ ≤ 13 λ log n (phases_le), every node supports m with probability at least 1 - 11 T / n.

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

              Theorem 3.8, O(λ log n) form. Under the hypotheses of theorem_3_8, consensus on m holds after 10 T ≤ 130 λ log n rounds with probability at least 1 - 143 λ log n / n.