The lower bound for h-plurality (Section 4.3) #
In the h-plurality dynamics every node samples h nodes uniformly at
random (with repetition, possibly itself) and adopts the most frequent color
among them, breaking ties uniformly at random.
Tie-breaking. Each node also draws a uniform ordering σ of its h sample
positions, and adopts the color of the tied position of smallest σ-rank
(hplur). All tied colors appear equally often, so this picks each tied color
with the same probability, as the paper requires.
- Lemma 4.11 (
lemma_4_11,lemma_4_11_paper): if colorjhas at mosta ≤ 2n/knodes, it has at leasta (1 + 2h²/k)nodes after one round with probability at mostexp(-2 (a h²/k)² / n). A node adoptsjonly if it seesjat least twice (probability at most(h²/2)(c_j/n)²), or exactly once, in which case allhsampled colors are distinct andjmust be at the position ranked first (probabilityc_j/n). - Theorem 4.12 (
theorem_4_12,theorem_4_12_log): from a coloring with at most(3/2)(n/k)nodes per color, the process is not monochromatic afterT ≤ (k/(2h²)) log (4/3)rounds, except with probabilityk T exp(-2 n h⁴/k⁴).
The paper states Lemma 4.11 with the factor 1 + h²/k but proves
1 + 2h²/k, which is also what Theorem 4.12 uses.
Two finite-probability facts #
Fubini for uniform averages over a product.
The model #
The randomness of one node in one round: h samples and an ordering of the
sample positions used to break ties.
Equations
- Plurality.HSample n h = ((Fin h → Fin n) × Equiv.Perm (Fin h))
Instances For
One round of h-plurality: the randomness of every node.
Equations
- Plurality.HRound n h = (Fin n → Plurality.HSample n h)
Instances For
The ranks of the positions whose color is most frequent.
Equations
- Plurality.topRanks cs σ = Finset.image ⇑σ {i : Fin h | ∀ (i' : Fin h), Plurality.mult cs i' ≤ Plurality.mult cs i}
Instances For
The winning position: among the positions with a most frequent color, the
one ranked first by σ.
Equations
- Plurality.winnerPos cs σ = (Equiv.symm σ) ((Plurality.topRanks cs σ).min' ⋯)
Instances For
The plurality color of the sampled colors cs, ties broken by σ.
Equations
- Plurality.hplur cs σ = cs (Plurality.winnerPos cs σ)
Instances For
One round of h-plurality.
Equations
- Plurality.hstep x R v = Plurality.hplur (fun (i : Fin h) => x ((R v).1 i)) (R v).2
Instances For
The coloring after a list of rounds of h-plurality.
Equations
- Plurality.hrun x l = List.foldl Plurality.hstep x l
Instances For
Seen exactly once. If j appears at exactly one sample position and
wins, then all sampled colors are distinct and j is at the position ranked
first.
One node #
Lemma 4.11 #
Lemma 4.11 (growth rate under h-plurality). If color j has at most
a ≤ 2n/k nodes, then after one round it has at least a (1 + 2h²/k) nodes
with probability at most exp(-2 (a h²/k)² / n).
Lemma 4.11, as stated in the paper (with the factor 1 + 2h²/k that its
proof gives): if n/k ≤ c_j ≤ 2n/k, then
P(C_{j,t+1} ≥ (1 + 2h²/k) c_j) ≤ exp(-2 n h⁴/k⁴).
Theorem 4.12 #
Theorem 4.12 (lower bound for h-plurality). Let k ≥ 3. If every color
starts with at most (3/2)(n/k) nodes and (3/2)(1 + 2h²/k)^T ≤ 2, then the
coloring after T rounds of h-plurality is monochromatic with probability
at most k T exp(-2 n h⁴/k⁴).
Theorem 4.12, logarithmic form. Under the hypotheses of theorem_4_12,
the coloring is still not monochromatic after T ≤ (k/(2h²)) log (4/3) rounds,
i.e. Ω(k/h²) rounds, except with probability k T exp(-2 n h⁴/k⁴).