Theorem 4.8 (a): a solver must follow the clear majority #
Consider two colors r ≠ b and only these two colors present, with fractions
x and y = 1 - x. Under a 3-input rule f, a node adopts r with
probability x³ + Δ_r x² y + (3 - Δ_b) x y², where Δ_r = majCount f r b and
Δ_b = majCount f b r. Hence
p(x) - x = x y (x (Δ_r - 2) + y (2 - Δ_b)).
If Δ_r ≤ 2 ≤ Δ_b this is ≤ 0 in every state, so the number of red nodes
is a supermartingale, its expectation never exceeds its initial value, and from
5n/8 red nodes (bias n/4) the probability that all nodes are red at any time
is at most 5/8 (not_solver_of_drift). No optional stopping is needed.
theorem_4_8_a: a (n/4, 1/4)-solver has, for every pair of colors, either
Δ_r = Δ_b = 3 (it follows the clear majority on that pair) or
Δ_r, Δ_b ≤ 1.
The remaining case. The paper's proof also claims the case
Δ_r, Δ_b ≤ 1, but it only checks the supermartingale inequality when red is
the majority. In this case p(x) - x > 0 when red is the minority: the process
is pulled towards an interior point x* = (2 - Δ_b)/(4 - Δ_r - Δ_b), and which
color eventually wins depends on how the process leaves that point, which is
not addressed. That case is left open here.
The red drift. With only r and b present and Δ_r ≤ 2 ≤ Δ_b, the
expected number of red nodes does not increase in one round.
The red count is a supermartingale: its expectation after T rounds is
at most its initial value.
If Δ_r ≤ 2 ≤ Δ_b, the rule is not an (n/4, 1/4)-solver. From 5n/8
red and 3n/8 blue nodes, all nodes are red at time T with probability at
most 5/8, for every T.
Theorem 4.8 (a), proved cases. If f is an (n/4, 1/4)-solver (with
8 ∣ n), then for every pair of distinct colors either f follows the clear
majority on that pair (Δ_r = Δ_b = 3) or Δ_r, Δ_b ≤ 1. The paper claims
that the second alternative is also impossible; see the module docstring.