Voter reduces the number of colours fast (BCEKMN17, Lemma 3) #
The Voter process is dual to coalescing random walks (Lemma 4). On the complete graph with
self-loops, one step of the coalescing walks moves the set Z of occupied nodes to its image
walkStep Z y = y '' Z under one uniform round y : Fin n → Fin n, and two walks coalesce when
they move to the same node. This duality is restated here rather than imported, since this
package does not depend on the voter package.
numColours_voterRun_le: Lemma 4 (the inequalityT^k_V ≤ T^k_Cused by the paper), pathwise: the colours of Voter after the roundsy₀, …, y_{T-1}are images of the walks started on all nodes and moved by the rounds in reverse order.voter_dual: the probabilistic form, Equation (6) as the inequality used: Voter has more thankcolours at timeTwith at most the probability that more thankcoalescing walks remain.walk_drift: the expected drop of the number of walks,E[X_{t+1} | X_t = x] ≤ x − x(x−1)/(3n)for everyx(an exact occupancy computation);walk_drift_paperis the paper's Equation (7),≤ x − x²/(10n)forx ≥ 2.walk_expect_le:E[X_t] ≤ 1 + 3n/t, from any initial set of walks; it replaces the expected coalescence time boundE[T^k_C] ≤ 20 n/k(Equations (18), (19)).voter_reduce_whp: Lemma 3, at mostkcolours remain after24 (n/k) log nrounds with probability at least1 − 1/n.
One step of coalescing random walks on the complete graph with self-loops: the walks at the
nodes of Z move along the round y, and walks on the same node coalesce.
Equations
- ThreeMajority.walkStep Z y = Finset.image y Z
Instances For
The colours of Voter after the rounds l are colours of the nodes still occupied by the
walks started on all nodes and moved by the rounds in reverse order.
Lemma 4 (BCEKMN17), the inequality T^k_V ≤ T^k_C, pathwise: the number of colours of
Voter after the rounds l is at most the number of coalescing walks, started on all nodes, after
the same rounds applied in reverse order (List.foldr applies the last round first).
Equation (6) (BCEKMN17), as the inequality used: after T rounds, Voter has more than
k colours with at most the probability that more than k of the n coalescing walks remain.
The expected number of coalescing walks after one step, from x = |Z| walks, is at most
x − x(x−1)/(3n) (exactly n(1 − (1 − 1/n)^x), the expected number of occupied nodes). This
is the drift of Equation (7) of BCEKMN17, in a form valid for every x.
One more step of the walks: E[X_{t+1}] ≤ m − m(m−1)/(3n) for m = E[X_t], by
walk_drift and the concavity of the bound.
The expected number of coalescing walks after t ≥ 1 steps, from any initial set, is at
most 1 + 3n/t. This replaces the bound E[T^k_C] ≤ 20 n/k of BCEKMN17 (Equations (18),
(19), from the variable drift theorem, Theorem 7) in the proof of Lemma 3.
Expectations along the walks compare on a set of configurations that the walks cannot leave.
Lemma 3 (BCEKMN17): from any configuration, Voter has at most k colours after any
T ≥ 24 (n/k) log n rounds, with probability at least 1 − 1/n.