Documentation

Plurality.Expectation

The next expected coloring (Lemma 2.1) #

A node recolors itself using three independent uniform samples, so the probability that it adopts color j under a rule f is a polynomial in the color fractions x_h = c_h / n: โˆ‘_{a,b,c} x_a x_b x_c ๐Ÿ™[f a b c = j] (avg_adopt). For 3-majority this is x_jยฒ + x_j (1 - โˆ‘_h x_hยฒ) (avg_adopt_maj3), and summing over the n independent nodes gives the paper's Lemma 2.1 (expected_count): ๐”ผ[C_{j,t+1} | C_t = c] = c_j (1 + (n c_j - โˆ‘_h c_hยฒ)/nยฒ).

The per-node {0,1} decomposition count_stepWith_eq_sum is the shape the concentration bounds (Chernoff, Hoeffding, Bernstein) consume.

noncomputable def Plurality.frac {n k : โ„•} (x : Config n k) (j : Fin k) :

The fraction x_j = c_j / n of nodes of color j.

Equations
Instances For
    theorem Plurality.frac_nonneg {n k : โ„•} (x : Config n k) (j : Fin k) :
    theorem Plurality.sum_frac {n k : โ„•} (hn : 1 โ‰ค n) (x : Config n k) :
    โˆ‘ j : Fin k, frac x j = 1
    theorem Plurality.avg_color_indicator {n k : โ„•} (x : Config n k) (j : Fin k) :
    (Dynamics.avg fun (v : Fin n) => if x v = j then 1 else 0) = frac x j

    The color fraction is the probability that a uniform sample has that color.

    def Plurality.adopt {n k : โ„•} (f : Fin k โ†’ Fin k โ†’ Fin k โ†’ Fin k) (x : Config n k) (j : Fin k) (s : Fin n ร— Fin n ร— Fin n) :

    The indicator that a node whose three samples are s adopts color j under rule f.

    Equations
    Instances For
      theorem Plurality.adopt_maj3_eq_adoptInd {n k : โ„•} (x : Config n k) (j : Fin k) (v : Fin n) (s : Fin n ร— Fin n ร— Fin n) :

      Under 3-majority, adopt is the adoption indicator ThreeMajority.adoptInd of 3-Majority with colours of any type, at colours Fin k (whose agent argument is not used).

      theorem Plurality.adopt_zero_one {n k : โ„•} (f : Fin k โ†’ Fin k โ†’ Fin k โ†’ Fin k) (x : Config n k) (j : Fin k) (s : Fin n ร— Fin n ร— Fin n) :
      adopt f x j s = 0 โˆจ adopt f x j s = 1
      theorem Plurality.count_stepWith_eq_sum {n k : โ„•} (f : Fin k โ†’ Fin k โ†’ Fin k โ†’ Fin k) (x : Config n k) (r : ThreeMajority.Tgt3 n) (j : Fin k) :
      โ†‘(count (stepWith f x r) j) = โˆ‘ v : Fin n, adopt f x j (r v)

      The new count of color j is a sum of independent per-node indicators.

      theorem Plurality.avg_color_triple {n k : โ„•} (x : Config n k) (g : Fin k โ†’ Fin k โ†’ Fin k โ†’ โ„) :
      (Dynamics.avg fun (s : Fin n ร— Fin n ร— Fin n) => g (x s.1) (x s.2.1) (x s.2.2)) = โˆ‘ a : Fin k, โˆ‘ b : Fin k, โˆ‘ c : Fin k, frac x a * frac x b * frac x c * g a b c

      Three independent samples. The average of a function of the three sampled colors is its expectation under three independent draws from the color fractions.

      theorem Plurality.avg_adopt {n k : โ„•} (f : Fin k โ†’ Fin k โ†’ Fin k โ†’ Fin k) (x : Config n k) (j : Fin k) :
      Dynamics.avg (adopt f x j) = โˆ‘ a : Fin k, โˆ‘ b : Fin k, โˆ‘ c : Fin k, frac x a * frac x b * frac x c * if f a b c = j then 1 else 0

      The probability that a node adopts color j under rule f.

      theorem Plurality.expected_count_stepWith {n k : โ„•} (hn : 1 โ‰ค n) (f : Fin k โ†’ Fin k โ†’ Fin k โ†’ Fin k) (x : Config n k) (j : Fin k) :
      (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => โ†‘(count (stepWith f x r) j)) = โ†‘n * Dynamics.avg (adopt f x j)

      The expected new count of color j under rule f is n times the adoption probability.

      theorem Plurality.sum_weight_ite {k : โ„•} {w : Fin k โ†’ โ„} (hw : โˆ‘ c : Fin k, w c = 1) (b : Fin k) (u v : โ„) :
      (โˆ‘ c : Fin k, w c * if b = c then u else v) = w b * u + (1 - w b) * v

      โˆ‘_c w_c ยท (if b = c then u else v) = w_b u + (1 - w_b) v for weights summing to 1.

      theorem Plurality.sum_triple_maj3 {k : โ„•} {w : Fin k โ†’ โ„} (hw : โˆ‘ c : Fin k, w c = 1) (j : Fin k) :
      (โˆ‘ a : Fin k, โˆ‘ b : Fin k, โˆ‘ c : Fin k, w a * w b * w c * if maj3 a b c = j then 1 else 0) = w j ^ 2 + w j * (1 - โˆ‘ h : Fin k, w h ^ 2)

      The 3-majority adoption polynomial. For weights w summing to one, โˆ‘_{a,b,c} w_a w_b w_c ๐Ÿ™[maj3 a b c = j] = w_jยฒ + w_j (1 - โˆ‘_h w_hยฒ).

      theorem Plurality.avg_adopt_maj3 {n k : โ„•} (hn : 1 โ‰ค n) (x : Config n k) (j : Fin k) :
      Dynamics.avg (adopt maj3 x j) = frac x j ^ 2 + frac x j * (1 - โˆ‘ h : Fin k, frac x h ^ 2)

      The probability that a node adopts color j under 3-majority is x_jยฒ + x_j (1 - โˆ‘_h x_hยฒ).

      theorem Plurality.expected_count {n k : โ„•} (hn : 1 โ‰ค n) (x : Config n k) (j : Fin k) :
      (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => โ†‘(count (step x r) j)) = โ†‘(count x j) * (1 + (โ†‘n * โ†‘(count x j) - โˆ‘ h : Fin k, โ†‘(count x h) ^ 2) / โ†‘n ^ 2)

      Lemma 2.1 (next expected coloring). For every coloring and every color j, ๐”ผ[C_{j,t+1} | C_t = c] = c_j (1 + (n c_j - โˆ‘_h c_hยฒ) / nยฒ).