One-round tails of 3-Majority with many colours (roadmap MAJ-12 (a)) #
Tools for the one-round estimates of BCNPT16 (Becchetti, Clementi, Natale, Pasquale, Trevisan,
Stabilizing consensus with many opinions, SODA 2016, arXiv:1508.06782), Section 3 and
Appendix B, for the model stepCol of ThreeMajority.AnyStartModel.
- Deterministic facts on supports: dead colours stay dead (
colourCount_runCol_eq_zero); if every colour of a configuration withjcolours has more thann/j − magents, every colour has at mostn/j + (j − 1) m(colourCount_le_of_forall_lt), hence∑_b (c_b/n)² ≤ (n/j + (j − 1) m)/nand a lower bound on the expected support (le_avg_colourCount_stepCol); the upper bound of Lemma 2.1 at a levelb ≥ c_a(avg_colourCount_stepCol_le_of_le); the smallest ofjsupports adding up tonis at mostn/j − (1/(2j)) ∑_a |c_a − n/j|(inf'_colourCount_le). - Chernoff bounds for the new support of a colour at a threshold
k(avg_colourCount_stepCol_ge,avg_colourCount_stepCol_le_tail): with the mean bounded byμ, the tail beyondkis at mostexp(−(k − μ)²/(k + μ))(upper) orexp(−(μ − k)²/(2μ))(lower). - Anti-concentration (
avg_abs_colourCount_stepCol_sub_ge): the new support of a colour is at mean absolute distance at least(9/256) σfrom any fixed value,σ²being the sum of the agents' variances (Paley–Zygmund,avg_pz_zero_one). This replaces the Central Limit Theorem of BCNPT16, Equation (4).
A dead colour stays dead.
The supports of the colours of any superset of the remaining colours add up to n.
If every colour of c (j colours) has more than n/j − m agents, every colour has at most
n/j + (j − 1) m agents.
∑_b (c_b/n)² ≤ M/n when every support is at most M.
The smallest of the supports of the colours of J ⊇ image c is at most
n/|J| − (1/(2|J|)) ∑_{a ∈ J} |c_a − n/|J||.
The expected new support of a is the sum of the agents' adoption probabilities.
Lower bound on the expected new support (Lemma 2.1 with c_b ≤ M for all b):
𝔼[C_a'] ≥ c_a (1 + c_a/n − M/n).
Upper bound of Lemma 2.1 at a level b ≥ c_a, with at most j colours:
𝔼[C_a'] ≤ b (1 + b/n − 1/j).
Under the hypotheses of Equation (6) (every colour of x, with j ≥ 2 colours, has more
than n/j − m agents, 8 j m ≤ n), every colour of x has expected new support at least
n/j − 2m: the supports are at most M = n/j + (j − 1) m, so ∑_b (c_b/n)² ≤ M/n, and
c ↦ c (1 + c/n − M/n) is increasing, with value at least n/j − 2m at c = n/j − m.
Chernoff upper tail for the new support of a colour, at a threshold k: if the mean is
at most μ with 0 < μ < k, then P(C_a' ≥ k) ≤ exp(−(k − μ)²/(k + μ)).
Chernoff lower tail for the new support of a colour, at a threshold k: if the mean is
at least μ with 0 < k < μ, then P(C_a' ≤ k) ≤ exp(−(μ − k)²/(2μ)).
Anti-concentration of the new support of a colour (replaces the Central Limit Theorem of
BCNPT16, Equation (4)): if the agents' variances add up to σ² ≥ 1, the new support is at mean
absolute distance at least (9/256) σ from any fixed value θ. If the mean is at distance at
least σ/4 from θ, this is Jensen's inequality; otherwise, on the Paley–Zygmund event
σ² ≤ 4 S² (probability at least 9/64) the centered sum S is at least σ/2 in absolute
value.
Variance near the uniform configuration (for BCNPT16, Equation (4)): if every colour of
x (j ≥ 2 colours) has more than n/j − n u agents with j u ≤ 1/250, the agents' variances
for the new support of each colour add up to at least n/(4j). The adoption probability
p = X (1 + X − ‖x‖²) (X = c_a/n) lies between (1 − 1/250)²/j and (1/2 + 1/250)(1 + 1/250),
and the variance is n p (1 − p).