Documentation

Plurality.HPlurality

The lower bound for h-plurality (Section 4.3) #

In the h-plurality dynamics every node samples h nodes uniformly at random (with repetition, possibly itself) and adopts the most frequent color among them, breaking ties uniformly at random.

Tie-breaking. Each node also draws a uniform ordering σ of its h sample positions, and adopts the color of the tied position of smallest σ-rank (hplur). All tied colors appear equally often, so this picks each tied color with the same probability, as the paper requires.

The paper states Lemma 4.11 with the factor 1 + h²/k but proves 1 + 2h²/k, which is also what Theorem 4.12 uses.

Two finite-probability facts #

theorem Plurality.avg_prod_iter {β : Type u_1} {δ : Type u_2} [Fintype β] [Fintype δ] (F : β → δ → ℝ) :
(Dynamics.avg fun (p : β × δ) => F p.1 p.2) = Dynamics.avg fun (d : δ) => Dynamics.avg fun (b : β) => F b d

Fubini for uniform averages over a product.

theorem Plurality.avg_eval_two {γ : Type u_1} [Fintype γ] [Nonempty γ] (m : ℕ) {i i' : Fin m} (hii : i ≠ i') (G H : γ → ℝ) :
(Dynamics.avg fun (x : Fin m → γ) => G (x i) * H (x i')) = Dynamics.avg G * Dynamics.avg H

Two distinct coordinates are independent.

The model #

@[reducible, inline]
abbrev Plurality.HSample (n h : ℕ) :

The randomness of one node in one round: h samples and an ordering of the sample positions used to break ties.

Equations
Instances For
    @[reducible, inline]
    abbrev Plurality.HRound (n h : ℕ) :

    One round of h-plurality: the randomness of every node.

    Equations
    Instances For
      def Plurality.mult {k h : ℕ} (cs : Fin h → Fin k) (i : Fin h) :

      How often the color at position i appears among the sampled colors cs.

      Equations
      Instances For
        theorem Plurality.one_le_mult {k h : ℕ} (cs : Fin h → Fin k) (i : Fin h) :
        1 ≤ mult cs i
        theorem Plurality.exists_top {k h : ℕ} [NeZero h] (cs : Fin h → Fin k) :
        ∃ (i : Fin h), ∀ (i' : Fin h), mult cs i' ≤ mult cs i
        def Plurality.topRanks {k h : ℕ} (cs : Fin h → Fin k) (σ : Equiv.Perm (Fin h)) :

        The ranks of the positions whose color is most frequent.

        Equations
        Instances For
          theorem Plurality.topRanks_nonempty {k h : ℕ} [NeZero h] (cs : Fin h → Fin k) (σ : Equiv.Perm (Fin h)) :
          def Plurality.winnerPos {k h : ℕ} [NeZero h] (cs : Fin h → Fin k) (σ : Equiv.Perm (Fin h)) :
          Fin h

          The winning position: among the positions with a most frequent color, the one ranked first by σ.

          Equations
          Instances For
            def Plurality.hplur {k h : ℕ} [NeZero h] (cs : Fin h → Fin k) (σ : Equiv.Perm (Fin h)) :
            Fin k

            The plurality color of the sampled colors cs, ties broken by σ.

            Equations
            Instances For
              def Plurality.hstep {n k h : ℕ} [NeZero h] (x : Config n k) (R : HRound n h) :
              Config n k

              One round of h-plurality.

              Equations
              Instances For
                def Plurality.hrun {n k h : ℕ} [NeZero h] (x : Config n k) (l : List (HRound n h)) :
                Config n k

                The coloring after a list of rounds of h-plurality.

                Equations
                Instances For
                  theorem Plurality.winnerPos_top {k h : ℕ} [NeZero h] (cs : Fin h → Fin k) (σ : Equiv.Perm (Fin h)) (i' : Fin h) :
                  mult cs i' ≤ mult cs (winnerPos cs σ)
                  theorem Plurality.hplur_first {k h : ℕ} [NeZero h] {cs : Fin h → Fin k} {σ : Equiv.Perm (Fin h)} {j : Fin k} (hj : hplur cs σ = j) (h1 : {i : Fin h | cs i = j}.card = 1) :
                  cs ((Equiv.symm σ) 0) = j

                  Seen exactly once. If j appears at exactly one sample position and wins, then all sampled colors are distinct and j is at the position ranked first.

                  One node #

                  def Plurality.hadopt {n k h : ℕ} [NeZero h] (x : Config n k) (j : Fin k) (t : HSample n h) :

                  The indicator that a node with randomness t adopts j.

                  Equations
                  Instances For
                    theorem Plurality.hadopt_zero_one {n k h : ℕ} [NeZero h] (x : Config n k) (j : Fin k) (t : HSample n h) :
                    hadopt x j t = 0 ∨ hadopt x j t = 1
                    theorem Plurality.count_hstep_eq_sum {n k h : ℕ} [NeZero h] (x : Config n k) (R : HRound n h) (j : Fin k) :
                    ↑(count (hstep x R) j) = ∑ v : Fin n, hadopt x j (R v)
                    def Plurality.seen {n k h : ℕ} (x : Config n k) (j : Fin k) (s : Fin h → Fin n) :

                    The number of sample positions showing color j.

                    Equations
                    Instances For
                      theorem Plurality.seen_mul_pred {n k h : ℕ} (x : Config n k) (j : Fin k) (s : Fin h → Fin n) :
                      ↑(seen x j s) * (↑(seen x j s) - 1) = ∑ i : Fin h, ∑ i' ∈ Finset.univ.erase i, (if x (s i) = j then 1 else 0) * if x (s i') = j then 1 else 0

                      N(N-1) = ∑_{i ≠ i'} 𝟙ᵢ 𝟙ᵢ' for the number N of positions showing j.

                      theorem Plurality.avg_hadopt_le {n k h : ℕ} [NeZero h] (hn : 1 ≤ n) (x : Config n k) (j : Fin k) :
                      Dynamics.avg (hadopt x j) ≤ frac x j + ↑h ^ 2 / 2 * frac x j ^ 2

                      Adoption probability (proof of Lemma 4.11): a node adopts j with probability at most x_j + (h²/2) x_j², where x_j = c_j/n.

                      Lemma 4.11 #

                      theorem Plurality.lemma_4_11 {n k h : ℕ} [NeZero h] (hn : 1 ≤ n) (hk : 1 ≤ k) (x : Config n k) (j : Fin k) {a : ℝ} (hx : ↑(count x j) ≤ a) (ha : a ≤ 2 * ↑n / ↑k) :
                      (Dynamics.avg fun (R : HRound n h) => if a * (1 + 2 * ↑h ^ 2 / ↑k) ≤ ↑(count (hstep x R) j) then 1 else 0) ≤ Real.exp (-(2 * (a * ↑h ^ 2 / ↑k) ^ 2 / ↑n))

                      Lemma 4.11 (growth rate under h-plurality). If color j has at most a ≤ 2n/k nodes, then after one round it has at least a (1 + 2h²/k) nodes with probability at most exp(-2 (a h²/k)² / n).

                      theorem Plurality.exp_bound_le {n k h : ℕ} (hn : 1 ≤ n) (hk : 1 ≤ k) {a : ℝ} (ha : ↑n / ↑k ≤ a) :
                      Real.exp (-(2 * (a * ↑h ^ 2 / ↑k) ^ 2 / ↑n)) ≤ Real.exp (-(2 * ↑n * ↑h ^ 4 / ↑k ^ 4))

                      For a ≥ n/k, the bound of Lemma 4.11 is at most exp(-2 n h⁴ / k⁴).

                      theorem Plurality.lemma_4_11_paper {n k h : ℕ} [NeZero h] (hn : 1 ≤ n) (hk : 1 ≤ k) (x : Config n k) (j : Fin k) (h1 : ↑n / ↑k ≤ ↑(count x j)) (h2 : ↑(count x j) ≤ 2 * ↑n / ↑k) :
                      (Dynamics.avg fun (R : HRound n h) => if ↑(count x j) * (1 + 2 * ↑h ^ 2 / ↑k) ≤ ↑(count (hstep x R) j) then 1 else 0) ≤ Real.exp (-(2 * ↑n * ↑h ^ 4 / ↑k ^ 4))

                      Lemma 4.11, as stated in the paper (with the factor 1 + 2h²/k that its proof gives): if n/k ≤ c_j ≤ 2n/k, then P(C_{j,t+1} ≥ (1 + 2h²/k) c_j) ≤ exp(-2 n h⁴/k⁴).

                      Theorem 4.12 #

                      def Plurality.hBalancedSet (n : ℕ) {k : ℕ} (h : ℕ) (j : Fin k) (t : ℕ) :
                      Set (Config n k)

                      The threshold of round t: (3/2)(n/k)(1 + 2h²/k)^t.

                      Equations
                      Instances For
                        theorem Plurality.theorem_4_12 {n k h : ℕ} [NeZero h] (hn : 1 ≤ n) (hk : 3 ≤ k) (x : Config n k) (hx : ∀ (j : Fin k), ↑(count x j) ≤ 3 / 2 * (↑n / ↑k)) {T : ℕ} (hT : 3 / 2 * (1 + 2 * ↑h ^ 2 / ↑k) ^ T ≤ 2) :
                        (Dynamics.expList (HRound n h) T fun (l : List (HRound n h)) => if Monochromatic (hrun x l) then 1 else 0) ≤ ↑k * ↑T * Real.exp (-(2 * ↑n * ↑h ^ 4 / ↑k ^ 4))

                        Theorem 4.12 (lower bound for h-plurality). Let k ≥ 3. If every color starts with at most (3/2)(n/k) nodes and (3/2)(1 + 2h²/k)^T ≤ 2, then the coloring after T rounds of h-plurality is monochromatic with probability at most k T exp(-2 n h⁴/k⁴).

                        theorem Plurality.theorem_4_12_log {n k h : ℕ} [NeZero h] (hn : 1 ≤ n) (hk : 3 ≤ k) (x : Config n k) (hx : ∀ (j : Fin k), ↑(count x j) ≤ 3 / 2 * (↑n / ↑k)) {T : ℕ} (hT : ↑T ≤ ↑k / (2 * ↑h ^ 2) * Real.log (4 / 3)) :
                        (Dynamics.expList (HRound n h) T fun (l : List (HRound n h)) => if Monochromatic (hrun x l) then 1 else 0) ≤ ↑k * ↑T * Real.exp (-(2 * ↑n * ↑h ^ 4 / ↑k ^ 4))

                        Theorem 4.12, logarithmic form. Under the hypotheses of theorem_4_12, the coloring is still not monochromatic after T ≤ (k/(2h²)) log (4/3) rounds, i.e. Ω(k/h²) rounds, except with probability k T exp(-2 n h⁴/k⁴).