Growth of the bias in one round (Lemmas 3.3, 3.4, 3.5) #
Fix a coloring x with a unique plurality color m, and write c = count x,
s = s(c), α = α(c), γ = γ(c).
- Lemma 3.3 (
lemma_3_3): for every other colorj, the gapC_{m,t+1} - C_{j,t+1}exceedss (1 + γ + c_m α / (2s))except with probabilityexp(-c_m α²/25). Its expectation is at leasts(1 + γ) + c_m α(from Lemmas 3.1 and 3.2), and Bernstein's inequality (Dynamics.avg_bernstein, withb = 2and variance at most3 c_m) bounds the lower deviation byc_m α / 2. - Lemma 3.4 (
lemma_3_4):C_{m,t+1} > c_m (1 + γ + α/2)except with probabilityexp(-c_m α²/11), by the multiplicative Chernoff bound (Dynamics.avg_chernoff_lower_mul). - Lemma 3.5 (
lemma_3_5): ifλ n ≤ c_m ≤ (2/3) nands ≥ 22 √((1/λ) n log n), the bias grows by a factor1 + λ/6against each color, and the plurality grows, except with probability1/n²each.
theorem
Plurality.lemma_3_5
{n k : ℕ}
(hn : 1 ≤ n)
(x : Config n k)
{m : Fin k}
(hM : argmaxSet (count x) = {m})
{lam : ℝ}
(hlam0 : 0 < lam)
(hlam1 : lam ≤ 2 / 3)
(hcm0 : lam * ↑n ≤ ↑(count x m))
(hcm1 : ↑(count x m) ≤ 2 / 3 * ↑n)
(hs : 22 * √(1 / lam * ↑n * Real.log ↑n) ≤ ↑(bias (count x)))
:
(∀ (j : Fin k),
j ≠ m →
(Dynamics.avg fun (r : ThreeMajority.Tgt3 n) =>
if ↑(count (step x r) m) - ↑(count (step x r) j) ≤ ↑(bias (count x)) * (1 + lam / 6) then 1 else 0) ≤ 1 / ↑n ^ 2) ∧ (Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑(count (step x r) m) ≤ ↑(count x m) then 1 else 0) ≤ 1 / ↑n ^ 2
Lemma 3.5 (large plurality and large bias). If M(c) = {m},
0 < λ ≤ 2/3, λ n ≤ c_m ≤ (2/3) n and s(c) ≥ 22 √((1/λ) n log n), then for
every other color j, P(C_{m,t+1} - C_{j,t+1} ≤ s(c)(1 + λ/6)) ≤ 1/n², and
P(C_{m,t+1} ≤ c_m) ≤ 1/n².