Documentation

ThreeMajority.OneRound

One-round exact drift #

The cubic majority map p(x) = 3x² - 2x³: the exact probability that a single agent adopts opinion 1 in one round, as a function of the current fraction x of opinion-1 agents. avg_card_step computes the exact expected size of step I r as n * p(|I|/n), via the algebraic identity maj(a,b,c) = ab+bc+ac-2abc for a,b,c ∈ {0,1} (the majority-of-three function, as a polynomial) plus the independence toolkit of Prob.lean.

Y_maj and card_step_eq_sum expose the underlying {0,1}-valued, per-agent decomposition of (step I r).card as ∑ v, Y_maj I v (r v), which is exactly the shape the Chernoff bounds of Dynamics.Chernoff need; Growth.lean and Saturation.lean apply them directly to Y_maj.

def ThreeMajority.ind {n : ℕ} (I : Finset (Fin n)) (x : Fin n) :

The real-valued membership indicator.

Equations
Instances For
    theorem ThreeMajority.avg_ind {n : ℕ} (I : Finset (Fin n)) :
    avg (ind I) = ↑I.card / ↑(Fintype.card (Fin n))
    theorem ThreeMajority.avg_ind_eq {n : ℕ} (I : Finset (Fin n)) :
    avg (ind I) = ↑I.card / ↑n

    avg (ind I) = |I|/n, phrased so downstream files can talk about the opinion-1 fraction directly.

    theorem ThreeMajority.majorityIndicator_eq {n : ℕ} (I : Finset (Fin n)) (s : Fin n × Fin n × Fin n) :
    (if 2 ≤ sampleCountOf I s then 1 else 0) = ind I s.1 * ind I s.2.1 + ind I s.2.1 * ind I s.2.2 + ind I s.1 * ind I s.2.2 - 2 * (ind I s.1 * ind I s.2.1 * ind I s.2.2)

    Majority-of-three as a polynomial: for a, b, c ∈ {0,1}, 𝟙[a+b+c ≥ 2] = ab+bc+ac-2abc.

    theorem ThreeMajority.avg_ind_mul_fst_snd1 {n : ℕ} (I : Finset (Fin n)) [Nonempty (Fin n)] :
    (avg fun (s : Fin n × Fin n × Fin n) => ind I s.1 * ind I s.2.1) = avg (ind I) * avg (ind I)
    theorem ThreeMajority.avg_ind_mul_snd1_snd2 {n : ℕ} (I : Finset (Fin n)) [Nonempty (Fin n)] :
    (avg fun (s : Fin n × Fin n × Fin n) => ind I s.2.1 * ind I s.2.2) = avg (ind I) * avg (ind I)
    theorem ThreeMajority.avg_ind_mul_fst_snd2 {n : ℕ} (I : Finset (Fin n)) [Nonempty (Fin n)] :
    (avg fun (s : Fin n × Fin n × Fin n) => ind I s.1 * ind I s.2.2) = avg (ind I) * avg (ind I)
    theorem ThreeMajority.avg_ind_mul_triple {n : ℕ} (I : Finset (Fin n)) [Nonempty (Fin n)] :
    (avg fun (s : Fin n × Fin n × Fin n) => ind I s.1 * ind I s.2.1 * ind I s.2.2) = avg (ind I) * avg (ind I) * avg (ind I)
    def ThreeMajority.Y_maj {n : ℕ} (I : Finset (Fin n)) :
    Fin n → (s : Fin n × Fin n × Fin n) → ℝ

    The per-agent {0,1} contribution: whether a majority of the sample triple s lies in I. Independent of the agent index v; kept as a function Fin n → (Fin n × Fin n × Fin n) → ℝ to match the shape the Chernoff bounds of Dynamics.Chernoff expect.

    Equations
    Instances For
      theorem ThreeMajority.Y_maj_zero_one {n : ℕ} (I : Finset (Fin n)) (v : Fin n) (s : Fin n × Fin n × Fin n) :
      Y_maj I v s = 0 ∨ Y_maj I v s = 1
      theorem ThreeMajority.card_step_eq_sum {n : ℕ} (I : Finset (Fin n)) (r : Tgt3 n) :
      ↑(step I r).card = ∑ v : Fin n, Y_maj I v (r v)

      (step I r).card decomposes as the sum, over agents v, of the per-agent {0,1} contributions Y_maj I v (r v).

      theorem ThreeMajority.avg_Y_maj_eq {n : ℕ} (I : Finset (Fin n)) [Nonempty (Fin n)] (v : Fin n) :
      avg (Y_maj I v) = avg (ind I) * avg (ind I) * 3 - 2 * (avg (ind I) * avg (ind I) * avg (ind I))
      theorem ThreeMajority.sum_avg_Y_maj {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) :
      ∑ v : Fin n, avg (Y_maj I v) = ↑n * (3 * avg (ind I) ^ 2 - 2 * avg (ind I) ^ 3)

      The sum, over all n agents, of the average per-agent contribution: n · p(x), p(x) = 3x² - 2x³, x = |I|/n.

      theorem ThreeMajority.avg_card_step {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) :
      (avg fun (r : Tgt3 n) => ↑(step I r).card) = ↑n * (3 * avg (ind I) ^ 2 - 2 * avg (ind I) ^ 3)

      Exact one-round drift: the average number of agents adopting opinion 1 after one round equals n · p(x), p(x) = 3x²-2x³, x = |I|/n.

      def ThreeMajority.Y_dis {n : ℕ} (I : Finset (Fin n)) (v : Fin n) (s : Fin n × Fin n × Fin n) :

      The complementary per-agent {0,1} contribution: whether agent v adopts opinion 0 (dissents), i.e. 1 - Y_maj.

      Equations
      Instances For
        theorem ThreeMajority.Y_dis_zero_one {n : ℕ} (I : Finset (Fin n)) (v : Fin n) (s : Fin n × Fin n × Fin n) :
        Y_dis I v s = 0 ∨ Y_dis I v s = 1
        theorem ThreeMajority.card_dissent_eq_sum {n : ℕ} (I : Finset (Fin n)) (r : Tgt3 n) :
        ↑n - ↑(step I r).card = ∑ v : Fin n, Y_dis I v (r v)

        n - (step I r).card decomposes as the sum, over agents v, of the per-agent dissent contributions Y_dis I v (r v).

        theorem ThreeMajority.sum_avg_Y_dis {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) :
        ∑ v : Fin n, avg (Y_dis I v) = ↑n - ↑n * (3 * avg (ind I) ^ 2 - 2 * avg (ind I) ^ 3)