Documentation

Plurality.Quantities

Plurality, bias, α and γ of a color distribution (Section 3) #

For a k-color distribution c : Fin k → ℕ with ∑ₕ cₕ = n the paper uses

Lemma 3.1 bounds these quantities and Lemma 3.2 rewrites μⱼ in terms of them. Everything here is elementary algebra about finite sums of naturals.

def Plurality.maxc {k : ℕ} (c : Fin k → ℕ) :

m(c): the plurality size.

Equations
Instances For
    def Plurality.argmaxSet {k : ℕ} (c : Fin k → ℕ) :

    M(c): the plurality colors.

    Equations
    Instances For
      def Plurality.secondc {k : ℕ} (c : Fin k → ℕ) :

      The largest count among the colors outside M(c) (0 if there is none).

      Equations
      Instances For
        def Plurality.bias {k : ℕ} (c : Fin k → ℕ) :

        s(c): the bias, i.e. the gap between the plurality color and every other color when the plurality color is unique, and 0 otherwise.

        Equations
        Instances For
          noncomputable def Plurality.alpha {k : ℕ} (n : ℕ) (c : Fin k → ℕ) :

          α(c) = (n - m(c)) s(c) / n².

          Equations
          Instances For
            noncomputable def Plurality.gamma {k : ℕ} (n : ℕ) (c : Fin k → ℕ) :

            γ(c) = (n m(c) - ∑ₕ cₕ²) / n² - α(c).

            Equations
            Instances For
              noncomputable def Plurality.mu {k : ℕ} (n : ℕ) (c : Fin k → ℕ) (j : Fin k) :

              μⱼ(c) = cⱼ (1 + (n cⱼ - ∑ₕ cₕ²)/n²), the expected next count of j.

              Equations
              Instances For

                Basic facts #

                theorem Plurality.le_maxc {k : ℕ} (c : Fin k → ℕ) (h : Fin k) :
                c h ≤ maxc c
                theorem Plurality.exists_eq_maxc {k : ℕ} (hk : 0 < k) (c : Fin k → ℕ) :
                ∃ (m : Fin k), c m = maxc c
                theorem Plurality.mem_argmaxSet {k : ℕ} {c : Fin k → ℕ} {j : Fin k} :
                j ∈ argmaxSet c ↔ c j = maxc c
                theorem Plurality.maxc_le_of_sum {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hc : ∑ h : Fin k, c h = n) :
                maxc c ≤ n
                theorem Plurality.secondc_le_maxc {k : ℕ} (c : Fin k → ℕ) :
                theorem Plurality.bias_le_maxc {k : ℕ} (c : Fin k → ℕ) :
                theorem Plurality.argmaxSet_eq_singleton {k : ℕ} {c : Fin k → ℕ} {m : Fin k} (hM : argmaxSet c = {m}) :
                c m = maxc c

                A unique plurality color m.

                theorem Plurality.bias_of_singleton {k : ℕ} {c : Fin k → ℕ} {m : Fin k} (hM : argmaxSet c = {m}) :
                theorem Plurality.add_bias_le {k : ℕ} {c : Fin k → ℕ} {m : Fin k} (hm : c m = maxc c) {h : Fin k} (hh : h ≠ m) :
                c h + bias c ≤ maxc c

                Every other color trails a plurality color by at least the bias.

                theorem Plurality.exists_add_bias_eq {k : ℕ} (hk : 2 ≤ k) {c : Fin k → ℕ} {m : Fin k} (hm : c m = maxc c) :
                ∃ (ℓ : Fin k), ℓ ≠ m ∧ c ℓ + bias c = maxc c

                The bias is attained: with at least two colors, some color other than a plurality color m has exactly m(c) - s(c) nodes.

                theorem Plurality.sum_mul_sub_eq {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hc : ∑ h : Fin k, c h = n) :
                ↑n * ↑(maxc c) - ∑ h : Fin k, ↑(c h) ^ 2 = ∑ h : Fin k, ↑(c h) * (↑(maxc c) - ↑(c h))

                n m - ∑ₕ cₕ² = ∑ₕ cₕ (m - cₕ) when the counts sum to n.

                theorem Plurality.gamma_mul_sq {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hc : ∑ h : Fin k, c h = n) (hn : 0 < n) {m : Fin k} (hm : c m = maxc c) :
                gamma n c * ↑n ^ 2 = ∑ h ∈ Finset.univ.erase m, ↑(c h) * (↑(maxc c) - ↑(bias c) - ↑(c h))

                The key identity: γ(c) n² = ∑_{h ≠ m} cₕ (m(c) - s(c) - cₕ).

                Lemma 3.1 #

                theorem Plurality.lemma_3_1_a {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hc : ∑ h : Fin k, c h = n) :
                0 ≤ ↑(bias c) ∧ ↑(bias c) ≤ ↑(maxc c) - (↑n - ↑(maxc c)) / (↑k - 1)

                Lemma 3.1 (a). 0 ≤ s(c) ≤ m(c) - (n - m(c))/(k - 1).

                theorem Plurality.lemma_3_1_b {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hc : ∑ h : Fin k, c h = n) :
                0 ≤ alpha n c ∧ alpha n c ≤ min (↑(bias c) / ↑n) (1 / 4)

                Lemma 3.1 (b). 0 ≤ α(c) ≤ min {s(c)/n, 1/4}.

                theorem Plurality.lemma_3_1_c {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hc : ∑ h : Fin k, c h = n) (hn : 0 < n) :
                0 ≤ gamma n c ∧ gamma n c ≤ 1 / 8

                Lemma 3.1 (c). 0 ≤ γ(c) ≤ 1/8.

                Lemma 3.2 #

                theorem Plurality.lemma_3_2_a {k : ℕ} {c : Fin k → ℕ} {n : ℕ} {m : Fin k} (hm : m ∈ argmaxSet c) :
                mu n c m = ↑(c m) * (1 + gamma n c + alpha n c)

                Lemma 3.2 (a). For a plurality color m, μₘ(c) = cₘ (1 + γ(c) + α(c)).

                theorem Plurality.lemma_3_2_b {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hn : 0 < n) (j : Fin k) :
                mu n c j = ↑(c j) * (1 + gamma n c + alpha n c - (↑(maxc c) - ↑(c j)) / ↑n)

                Lemma 3.2 (b). For every non-plurality color j, μⱼ(c) = cⱼ (1 + γ(c) + α(c) - (m(c) - cⱼ)/n).

                theorem Plurality.lemma_3_2_c {k : ℕ} {c : Fin k → ℕ} {n : ℕ} (hn : 0 < n) {m ℓ : Fin k} (hm : m ∈ argmaxSet c) (hℓm : ℓ ≠ m) (hℓ : c ℓ = (Finset.univ.erase m).sup c) :
                mu n c ℓ = ↑(c ℓ) * (1 + gamma n c + alpha n c - ↑(bias c) / ↑n)

                Lemma 3.2 (c). If m is a plurality color and ℓ has the most nodes among the other colors, μ_ℓ(c) = c_ℓ (1 + γ(c) + α(c) - s(c)/n).