The saturation phase (Lemmas 3.6 and 3.7) #
Once the bias is at least n/3, the number C̄ₘ = n - Cₘ of nodes that do
not support the plurality color m decreases geometrically.
- Lemma 3.6 (
lemma_3_6):(n - cₘ)(1 - cₘ²/n²) ≤ 𝔼[C̄_{m,t+1}] ≤ (n - cₘ)(1 - s cₘ/n²). - Lemma 3.7 (
lemma_3_7_i,lemma_3_7_ii): ifs(c) ≥ n/3thenC̄_{m,t+1} < (17/18)(n - cₘ)except with probability1/n²as long asn - cₘ ≥ n^{1/4} log n; below that threshold, all nodes supportmafter one more round except with probabilityn^{-1/5}, and the threshold is not exceeded again except with probability1/n².
The paper omits the proof of Lemma 3.7; the one here uses Lemma 3.6 with the
bounds s cₘ ≥ n²/9 (first regime) and s ≥ n - 2(n - cₘ) (second regime),
the closed-form Chernoff upper tail Dynamics.avg_chernoff_upper_log, and Markov's
inequality Dynamics.avg_markov_one. "Sufficiently large n" is made explicit as log n ≥ 40.
The per-node indicator of not adopting m.
Equations
- Plurality.notAdopt x m x✝ t = 1 - Plurality.adopt Plurality.maj3 x m t
Instances For
The expected number of nodes not supporting m after one round.
Lemma 3.7, first regime. If M(c) = {m}, s(c) ≥ n/3 and
n - cₘ ≥ n^{1/4} log n, then P(C̄_{m,t+1} ≥ (17/18)(n - cₘ)) ≤ 1/n².
Lemma 3.7, second regime. If M(c) = {m}, s(c) ≥ n/3 and
n - cₘ < n^{1/4} log n, then P(C̄_{m,t+1} > 0) ≤ n^{-1/5} and
P(C̄_{m,t+1} ≥ n^{1/4} log n) ≤ 1/n².