Theorem 4.8 (b): a solver with the clear-majority property is uniform #
Let f have the clear-majority property and let r, g, b be distinct colors
with δ_r ≤ 1 (r is returned on at most one of the six orderings of
(r, g, b)). Start from 23n/60 nodes of color r, n/3 of color g and
17n/60 of color b: r is the unique plurality color with bias n/20.
One round. With only r, g, b present and x = x_r, a node adopts r
only if it sees r at least twice, or sees r, g, b in an order on which
f returns r (clear majority rules out everything else), so
p(r) ≤ 3x² - 2x³ + δ_r x_r x_g x_b ≤ x (3x - 2x² + (1-x)²/4). For
x ≤ 2/5 this is at most 0.97 x (expected_count_le), and Hoeffding's
inequality bounds the probability of jumping above 2n/5
(jump_prob_le).
Many rounds. The frozen chain (frozenStep) stops as soon as r has
more than 2n/5 nodes. On it, Φ = C_r 𝟙[C_r ≤ 2n/5] contracts by 0.97
in every state (frozen_potential_le), and it is stopped within T
rounds with probability at most T e^{-9n/31250} (frozen_stop_le). The
real and frozen chains agree until the frozen chain stops
(foldl_frozen_eq). Hence r survives T₀ = O(log n) rounds with
probability at most 1/4 (alive_le), and so it is never the consensus color
with probability more than 1/4: f is not an (n/20, 1/4)-solver
(not_solver_of_nonuniform).
theorem_4_8_b: an (n/20, 1/4)-solver with the clear-majority property has
the uniform property. The paper's proof of Lemma 4.10 is a sketch covering
δ_r = 1 with (δ_g, δ_b) ∈ {(3,2), (4,1)}; the argument here covers every
triple with some δ ≤ 1, which is every non-uniform triple.
Three colors present #
One round #
Pointwise bound on adopting r. For colors a, b', c among r, g, b,
f returns r only if r appears at least twice or (a, b', c) is an
ordering of (r, g, b) on which f returns r.
Contraction in expectation. With only r, g, b present, δ_r ≤ 1 and
at most 2n/5 nodes of color r, the expected number of r nodes after one
round is at most 0.97 times the current one.
No jump above 2n/5. From at most 2n/5 nodes of color r, one
round ends with more than 2n/5 of them with probability at most
exp(-9n/31250).
The frozen chain #
r has at most 2n/5 nodes.
Equations
- Plurality.LowR r y = (↑(Plurality.count y r) ≤ 2 * ↑n / 5)
Instances For
One round of the chain that stops once r has more than 2n/5 nodes.
Equations
- Plurality.frozenStep f r y t = if Plurality.LowR r y then Plurality.stepWith f y t else y
Instances For
The potential Φ = C_r 𝟙[C_r ≤ 2n/5].
Equations
- Plurality.potential r y = if Plurality.LowR r y then ↑(Plurality.count y r) else 0
Instances For
Φ contracts in every state of the frozen chain.
The frozen chain rarely stops.
Coupling. If the frozen chain has not stopped, it agrees with the real one.
r dies out. After T rounds, r still has a node with probability at
most 0.97^T C_r + T e^{-9n/31250}.
The counterexample #
A non-uniform triple defeats the rule. If f has the clear-majority
property and δ_r ≤ 1 for distinct r, g, b, then from 23n/60 nodes of
color r, n/3 of g and 17n/60 of b (bias n/20), consensus on r
has probability at most 1/4 at every time. Hence f is not an
(n/20, 1/4)-solver (for 60 ∣ n, log n ≥ 20).
Theorem 4.8 (b). If f has the clear-majority property and is an
(n/20, 1/4)-solver (for 60 ∣ n and log n ≥ 20), then f has the uniform
property.