The dropping stage (BCNPT16, Lemmas 3.4 and 3.5; roadmap MAJ-12 (a)) #
Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many opinions,
SODA 2016, arXiv:1508.06782 (BCNPT16 below), Section 3. Once a colour a is below
n/j − 16 √(j n log n) agents in a configuration with at most j colours, Lemma 2.1 makes it
shrink geometrically: its gap to the average n/j grows by a factor 1 + 1/(4j) per round, and
below n/(2j) the support itself shrinks by a factor 1 − 1/(2j).
dropping_stage1: Lemma 3.4. WithinO(j log n)rounds the support ofaisO(j² log n), with probability at least1 − 1/n(at every timetwithC j log n ≤ t ≤ n).dropping_stage2: Lemma 3.5. From at mostn/(2j)agents, colouradies withinO(j log n)rounds with probability at least1/2.
One-round estimates (Chernoff upper tails, avg_colourCount_stepCol_ge): below n/(2j) the
support shrinks by 1 − 1/(4j) (avg_colourCount_stepCol_ge_shrink), between n/(2j) and n/j
the gap to n/j grows by 1 + 1/(4j) (avg_colourCount_stepCol_ge_gap). Lemma 3.4 follows them
along one moving target stage1Level (stage1_step, Dynamics.expList_escape); Lemma 3.5
iterates the contraction of min(c_a, n/(2j)) (expList_min_colourCount_le, BCNPT16,
Appendix B) and applies Markov's inequality.
Both assume C j³ log n ≤ n, implied by the paper's j ≤ n^{1/3 − ε} for large n. The proof of
Lemma 3.4 needs a minor correction: from the paper's threshold n/j − √(j n log n) the one-round
Chernoff bound (Appendix B, Equation (7)) only gives failure probability n^{-1/12}, still at least
n^{-1/10} during the first j/10 rounds, so the iterated union bound exceeds 1 as soon as
j ≥ 20 n^{1/10}, and the same happens near the floor j² log n. With the threshold
n/j − 16 √(j n log n) and the floor C j² log n for a large C the failure is at most n^{-5}
per round.
From at most j colours and c_a ≤ b ≤ n/(2j), the expected new support of a is at most
(1 − 1/(2j)) b (Lemma 2.1).
One round below n/(2j) (Chernoff upper tail): from at most j colours and
c_a ≤ b ≤ n/(2j), the new support of a reaches b (1 − 1/(4j)) with probability at most
exp(−b/(32 j²)).
The potential ψ = min(c_a, n/(2j)) of Lemma 3.5 contracts by 1 − 1/(2j) per round, up to
the event that c_a is above n/(2j).
Union bound over rounds: from c_a ≤ n/(2j) and at most j colours, if every round from
such a state takes c_a above n/(2j) with probability at most ε, then after s rounds
c_a > n/(2j) with probability at most s ε.
The recursion of Lemma 3.5 (BCNPT16, Appendix B): 𝔼 ψ(x_s) ≤ (1 − 1/(2j))^s n/(2j) + (n/(4j²)) ε s².
One round between n/(2j) and n/j (Chernoff upper tail): from at most j colours and
c_a ≤ b with n/(2j) < b < n/j, the gap g = n/j − b grows by a factor 1 + 1/(4j)
except with probability at most exp(−g²/(32 j n)): the new support of a reaches
b − g/(4j) with at most that probability (the mean is at most b − g/(2j)).
The target levels of the proof of Lemma 3.4 (BCNPT16, Appendix B, with the corrections listed
in FORMALIZATION_DIFFERENCES.md):
max(n/j − m (1 + 1/(4j))^s, (n/(2j)) (1 − 1/(4j))^(s − s_A), K). The
first term is the gap-growth block (until c_a ≤ n/(2j)), the second the geometric decrease
from n/(2j) (after round s_A), and K the floor.
Equations
Instances For
One round along the schedule of Lemma 3.4: from at most j colours and c_a below the
level of round s, the new support of a exceeds the level of round s + 1 with probability at
most 1/n² (exp(−2 log n)). Above n/(2j) the level is n/j − m (1 + 1/(4j))^s and the gap
grows (avg_colourCount_stepCol_ge_gap); below, it shrinks by 1 − 1/(4j) down to the floor
K ≥ 64 j² log n (avg_colourCount_stepCol_ge_shrink).
Lemma 3.4 (BCNPT16, dropping stage 1): there is C such that, for j ≥ 2 with
C j³ log n ≤ n, from every configuration x with at most j colours and every colour a with
at most n/j − 16 √(j n log n) agents, at every time t with C j log n ≤ t ≤ n colour a has
more than C j² log n agents with probability at most 1/n.
Lemma 3.5 (BCNPT16, dropping stage 2): there is C such that, for j ≥ 2 with
C j³ log n ≤ n, from every configuration x with at most j colours and every colour a with
at most n/(2j) agents, colour a has died after any t ≥ C j log n rounds with probability at
least 1/2.