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.
The fraction x_j = c_j / n of nodes of color j.
Equations
- Plurality.frac x j = โ(Plurality.count x j) / โn
Instances For
The expected new count of color j under rule f is n times the adoption
probability.
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ยฒ).