3-Majority and Plurality Consensus
\(n\) anonymous nodes each support one of \(k\) colors. In every round each node samples three nodes uniformly at random (with repetition, possibly itself) and adopts the majority color among them, or the first one if all three differ. If some color \(m\) leads every other color by a sufficiently large bias \(s\), the process reaches consensus on \(m\). The paper proves that this takes \(O(\lambda \log n)\) rounds w.h.p. whenever \(c_m \ge n/\lambda \) and \(s \ge c\sqrt{\lambda n\log n}\) (Theorem 24), that \(\Omega (k\log n)\) rounds are needed from balanced configurations, that 3-majority is essentially the only 3-input rule that solves plurality consensus, and that sampling \(h {\gt} 3\) nodes speeds the process up by at most a factor \(O(h^2)\).
The upper bound (Section 3), including the headline bound \(O(\min \{ k,(n/\log n)^{1/3}\} \log n)\) of Corollary 26, is fully formalized, with no sorry, on the finite probability layer of the shared dynamics package: all randomness is uniform over finite types, multi-round probabilities are iterates of a finite Markov kernel, and the concentration inequalities (Chernoff, Hoeffding, Bernstein) are proved from scratch. The lower bounds of Section 4 are formalized as well, with two exceptions where the paper’s argument does not go through: the \(\Omega (k\log n)\) bound is proved for \(k \le n^{1/4-\delta }\) rather than up to \((n/\log n)^{1/4}\), and part (a) of Theorem 4.8 (Theorem 44) leaves open rules with \(\Delta _r, \Delta _b \le 1\). Observation 3.9 (an adversary) is not formalized. Beyond the paper, Section 3.7 proves that with two opinions 3-majority reaches consensus from any configuration, including a perfectly balanced one, within \(O(\log n)\) rounds w.h.p., and Section 3.8 identifies binary 3-majority with conformist transmission on counts.
The package also contains the library ThreeMajority. Sections 5 to 13 give a complete, elementary proof that with two opinions 3-majority reaches consensus within \(O(\log n)\) rounds with probability \(1-O(1/n)\) from a \(3/5\) majority; Theorem 28 transfers it to colorings with \(k = 2\). Section 14 formalizes, for any number of colours, the comparison of 3-Majority with the Voter model of Berenbrink et al. (PODC 2017) and their bound \(O(n^{3/4}\log ^{7/8}n)\) on the consensus time from any configuration. Its second phase is Theorem 3.1 of Becchetti et al. (SODA 2016), from \(k\le n^{1/3-\varepsilon }\) colours, which Section 15 formalizes; together they give the bound without hypothesis.
1 The model
A coloring is a map \(x \colon [n] \to [k]\). The number of nodes of color \(j\) is \(c_j = |\{ v : x(v) = j\} |\), and \(\sum _j c_j = n\). The vector \(c = (c_1,\dots ,c_k)\) is the paper’s \(k\)-color distribution (\(k\)-cd), the configuration vector of Definition 95 at colors \([k]\).
A 3-input rule is a map \(f \colon [k]^3 \to [k]\) with \(f(a,b,c) \in \{ a,b,c\} \). The 3-majority rule is \(\mathrm{maj}_3(a,b,c) = b\) if \(b = c\) and \(a\) otherwise; it returns the majority color, and the first color if all three differ.
A round is a map \(r \colon [n] \to [n]^3\) (the three samples of every node), drawn uniformly. The next coloring under rule \(f\) is \(v \mapsto f(x(r_v^1), x(r_v^2), x(r_v^3))\). The process after \(T\) rounds folds this step over \(T\) independent uniform rounds. Under 3-majority, a round is the round of 3-Majority with colours of any type (Definition 95) at colors \([k]\), by definition.
\(x\) is in consensus on \(m\) if every node has color \(m\), i.e. \(c_m = n\). For every 3-input rule, consensus is absorbing.
The process with rule \(f\) is the finite Markov kernel on colorings whose row at \(x\) is the law of one round of \(f\) from \(x\). Its \(T\)-step event probabilities are the expectations over \(T\) independent uniform rounds.
2 The next expected coloring
The new count of color \(j\) is a sum of \(n\) independent indicators, one per node. Under 3-majority, a node adopts \(j\) with probability \(x_j^2 + x_j(1 - \sum _h x_h^2)\), where \(x_h = c_h/n\).
The three samples are independent with law \((x_h)_h\). Summing the indicator of \(\mathrm{maj}_3(a,b,c) = j\) first over \(c\), then \(b\), then \(a\) gives the polynomial.
For every coloring and every color \(j\),
Multiply the adoption probability of Lemma 6 by \(n\).
3 The upper bound
This section formalizes Theorem 3.8 of Becchetti, Clementi, Natale, Pasquale, Silvestri and Trevisan, Simple Dynamics for Plurality Consensus (SPAA 2014), and its Corollaries 3.10 to 3.12. The SPAA proof of Theorem 3.8 needs a minor correction (small repairs: the saturation phases as defined are not shown to be preserved, and a union bound over the competing colors is missing), and the repaired proof is what is formalized (details).
3.1 Plurality, bias, \(\alpha \) and \(\gamma \)
For a \(k\)-cd \(c\) with \(\sum _h c_h = n\): \(m(c) = \max _h c_h\), \(M(c) = \{ j : c_j = m(c)\} \), the bias \(s(c) = m(c) - \max _{h \notin M(c)} c_h\) if \(|M(c)| = 1\) and \(0\) otherwise, \(\alpha (c) = (n - m(c))\, s(c)/n^2\) and \(\gamma (c) = (n\, m(c) - \sum _h c_h^2)/n^2 - \alpha (c)\).
If \(c_m = m(c)\) then \(c_h + s(c) \le m(c)\) for every \(h \ne m\), with equality for some \(h\) when \(k \ge 2\). Moreover \(\gamma (c)\, n^2 = \sum _{h \ne m} c_h\, (m(c) - s(c) - c_h)\).
For every \(k\)-cd \(c\): (a) \(0 \le s(c) \le m(c) - (n - m(c))/(k-1)\); (b) \(0 \le \alpha (c) \le \min \{ s(c)/n,\ 1/4\} \); (c) \(0 \le \gamma (c) \le 1/8\).
(a) The \(k-1\) other colors each have at most \(m(c) - s(c)\) nodes. (b) \((n - m)m \le n^2/4\) and \(s \le m\). (c) Use the identity of Lemma 9: every summand is nonnegative, the color attaining the bias contributes \(0\), and the rest is at most \(d(n - m - d) \le n^2/8\) with \(d = m(c) - s(c)\).
Let \(m \in M(c)\) and let \(\ell \ne m\) have the most nodes among the other colors. Then (a) \(\mu _m(c) = c_m(1 + \gamma + \alpha )\); (b) \(\mu _j(c) = c_j(1 + \gamma + \alpha - (m(c) - c_j)/n)\) for every \(j\); (c) \(\mu _\ell (c) = c_\ell (1 + \gamma + \alpha - s(c)/n)\).
3.2 Concentration
For \(X = \sum _i Y_i(\omega _i)\) with independent uniform coordinates: Bernstein’s inequality \(\Pr (X \ge \mathbb {E}X + \lambda ) \le \exp (-\lambda ^2/(2\sigma ^2(1 + b\lambda /(3\sigma ^2))))\) when \(Y_i - \mathbb {E}Y_i \le b\) and \(\sum _i \mathrm{Var}\, Y_i \le \sigma ^2\); Hoeffding’s inequality for \(\{ 0,1\} \) coordinates; the multiplicative Chernoff lower tail \(\Pr (X \le (1-\delta )\mu ) \le \exp (-\delta ^2\mu /2)\); Markov’s inequality \(\Pr (X \ge 1) \le \mathbb {E}X\) for nonnegative coordinates; and the closed-form Chernoff upper tail \(\Pr (X \ge k) \le \exp (k - \mu - k\log (k/\mu ))\) for \(\mathbb {E}X \le \mu \le k\). All are proved once in the shared dynamics library (Dynamics/Concentration.lean, Dynamics/Chernoff.lean, Dynamics/Tail.lean).
3.3 Growth of the bias
If \(M(c) = \{ m\} \) then for every \(j \ne m\),
If \(M(c) = \{ m\} \) then \(\Pr (C_{m,t+1} \le c_m(1 + \gamma + \alpha /2) \mid C_t = c) \le \exp (-c_m\alpha ^2/11)\).
The multiplicative Chernoff lower tail with \(\delta = \alpha /(2(1 + \gamma + \alpha ))\).
If \(M(c) = \{ m\} \), \(0 {\lt} \lambda \le 2/3\), \(\lambda n \le c_m \le (2/3)n\) and \(s(c) \ge 22\sqrt{(1/\lambda )\, n\log n}\), then for every \(j \ne m\)
3.4 Saturation
For every \(m \in M(c)\), writing \(\bar C_{m,t+1} = n - C_{m,t+1}\),
Let \(\log n \ge 40\), \(M(c) = \{ m\} \). (i) If \(s(c) \ge n/3\) and \(n - c_m \ge n^{1/4}\log n\) then \(\Pr (\bar C_{m,t+1} \ge \frac{17}{18}(n - c_m)) \le 1/n^2\). (ii) If \(n - c_m {\lt} n^{1/4}\log n\) then \(\Pr (\bar C_{m,t+1} {\gt} 0) \le n^{-1/5}\) and \(\Pr (\bar C_{m,t+1} \ge n^{1/4}\log n) \le 1/n^2\).
The paper omits this proof. (i) By Lemma 16 and \(s\, c_m \ge n^2/9\), \(\mathbb {E}\bar C_{m,t+1} \le \frac89(n - c_m)\); apply the closed-form Chernoff upper tail at ratio \(17/16\). (ii) Here \(s(c) \ge n - 2(n - c_m)\), so \(\mathbb {E}\bar C_{m,t+1} \le 3(n-c_m)^2/n \le 3\log ^2 n\, e^{-(\log n)/2}\); apply Markov’s inequality for the first bound and the Chernoff upper tail for the second.
3.5 Nested phases and the main theorem
Let \(A_1 \supseteq \cdots \supseteq A_T\) be sets of states of a finite Markov chain such that from every state of \(A_i\) the chain stays in \(A_i\) with probability \(\ge 1-\varepsilon \) and, for \(i {\lt} T\), moves into \(A_{i+1}\) with probability \(\ge 1 - \nu \). Then from any state of \(A_1\), after \(\ell T\) steps the chain is in \(A_T\) with probability at least \(1 - T(\ell \varepsilon + \nu ^\ell )\).
The paper omits this proof. Phase by phase: within \(\ell \) steps the chain leaves \(A_i\) with probability at most \(\ell \varepsilon \), and fails to jump into \(A_{i+1}\) in each of the \(\ell \) steps with probability at most \(\nu ^\ell \). The hypothesis \(\varepsilon \le \nu \) of the paper is not needed.
Fix \(m\), \(\lambda \), \(\Lambda \) and let \(q = 1 + 1/(6\lambda )\), \(B = n^{1/4}\log n\). Growth phase \(i\): \(c_m {\gt} \frac23 n\), or \(M(c) = \{ m\} \), \(c_m \ge n/\lambda \) and \(s(c) \ge \Lambda q^i\). Saturation phase \(j\): \(n - c_m {\lt} \max \{ \frac n3 (\frac{17}{18})^j,\ B\} \). Consensus: \(c_m = n\).
If \(n - c_m {\lt} n/3\) then \(M(c) = \{ m\} \) and \(s(c) \ge n/3\). If \(m\) leads every other color by at least \(g {\gt} 0\) and \(c_m \ge g\), then \(M(c) = \{ m\} \) and \(s(c) \ge g\). A color without nodes stays without nodes.
Let \(\log n \ge 40\), \(k \ge 2\), \(\lambda \ge 3\) and \(\Lambda \ge 22\sqrt{\lambda n \log n}\). From growth phase \(i\) the chain enters growth phase \(i+1\) with probability \(\ge 1 - 1/n\). From saturation phase \(j\) it enters saturation phase \(j+1\) with probability \(\ge 1 - 1/n^2\). From fewer than \(B\) dissenting nodes it reaches consensus with probability \(\ge 1 - n^{-1/5}\), and consensus is kept with probability \(1\). The phase sets are nested, and growth phase \(i\) lies in saturation phase \(0\) once \(\Lambda q^i {\gt} n\).
Growth, case \(c_m {\gt} \frac23 n\): saturation phase \(0\) moves into saturation phase \(1\), which lies in \(\{ c_m {\gt} \frac23 n\} \). Growth, otherwise: apply Lemma 15 with \(1/\lambda \) to each other color \(j\) that currently has a node, and to the growth of \(c_m\). There are fewer than \(n - c_m\) such colors, so a union bound gives failure probability at most \(n/n^2\). Colors without nodes stay empty, and the color attaining the bias has a node (otherwise \(c_m = n\)), so after a successful round \(m\) leads every other color by \(s(c)\, q\) and Lemma 21 applies. Saturation: Lemma 17(i) above \(B\) dissenters and Lemma 17(ii) below.
With \(T_1 = \lceil \log n/\log q\rceil \) growth phases, \(T_2 = \lceil \log n/\log (18/17)\rceil + 1\) saturation phases and one consensus phase, \(T = T_1 + T_2 + 1 \le 13\lambda \log n\) for \(\lambda \ge 3\) and \(\log n \ge 40\).
\(\log (1+x) \ge x/(1+x)\) gives \(\log q \ge 1/(6\lambda +1)\) and \(\log (18/17) \ge 1/18\).
Let \(\log n \ge 40\), \(k \ge 2\) and \(\lambda \ge 3\). If \(M(c) = \{ m\} \), \(c_m \ge n/\lambda \) and \(s(c) \ge 22\sqrt{\lambda n\log n}\), then after \(10T \le 130\lambda \log n\) rounds all nodes support \(m\) with probability at least \(1 - 11T/n \ge 1 - 143\lambda \log n/n\).
Apply Lemma 18 to the kernel of 3-majority with the \(T_1\) growth phases, the \(T_2\) saturation phases and consensus, \(\varepsilon = 1/n\), \(\nu = n^{-1/5}\) and \(\ell = 10\), so that \(\nu ^\ell = n^{-2}\). The initial coloring is in growth phase \(0\); growth phase \(T_1\) lies in saturation phase \(0\) because \(\Lambda q^{T_1} \ge 22n\); saturation phase \(T_2 - 1\) lies below \(B\) dissenters because \(\frac n3(\frac{17}{18})^{T_2-1} \le \frac13\).
The paper states the failure probability as \(11T/n^2\); the extra factor \(n\) comes from the union bound over competing colors in Lemma 22, which the paper omits. The paper’s hypothesis \(\lambda {\lt} \sqrt n\) is not used; it only makes the hypothesis on \(s(c)\) satisfiable.
If \(M(c) = \{ m\} \) and \(s(c) \ge 22\sqrt{\min \{ 2k, (n/\log n)^{1/3}\} \, n\log n}\), then 3-majority reaches consensus on \(m\) in \(O(\min \{ 2k, (n/\log n)^{1/3}\} \log n)\) rounds w.h.p. Precisely, for \(\log n \ge 40\) and \(k \ge 2\): at most \(130\lambda \log n\) rounds with probability at least \(1 - 143\lambda \log n/n\).
Take \(\lambda = \min \{ 2k, (n/\log n)^{1/3}\} \). If \(\lambda = 2k\) then \(c_m \ge n/k\) by pigeonhole; otherwise \(\lambda ^3 = n/\log n\), so \(22\sqrt{\lambda n\log n} = 22n/\lambda \) and \(c_m \ge s(c) \ge n/\lambda \). Moreover \(\lambda \ge 3\) because \(k \ge 2\) and \(n = e^{\log n} \ge 27\log n\).
If \(c_m \ge n/\log ^\ell n\) and \(s(c) \ge 22\sqrt{n\log ^{\ell +1}n}\), consensus takes \(O(\log ^{\ell +1} n)\) rounds w.h.p. If \(c_m \ge n/\beta \) and \(s(c) \ge 22\sqrt{\beta n\log n}\) for a constant \(\beta \ge 3\), it takes \(O(\log n)\) rounds w.h.p.
Take \(\lambda = \log ^\ell n\) (with \(\ell \ge 1\), so that \(\lambda \ge 3\)) and \(\lambda = \beta \) in Theorem 24.
3.6 Two colors
In the binary 3-majority process, if the initial majority leads by at least \(22\sqrt{3n\log n}\) nodes (a fraction \(\frac12 + O(\sqrt{\log n/n})\)) and \(\log n \ge 40\), all nodes adopt it within at most \(390\log n\) rounds with probability at least \(1 - 429\log n/n\).
3.7 Two colors from any configuration
This part goes beyond the paper: it follows the symmetry-breaking argument for the binary median dynamics of Doerr, Goldberg, Minder, Sauerwald and Scheideler (SPAA 2011), as described in Becchetti, Clementi, Natale, Consensus dynamics: an overview (SIGACT News 2020, §4, Case 3), here for binary 3-majority. Let \(I\) be the set of nodes with opinion \(1\) and \(s = |I| - (n - |I|)\) the gap. After one round, \(s' = 2\sum _v Y_v - n\) for independent \(\{ 0,1\} \)-valued \(Y_v\) with mean \(p = 3x^2 - 2x^3\), \(x = |I|/n\), so \(\mathbb {E}s' = s\, (3/2 - s^2/(2n^2))\).
If \(n \ge 5\) and \(|s| \le 4\sqrt n/25\), then \(|s'| \ge \sqrt n/5\) with probability at least \(9/64\).
The centered sum \(S = \sum _v (Y_v - p)\) has variance \(\sigma ^2 = np(1-p) \ge n/5\) and fourth moment at most \(\sigma ^2 + 3\sigma ^4\), so by Paley–Zygmund \(4S^2 \ge \sigma ^2\) with probability at least \(9/64\). Then \(|s'| = |2S + \mathbb {E}s'| \ge \sqrt{n/5} - \frac32|s| \ge \sqrt n/5\).
If \(0 \le s \le n/2\) and \(\lambda \ge 0\), then \(s' {\gt} \frac{11}{8}s - 2\lambda \) with probability at least \(1 - e^{-2\lambda ^2/n}\).
\(\mathbb {E}s' \ge \frac{11}{8}s\) for \(0 \le s \le n/2\), and Hoeffding’s inequality bounds the lower tail of \(\sum _v Y_v\).
There is \(C {\gt} 0\) such that, for \(\log n \ge 40\), from any configuration the gap reaches \(22\sqrt{3n\log n}\) in absolute value within any \(t \ge C\log n\) rounds with probability at least \(1 - 1/n\).
Apply the hitting-time bound of Doerr et al. (their Claim 2.9, Dynamics.Kernel.drift_hitting_log) to \(X = \lfloor |s|/(\sqrt n/100)\rfloor \) with \(q = n\), \(c_1 = 5/4\), \(c_2 = 1/320000\), \(c_3 = 9/64\), \(c_4 = 1000\), \(c_6 = 1\); by the symmetry between the opinions assume \(s \ge 0\). If \(X = 0\), Lemma 30 gives \(X' \ge 20 \ge 1\) with probability \(9/64\). If \(1 \le X {\lt} 16\), the same lemma gives \(X' \ge 20 \ge \frac54 X\) with probability \(9/64 \ge 1 - e^{-X/320000}\). If \(16 \le X {\lt} 1000\log n\), then \(s \le n/2\), and Lemma 31 with \(\lambda = X\sqrt n/3200\) gives \(s' {\gt} \frac{21}{16}X\sqrt n/100\), hence \(X' \ge \frac54 X\), except with probability \(e^{-X^2/5120000} \le e^{-X/320000}\). Reaching \(X \ge 1000\log n\) means \(|s| \ge 10\sqrt n\log n \ge 22\sqrt{3n\log n}\).
Let \(P\) be an absorbing event of a finite Markov chain. If from every state of \(B\) the chain is in \(P\) after \(T\) steps with probability at least \(1 - \varepsilon \), then from any state it is in \(P\) at time \(t + T\) with probability at least \(\Pr (T_B \le t) - \varepsilon \). If moreover from every state the chain is in \(P\) after \(T_1\) steps with probability at least \(1 - \varepsilon \), and from \(a\) after \(T_0\) steps with probability at least \(1 - \delta \), then from \(a\) it is in \(P\) after \(T_0 + T_1\) steps with probability at least \(1 - \delta \varepsilon \).
The first claim by induction on \(t\), through the recursion of \(\Pr (T_B \le t)\) and the monotonicity in time of an absorbing event; the second by the Markov property at time \(T_0\).
There is \(C {\gt} 0\) such that, for \(\log n \ge 40\), from any configuration (in particular from a perfectly balanced one) all nodes hold the same opinion after any \(T \ge C\log n\) rounds with probability at least \(1 - C\log n/n\); and, for \(\log n \ge C\), with probability at least \(1 - 1/n\).
Theorem 32, then Corollary 29 applied to the set of nodes of opinion \(1\) or to its complement, composed by Lemma 33; consensus on either opinion is absorbing, so further rounds keep it. For the second bound, two consecutive blocks each fail with probability at most \(\varepsilon = C_0\log n/n\), and \(\varepsilon ^2 \le 1/n\).
3.8 Two colors: mean field and conformist transmission
This part goes beyond the paper; it relates binary 3-majority to models of other fields (row three-majority of the cross-field dictionary). The relations “same chain on counts” (a lumping) and “same mean-field map” are defined in the shared dynamics package, together with the majority map \(m(x) = 3x^2 - 2x^3\), conformist transmission and Galam’s map.
One round maps the fraction \(x = |I|/n\) of nodes with opinion \(1\) to \(m(x) = 3x^2 - 2x^3\) in expectation; \(m\) is also conformist transmission with \(D = 1\) and Galam’s map with groups of three.
The exact one-round expectation of Lemma 68, divided by \(n\).
In a population of \(n\) with non-overlapping generations, every new individual samples three models with replacement from the whole previous generation and acquires a variant held by \(j\) of them with probability \(0\), \(\frac13 - \frac D3\), \(\frac23 + \frac D3\), \(1\) for \(j = 0,1,2,3\) (Boyd and Richerson). From \(k\) carriers, the next generation has \(\mathrm{Bin}(n, p + Dp(1-p)(2p-1))\) carriers, \(p = k/n\).
The mean-field map of conformist transmission is \(p \mapsto p + Dp(1-p)(2p-1)\). Under binary 3-majority the number of nodes with opinion \(1\) is conformist transmission with \(D = 1\): from \(k\) such nodes, one round leads to \(\mathrm{Bin}(n, m(k/n))\) of them.
The binomial law has mean \(np\). A round draws the sample triples of the nodes independently and uniformly, so the indicators that the nodes adopt opinion \(1\) are independent Bernoulli coins with the probability \(m(k/n)\) that the majority of a uniform triple holds \(1\), and their number is binomial.
4 Lower bounds
4.1 Lower bound for 3-majority
If a round-based process starts in \(G_0\) and, for every \(t {\lt} T\), one round from any state of \(G_t\) misses \(G_{t+1}\) with probability at most \(p\), then after \(T\) rounds it lies outside \(G_T\) with probability at most \(Tp\).
Induction on \(T\), conditioning on the first round.
Let \(k\sqrt{n\log n} \le b \le n/k\). If \(c_j \le n/k + b\), then \(\Pr (C_{j,t+1} \ge n/k + (1 + 3/k)b \mid C_t = c) \le 1/n^2\).
By Cauchy–Schwarz \(\sum _h c_h^2 \ge n^2/k\), so \(\mu _j \le c_j(1 + c_j/n - 1/k)\). Writing \(c_j = n/k + a\) with \(a \le b\), this is at most \(n/k + (1+1/k)b + b^2/n \le n/k + (1+2/k)b\). Hoeffding’s inequality with deviation \(b/k \ge \sqrt{n\log n}\) gives \(1/n^2\).
Let \(k \ge 3\) and suppose every color starts with at most \(n/k + b\) nodes, where \(b \ge k\sqrt{n\log n}\). If \(b(1 + 3/k)^T \le n/k\), in particular if \(T \le \frac k3 \log \frac{n}{kb}\), then the coloring after \(T\) rounds is monochromatic with probability at most \(kT/n^2\).
With \(b = \max \{ (n/k)^{1-\varepsilon }, k\sqrt{n\log n}\} \) this gives \(\Omega (k\log (n/(kb)))\) rounds, which is \(\Omega (k\log n)\) for \(k \le n^{1/4-\delta }\). The paper states \(\Omega (k\log n)\) for all \(k \le (n/\log n)^{1/4}\), but at that end \(n/k = k\sqrt{n\log n}\) and the argument gives nothing. The paper’s proof also chooses the thresholds after seeing the trajectory; the union bound needs the fixed schedule used here.
4.2 Which 3-input rules solve plurality consensus
A rule is conservative if it returns one of its inputs. It has the clear-majority property if it returns the majority color whenever two inputs agree. For colors \(r \ne b\), \(\Delta _r\) counts the orderings of \((r,r,b)\) on which the rule returns \(r\). For distinct \(r,g,b\), \(\delta _c\) counts the orderings of \((r,g,b)\) on which it returns \(c\); the rule is uniform if \(\delta _r = 2\) for all distinct triples. It is an \((s,\varepsilon )\)-solver if from every coloring whose unique plurality color \(m\) has bias at least \(s\), consensus on \(m\) is eventually reached with probability at least \(1-\varepsilon \).
Under a conservative rule a color without nodes never returns. Hence for all \(T, T_0\), the probability of consensus on \(m\) at time \(T\) is at most the probability that \(m\) has a node at time \(T_0\).
Let \(8 \mid n\). With only colors \(r, b\) present and \(x\) the fraction of \(r\), a node adopts \(r\) with probability \(p(x)\), where \(p(x) - x = x(1-x)\bigl(x(\Delta _r - 2) + (1-x)(2 - \Delta _b)\bigr)\). If \(\Delta _r \le 2 \le \Delta _b\), the number of \(r\) nodes is a supermartingale, so from \(5n/8\) nodes of \(r\) (bias \(n/4\)) consensus on \(r\) has probability at most \(5/8\) at every time: the rule is not an \((n/4, 1/4)\)-solver. Consequently, for an \((n/4, 1/4)\)-solver and every pair \(r \ne b\), either \(\Delta _r = \Delta _b = 3\) or \(\Delta _r, \Delta _b \le 1\).
\(\mathbb {E}[X_T] \le X_0\) by induction on \(T\), and \(\Pr (X_T = n) \le \mathbb {E}[X_T]/n\).
The paper claims that an \((n/4,1/4)\)-solver has the clear-majority property, i.e. that \(\Delta _r, \Delta _b \le 1\) is also impossible. Its proof uses the supermartingale property, but checks it only when red is the majority; for \(\Delta _r, \Delta _b \le 1\) it fails when red is the minority, because the process is pulled to the interior point \(x^* = (2 - \Delta _b)/(4 - \Delta _r - \Delta _b)\). That case is not formalized.
Let the rule be conservative with the clear-majority property, let only \(r, g, b\) be present and \(\delta _r \le 1\). Then \(p(r) \le 3x^2 - 2x^3 + \delta _r x_r x_g x_b \le x(3x - 2x^2 + (1-x)^2/4)\), which is at most \(0.97x\) for \(x \le 2/5\); and from \(x \le 2/5\) one round ends above \(2n/5\) with probability at most \(e^{-9n/31250}\).
Under the hypotheses of Lemma 46, starting with at most \(2n/5\) nodes of \(r\), the probability that \(r\) still has a node after \(T\) rounds is at most \(0.97^T c_r + T e^{-9n/31250}\).
Consider the chain frozen once \(r\) exceeds \(2n/5\). On it, \(\Phi = C_r\, \mathbb 1[C_r \le 2n/5]\) contracts by \(0.97\) in every state, it is frozen within \(T\) rounds with probability at most \(Te^{-9n/31250}\), and it agrees with the real chain until it is frozen.
Let \(60 \mid n\) and \(\log n \ge 20\). A rule with the clear-majority property that is an \((n/20, 1/4)\)-solver has the uniform property.
If a triple is not uniform, some color \(r\) of it has \(\delta _r \le 1\), since the three counts sum to \(6\). Start from \(23n/60\) nodes of \(r\), \(n/3\) of \(g\) and \(17n/60\) of \(b\): \(r\) is the unique plurality color with bias \(n/20\). By Lemmas 47 and 43, with \(T_0 = \lceil \log (8n)/\log (100/97)\rceil \), consensus on \(r\) has probability at most \(1/8 + 1/8\) at every time.
The paper’s proof (Lemma 4.10) is a sketch that treats \(\delta _r = 1\) with \((\delta _g,\delta _b) \in \{ (3,2),(4,1)\} \) and asserts that \(r\) “will not converge” by iterating a one-round estimate. The proof here covers every non-uniform triple and makes the iteration rigorous.
4.3 A lower bound for \(h\)-plurality
Every node samples \(h\) nodes and a uniformly random ordering \(\sigma \) of the \(h\) sample positions, and adopts the color of the position of smallest \(\sigma \)-rank among those whose color is most frequent. All tied colors appear equally often, so each is chosen with the same probability.
A node adopts \(j\) with probability at most \(x_j + \frac{h^2}{2}x_j^2\).
If \(j\) wins and is seen exactly once, all \(h\) sampled colors are distinct and \(j\) is at the position ranked first, which has probability \(x_j\). Otherwise \(j\) is seen at least twice, and \(\Pr (N_j \ge 2) \le \mathbb {E}[N_j(N_j-1)]/2 = \binom h2 x_j^2\).
If \(c_j \le a \le 2n/k\), then \(\Pr (C_{j,t+1} \ge a(1 + 2h^2/k)) \le \exp (-2(ah^2/k)^2/n)\), which is at most \(e^{-2nh^4/k^4}\) when \(a \ge n/k\).
Let \(k \ge 3\). If every color starts with at most \(\frac32\cdot \frac nk\) nodes and \(T \le \frac{k}{2h^2}\log \frac43\), then after \(T\) rounds of \(h\)-plurality the coloring is monochromatic with probability at most \(kT e^{-2nh^4/k^4}\).
As for Theorem 40, with thresholds \(\frac32\cdot \frac nk(1 + 2h^2/k)^t \le 2n/k\).
5 The two-opinion model
This section and the next ones, up to Section 13, give a complete, elementary proof that the 3-majority opinion-dynamics process on \(n\) fully-mixing agents, each holding one of two opinions, reaches consensus within \(O(\log n)\) rounds with probability \(1-O(1/n)\), provided the initial imbalance between the two opinions exceeds a fixed constant fraction of \(n\) (at least \(60\% \) vs. \(40\% \)). The probability space is finite and uniform throughout; the only analytic ingredient beyond finite sums is a single self-contained exponential-moment (Chernoff-type) concentration lemma for sums of independent \(\{ 0,1\} \)-valued random variables, proved from the elementary bound \(1+x \le e^x\): no measure theory, no PMF/kernels, no appeal to Mathlib’s probability library. This is a genuinely different regime from the companion push-protocol development (library RumorSpread of the epidemics package). The opinion-\(1\) count is not monotone in the round index (an unlucky round can shrink it), so a counting argument over “good rounds” does not suffice, and honest concentration around the process’s mean trajectory is needed in both the growth and saturation phases. This argument has been fully formalized (no sorry) in Lean 4 + Mathlib; the main theorem is ThreeMajority.majority3_consensus_whp.
Fix \(n \ge 1\) and let \(V = \{ 0,1,\dots ,n-1\} \) be the set of agents, each holding one of two opinions, \(1\) (“red”) or \(0\) (“blue”). Write \(I \subseteq V\) for the set of agents currently holding opinion \(1\).
A round configuration is a function \(r \colon V \to V \times V \times V\) assigning to every agent \(v\) an ordered triple of samples, each drawn independently and uniformly from \(V\), with replacement (an agent may sample itself, or the same agent twice; this is harmless, since a majority of three Boolean values is always well defined). Let \(R_n = V^{3V}\) denote the (finite) set of round configurations, with the uniform probability measure.
For an opinion-\(1\) set \(I \subseteq V\) and \(r \in R_n\),
Each agent independently samples \(3\) agents and adopts the majority of their current opinions.
Fix a horizon \(T \in \mathbb {N}\) and an initial set \(I_0 \subseteq V\). The sample space is \(\Omega = R_n^{\, T}\) with the uniform (i.i.d.) measure. For \(r = (r_0,\dots ,r_{T-1}) \in \Omega \) define \(I_{t+1} = \mathrm{step}(I_t, r_t)\). We write \(X_t = |I_t|\) and \(U_t = n - X_t\). In the formalization, a trajectory is a List of round configurations and \(\mathrm{run}\ I\ l\) folds step over the list \(l\).
For a fixed round \(r\), the map \(I \mapsto \mathrm{step}(I,r)\) is monotone: \(I \subseteq I'\) implies \(\mathrm{step}(I,r) \subseteq \mathrm{step}(I',r)\); iterating over a trajectory, \(\mathrm{run}\) is monotone in the same sense. This is purely combinatorial (no probability involved).
Unlike the push protocol, where the analogous monotonicity (Lemma 58 there) is load-bearing throughout, here the per-round probabilistic estimates below (Lemmas 79, 82, etc.) are instead stated and proved directly for any set \(I\) satisfying a hypothesis on \(|I|\), using monotonicity of the real polynomial \(p\) of Section 8 on \([0,1]\) rather than a reference-embedding argument via Lemma 58. Lemma 58 is recorded because it is the exact analogue of the push protocol’s structural fact, but it is not otherwise used by the chain of lemmas leading to the main theorem.
6 Two opinions from a 3/5 majority
Throughout, \(\log \) denotes the natural logarithm.
Let \(n\) be such that \(\log n \ge 30\) (in particular \(n \ge 2\)), let \(I_0 \subseteq V\) with \(|I_0| \ge \tfrac 35 n\), and set
Then \(\Pr [\, I_T = V \, ] \; \ge \; 1 - \dfrac {500}{n}\).
As in the push protocol’s write-up, the threshold \(\log n \ge 30\) and the constant \(500\) are deliberately crude: the proof is organized to keep every inequality an easy direct computation, not to be sharp. Reaching this modest, two-digit threshold on \(\log n\) (rather than an astronomically large one) relies on two ingredients in Section 9: a degree-\(11\) instance of the generic exponential-vs-power bound (Lemma 72), and a log-log bound tangent at a reference point near the threshold itself rather than at the fixed point \(e\) (Lemma 74). It is known (Doerr–Goldberg–Minder–Sauerwald–Scheideler 2011; Becchetti–Clementi–Natale–Pasquale–Silvestri, SODA 2015) that an initial imbalance of only \(\Theta (\sqrt{n\log n})\) already suffices for \(O(\log n)\)-round consensus w.h.p.; reaching that sharp threshold requires tracking the process on the scale of its own standard deviation throughout, a substantially more delicate multi-scale argument. Here a constant-fraction initial imbalance keeps every step to a single, reusable Chernoff bound (Section 10) applied at a handful of explicit parameters.
The proof has two phases, as in the push protocol, but for a structurally different reason: growth (Section 11), where the opinion-\(1\) fraction self-amplifies from \(60\% \) to \(75\% \); and saturation (Section 12), where the last dissenting agents are eliminated in three stages. Because the process is not monotone in the round index, both phases need the Chernoff bound of Section 10, unlike the push protocol, where only saturation needed a (much weaker) expectation argument.
7 Finite uniform probability and independence
As in the push protocol, all randomness is uniform over finite types, so instead of measure theory or PMF we work with plain finite sums.
For a finite type \(\alpha \) and \(f \colon \alpha \to \mathbb {R}\), \(\mathrm{avg}(f) := \bigl(\sum _a f(a)\bigr)/|\alpha |\) is the expectation of \(f\) under the uniform distribution on \(\alpha \).
Exactly as in the push protocol: \(\mathrm{expList}\ \alpha \ T\ F\) is the expectation of a functional \(F\) of a trajectory of \(T\) i.i.d. uniform draws from \(\alpha \), defined by recursion on \(T\) (the head draw is averaged out first), so conditioning on the first round is a definitional unfolding.
\(\mathrm{avg}\) and \(\mathrm{expList}\) are monotone, additive, homogeneous, and constants pass through unchanged; \(\mathrm{expList}\) over a concatenated horizon splits as a nested \(\mathrm{expList}\) (expList_append), used to glue phases in Section 13.
New relative to the push protocol, since that development only ever averaged over a single uniform draw at a time. For finite types \(\beta ,\delta \) and \(g \colon \beta \to \mathbb {R}\), \(h\colon \delta \to \mathbb {R}\): \(\mathrm{avg}(p \mapsto g(p_1)h(p_2)) = \mathrm{avg}(g)\, \mathrm{avg}(h)\) over the product \(\beta \times \delta \) (avg_mul_prod), with marginal consequences avg_fst_mul/avg_snd_mul. Iterating over a \(\mathrm{Fin}\ n\)-indexed product (avg_prod_pi): for \(f \colon \mathrm{Fin}\ n \to \gamma \to \mathbb {R}\),
over \(x \colon \mathrm{Fin}\ n \to \gamma \): the discrete, measure-theory-free form of “coordinate projections on a product space are independent,” with a one-coordinate marginal corollary (avg_eval). This is exactly the independence fact that lets the \(n\) agents’ per-round updates be combined into a single concentration bound (Section 10).
8 The majority map
Write \(x = X_t/n \in [0,1]\) for the opinion-\(1\) fraction, and \(\mathrm{ind}(I)\) for the real-valued membership indicator of \(I\), so \(\mathrm{avg}(\mathrm{ind}(I)) = |I|/n\).
For \(a,b,c \in \{ 0,1\} \): \(\mathbf1[a+b+c\ge 2] = ab+bc+ac-2abc\). Applied pointwise to the three samples of a fixed agent, this expresses the majority indicator as a polynomial in the three membership indicators.
\(Y_{\mathrm{maj}}(I,v,s) \in \{ 0,1\} \) is \(1\) iff a majority of the sample triple \(s\) lies in \(I\) (independent of \(v\), kept as a function of \(v\) to match the shape the Chernoff bound of Section 10 expects). Then \(|\mathrm{step}(I,r)| = \sum _v Y_{\mathrm{maj}}(I,v,r(v))\) (card_step_eq_sum): the per-agent, \(\{ 0,1\} \)-valued decomposition that Section 10’s tail bounds need.
Conditionally on a fixed \(I\) with \(|I|=m\), the next count \(X_{t+1} = |\mathrm{step}(I,r)|\) satisfies
proved exactly (no approximation) via Lemma 66, Definition 67 and the independence toolkit of Lemma 65 (each pairwise/triple product of membership indicators over distinct coordinates of the product space \(\mathrm{Tgt3}\ n\) factors by avg_mul_prod).
\(Y_{\mathrm{dis}} := 1 - Y_{\mathrm{maj}}\), the complementary per-agent dissent contribution, so \(n - |\mathrm{step}(I,r)| = \sum _v Y_{\mathrm{dis}}(I,v,r(v))\) with mean \(n - n\, p(x)\) (sum_avg_Y_dis); by the algebraic identity \(1-p(x) = (1-x)^2(1+2x)\) this is the quantity controlled in Section 12.
The algebraic identities for \(p\) used throughout below (\(p(x)-x = x(1-x)(2x-1)\), \(1-p(x) = (1-x)^2(1+2x)\), and the growth/saturation regional bounds \(p(\tfrac 12+\beta )-\tfrac 12 \ge \tfrac 54\beta \) for \(0\le \beta \le \tfrac 14\) and \(u(3-2u)\le \tfrac 58\) for \(0\le u\le \tfrac 14\)) are not isolated as separate Lean lemmas: each use site (growth_round, saturation_round_closed, saturation_mean_quad) re-derives the specific polynomial inequality it needs inline via ring/nlinarith, in the same spirit as the push protocol’s reverse-Markov bound, which is also not isolated as its own named lemma.
9 Elementary inequalities
For \(\tfrac 12 \le x \le 1\): \((x-1)-(x-1)^2 \le \log x\). (Mathlib’s crude linear bound \(\log x \ge x-1\) is false for \(x{\lt}1\) and, worse, plugging the correct one-sided bound \(1-\tfrac 1x\le \log x\) into the Chernoff exponent \(k-\mu -k\log (k/\mu )\) gives exactly \(0\) when \(k/\mu \to 1\), which is useless. This quadratic correction, derived from Mathlib’s degree-\(3\) Taylor lower bound for \(\exp \) by elementary algebra, is what makes the growth-phase Chernoff bound (Lemma 79) bite.)
For \(x\ge 0\) and any \(k\in \mathbb {N}\): \(x^k/k! \le \exp (x)\): the single degree-\(k\) term of the Taylor truncation, extracted by dropping every other (nonnegative, since \(x\ge 0\)) term of the sum. Choosing \(k\) large enough relative to a given lower bound on \(\log n\) lets \(n\) be shown to dominate any fixed polynomial in \(\log n\) using only a modest such lower bound (Stage 2b, Lemma 89, and the final numeric bound Lemma 94); a single low-degree truncation, such as the cubic case alone, would instead force \(\log n\) to be astronomically large.
For \(L{\gt}0\) and any reference point \(c{\gt}0\): \(\log L \le \log c - 1 + L/c\), from the crude bound \(\log t \le t - 1\) applied to \(t = L/c\); tight at \(L=c\) (equality there), unlike a bound tangent at a single globally-fixed point, so choosing \(c\) near the \(L\) actually in play gives a far sharper bound. Also records \(\exp (3)\ge 20\) (cubing the standard \(10\)-digit lower bound on \(e\)), used to instantiate \(c=\exp (3)\) below.
For \(\log x{\gt}0\): \(\log \log x \le 2 + (\log x)/20\), from Lemma 73 tangent at the reference point \(c=\exp (3)\approx 20.09\) (so \(\log c = 3\) exactly), combined with \(\exp (3)\ge 20\) to replace \(1/\exp (3)\) by the cruder but rational \(1/20\). Far tighter, once \(\log x\) is more than a few units above \(e\), than a bound tangent at the fixed point \(c=e\) (the crude bound \(\log t\le t-1\) applied directly at \(t=(\log x)/e\)), which is exactly the regime Lemma 89 needs. Used only inside Lemma 89’s numeric estimate.
10 An elementary Chernoff bound
The only concentration tool used in the whole development, and the only place beyond elementary combinatorics where real exponentials appear. These bounds are proved once in the shared dynamics library (Dynamics/Chernoff.lean, namespace Dynamics), which the plurality and median developments use as well.
Let \(Y_1,\dots ,Y_n \colon \gamma \to \{ 0,1\} \) be the per-agent contributions on the product space \(\mathrm{Fin}\ n \to \gamma \) (one independent draw of \(\gamma \) per agent), with \(\mu =\sum _i\mathrm{avg}(Y_i)\) and \(X(x) := \sum _i Y_i(x_i)\). Then for every real \(t\) (no sign restriction):
Proved via the independence toolkit (Lemma 65) applied to \(x \mapsto \prod _i \exp (tY_i(x_i))\), and the elementary bound \(1+y\le e^y\) (Mathlib’s Real.add_one_le_exp) at each factor.
In the setting of Lemma 75: for \(t\ge 0\) and any \(k\), \(\Pr [X\ge k] \le \exp (\mu (e^t-1)-tk)\) (avg_chernoff_upper_of_mgf, Markov applied to \(\exp (tX)\)); symmetrically for \(t\le 0\), \(\Pr [X\le k] \le \exp (\mu (e^t-1)-tk)\) (avg_chernoff_lower_of_mgf).
Plugging \(t=\log (k/\mu )\) into Lemma 76: for \(k\ge \mu {\gt}0\),
and symmetrically for \(0{\lt}k\le \mu \), \(\Pr [X\le k] \le \exp (k-\mu -k\log (k/\mu ))\). Both closed forms are mean-scaled: the exponent depends on the true \(\mu \) directly, not on a crude worst-case range/variance proxy, which matters late in the saturation phase once few at-risk agents remain (Lemma 89). The Lean statements are the generalized variants, which take only an upper bound \(\mu _{\mathrm{ub}}\ge \mu \) (avg_chernoff_upper_log, used by the saturation phase) or a lower bound \(\mu _{\mathrm{lb}}\le \mu \) (avg_chernoff_lower_log, used by the growth phase) on the true mean (the exact forms are the case of equality): monotonicity of the exponent in \(\mu \) at the optimal \(t\) makes both directions sound, and this is the form each phase actually needs, since the exact mean depends on \(x=|I|/n\) while the phases only assume an inequality on \(|I|\).
11 Two opinions: the growth phase
Set \(\beta _j = \tfrac 1{10}(1.1)^j\) for \(j=0,\dots ,10\); \(\beta _0=0.1\) (the hypothesis \(X_0\ge 0.6n\)) and \(\beta _{10}{\gt}0.25\).
\(\mathrm{growthBias}(j) := \tfrac 1{10}(\tfrac {11}{10})^j\), the deterministic bias target after \(j\) growth rounds; monotone, \(\le \tfrac 14\) for \(j\le 9\), and \({\gt}\tfrac 14\) at \(j=10\).
Starting from opinion-\(1\) fraction \(\ge \tfrac 12+\beta \) (\(\tfrac 1{10}\le \beta \le \tfrac 14\)), the probability of failing to reach the next bias target (guaranteed growth factor \(\tfrac {11}{10}\), comfortably below the true drift factor \(\tfrac 54\) from Lemma 68) is at most \(\exp (-n/10^7)\). Proved by computing a lower bound \(\mu _{\mathrm{lb}} = n(\tfrac 12+\tfrac 54\beta )\) on the true mean via monotonicity of \(p\) on \([\tfrac 12+\beta ,1]\) (an inline nlinarith computation, not a separate lemma), then applying the lower-tail bound avg_tail_le_log_ge at \(k=n(\tfrac 12+\tfrac {11}{10}\beta )\), and bounding the resulting exponent using Lemma 71.
Starting from bias \(\mathrm{growthBias}(i)\), after \(j\) further rounds (with \(i+j\le 10\)) the probability of failing to reach \(\mathrm{growthBias}(i+j)\) is at most \(j\exp (-n/10^7)\), by induction on \(j\) via the \(\mathrm{expList}\)-conditioning idiom (mirroring the push protocol’s Main.lean).
Starting from opinion-\(1\) fraction \(\ge \tfrac 35\), after \(10\) rounds the opinion-\(1\) fraction exceeds \(\tfrac 34\), except with probability \(\le 10\exp (-n/10^7)\).
12 Two opinions: the saturation phase
Write \(U_t = n-X_t\). By Lemma 81, \(U_{10}\le n/4\) except with probability \(\le 10\exp (-n/10^7)\). Getting \(U_t\) all the way to exactly \(0\) needs three stages, since a fixed-ratio Chernoff bound needs the mean itself to be \(\Omega (\log n)\) for a polynomially-small per-round failure probability.
Given a reference dissent bound \(U_t\le M\le n/4\) and any target \(k\ge \tfrac 58M\) (an upper bound \(\mu _{\mathrm{ub}}=\tfrac 58M\) on the true one-round mean, via \(1-p(x)=(1-x)^2(1+2x)\le \tfrac 58(1-x)\) for \(x\ge \tfrac 34\)), the probability the next dissent count exceeds \(k\) is at most \(\exp (k-\tfrac 58M-k\log (k/(\tfrac 58M)))\) (saturation_round_closed); the same conclusion holds for any directly-supplied upper bound \(\mu _{\mathrm{ub}}\) on the true mean (saturation_round_generic, used by Stage 2b where the quadratic estimate below is the tight one).
For any dissent bound \(U_t\le M\le n\), the true one-round mean is at most \(3M^2/n\) (the crude bound \(1-p(x)\le 3(1-x)^2\), dropping the \(\tfrac 58\) refinement). Used both by Stage 2b and by Stage 2c (at \(M=10\)).
Lemma 82’s exponent, simplified via Mathlib’s quadratic-tight Padé bound for \(\log \) (Real.le_log_one_add_of_nonneg) to the closed form \(-\lambda ^2/(k+\tfrac 58M)\), \(\lambda =k-\tfrac 58M\).
Guaranteed contraction factor \(0.7\) (vs. the true \(\tfrac 58\)): failure probability \(\le \exp (-M/250)\).
\(\mathrm{satAfter}(n,M,i) := \max (500\log n,\ (0.7)^i M)\), the target dissent bound after \(i\) Stage 2a rounds, clamped below at the floor \(500\log n\); written in closed form (not recursively) so shifts by one round agree definitionally on the unclamped branch.
Starting from a dissent bound \(M\) (\(500\log n\le M\le n/4\)), offset \(i\) rounds in, the probability the dissent count exceeds \(\mathrm{satAfter}(n,M,i+j)\) after \(j\) further rounds is at most \(j\, n^{-2}\), by induction on \(j\) via the same \(\mathrm{expList}\)- conditioning idiom as Lemma 80, with the tail direction flipped (dissent shrinking rather than opinion-\(1\) count growing).
With \(T_{2a}(n) := \left\lceil 6\log n \right\rceil \): starting from any dissent bound \(\le n/4\), after \(T_{2a}(n)\) rounds the dissent count exceeds the floor \(500\log n\) with probability at most \(T_{2a}(n)\cdot n^{-2}\).
Provided \(\log n\ge 30\): whenever \(U_t\le 500\log n\), \(\Pr [U_{t+1}{\gt}10] \le \exp (-\log n) = 1/n\). One round, jumping from the \(\Theta (\log n)\) floor directly to the fixed constant \(10\): since the mean is already tiny (\(\Theta ((\log n)^2/n)\)), this single round has an astronomically small failure probability once \(n\) is large enough to beat the relevant polynomial in \(\log n\), which a degree-\(11\) instance of Lemma 72, combined with the tighter tangent-line bound of Lemma 74, already secures at this modest threshold.
Whenever \(U_t\le 10\): \(\Pr [U_{t+1}\ge 1] \le 300/n\), via ordinary Markov applied to the nonnegative-integer \(U_{t+1}\) (\(\mathbb {E}[U_{t+1}]\le 300/n\) by Lemma 83 at \(M=10\)); no concentration is needed for the very last step.
13 Proof of the two-opinion theorem
\(T_{2a}(n)+2\) rounds, from \(U_t\le n/4\) to exactly \(U=0\), with total failure probability \(\le T_{2a}(n)\cdot n^{-2} + \exp (-\log n) + 300/n\).
For \(\log n\ge 30\) and \(|I_0|\ge \tfrac 35n\): over \(10+(T_{2a}(n)+2)\) rounds,
by gluing Lemma 81 (growth) to Lemma 92 (saturation), exactly as the push protocol’s prNotAllInformed_le glues its own two phases.
With \(T = 10+(T_{2a}(n)+2)\), Theorem 60 (majority3_consensus_whp) follows from Theorem 94 by \(\Pr [I_T=V] = 1-\Pr [I_T\ne V] \ge 1-500/n\).
14 3-Majority from any configuration in \(O(n^{3/4}\log ^{7/8} n)\) rounds
This section formalizes the upper bound for 3-Majority with any number of colours of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn and Natale, Ignore or comply? On breaking symmetry in consensus (PODC 2017) [ 3 ] : Theorem 4 of arXiv:1702.04921 (v1), with the comparison framework of its Section 2 and its Lemmas 2 to 4 (differences from the paper).
The second phase. The proof of Theorem 4 applies Theorem 3.1 of Becchetti, Clementi, Natale, Pasquale and Trevisan [ 4 ] , which is not part of [ 3 ] . Definition 108 states that result, Theorem 110 takes it as a hypothesis, exactly as the paper’s proof uses it, and Section 15 (roadmap MAJ-12 (a)) proves it (Theorem 125), so that Theorem 111, Theorem 4 of [ 3 ] , has no hypothesis.
14.1 Model and majorization
Agents \(V=\{ 0,\dots ,n-1\} \) hold colours in a finite set \(\Sigma \); a configuration is a map \(c\colon V\to \Sigma \), with \(c_a\) agents of colour \(a\) and \(\kappa (c)=|\{ a : c_a{\gt}0\} |\) remaining colours. Consensus is \(\kappa (c)\le 1\).
In a round of 3-Majority every agent draws an ordered sample triple \((s_1,s_2,s_3)\) uniformly with replacement (Definition 55); if \(s_2\) and \(s_3\) have the same colour it adopts that colour, otherwise the colour of \(s_1\). This is the only definition of the round with colours: at colours \([k]\) it is the 3-majority round of Definition 3. In a round of Voter every agent adopts the colour of one uniformly random agent (itself included).
The paper breaks a three-way tie by a uniformly random sample; since the samples are i.i.d., taking the first one gives the same law (Lemma 102).
With colours \(\{ 0,1\} \), a round of 3-Majority is the step of Definition 56. Renaming the colours by an injective map commutes with a round.
Case analysis on the colours of the three samples; the rule only compares colours.
For \(x,y\in \mathbb {R}^\Sigma \), \(x\succeq y\) if \(\sum x=\sum y\) and every sum of \(y\) over a set \(S\subseteq \Sigma \) is at most a sum of \(x\) over a set of the same size (equivalently, for every \(j\) the \(j\) largest entries of \(y\) sum to at most the \(j\) largest entries of \(x\)). An observable \(\varphi \) of configurations is Schur-convex if \((c_a)_a\succeq (c'_a)_a\) implies \(\varphi (c')\le \varphi (c)\).
If \((c_a)_a\succeq (c'_a)_a\) then \(\kappa (c)\le \kappa (c')\). Hence the indicator of \(\kappa (c)\le \kappa \) is Schur-convex.
The colours of \(c'\) carry all \(n\) agents, so a set of \(\kappa (c')\) colours carries all agents of \(c\).
14.2 Comparison of anonymous consensus processes
An anonymous consensus process with process function \(\alpha \) moves from \(c\) by letting every agent draw its new colour independently from the probability vector \(\alpha (c)\). The process \(\alpha \) dominates \(\alpha '\) if \(c\succeq c'\) implies \(\alpha (c)\succeq \alpha '(c')\).
If \(p\succeq q\) are probability vectors on \(\Sigma \) and \(\varphi \) is Schur-convex, the expectation of \(\varphi \) when the \(n\) agents draw their colours i.i.d. from \(q\) is at most the expectation when they draw from \(p\).
The paper cites this result without proof. For one Robin Hood transfer between colours \(a\) and \(b\), the expectation, as a function of the mass \(\theta \) of \(a\) (with \(a\) and \(b\) sharing a fixed total \(s\)), is nondecreasing on \([s/2,s]\): its derivative is a sum over agents, and swapping \(a\) and \(b\) for all agents and then for one agent pairs its terms into products of two factors with the same sign. A chain of transfers (the Hardy–Littlewood–Pólya construction) leads from \(p\) to \(q\) when \(q\) is sorted and the partial sums of \(p\) dominate those of \(q\); sorting and relabelling the colours, under which Schur-convex observables are invariant, reduce the general case to this one.
If \(\alpha \) dominates \(\alpha '\) and \(c\succeq c'\), then for every Schur-convex \(\varphi \) and every \(T\), \(\mathbb {E}_{c'}[\varphi (P'_T)]\le \mathbb {E}_c[\varphi (P_T)]\). In particular, from the same configuration, the dominating process has at most \(\kappa \) colours at time \(T\) with at least the probability of the dominated one.
Induction on \(T\). With \(u_T\), \(v_T\) the expectations at time \(T\) for the dominated and the dominating process, \(w(y)=\max \{ u_T(z):z\preceq y\} \) is Schur-convex and \(u_T\le w\le v_T\) on comparable configurations, so Proposition 100 applied to \(w\) gives the step from \(T\) to \(T+1\). The second statement is the case of the indicator of Lemma 98. The paper’s coupling (Lemma 1, from Strassen’s theorem) is not needed.
14.3 3-Majority is at least as fast as Voter
Both processes are AC-processes. With \(x=c/n\), Voter has \(\alpha ^V_a(c)=x_a\) and 3-Majority has \(\alpha ^{3M}_a(c)=x_a(1+x_a-\| x\| _2^2)\).
The agents’ samples are independent. For 3-Majority, \([\mathrm{maj}=a]=[x_2=a][x_3=a]+[x_1=a]-[x_2=x_3][x_1=a]\), and the number of pairs of agents of equal colour is \(\sum _b c_b^2\).
3-Majority dominates Voter. Hence, from the same configuration, after \(T\) rounds 3-Majority has at most \(\kappa \) colours with at least the probability that Voter has.
For a set \(S\) of the largest entries of \(x\), \(\| x\| _2^2\sum _S x\le \sum _S x^2\), since \(\sum _{i\in S}\sum _j x_ix_j(x_i-x_j)\ge 0\); this gives \(\alpha ^{3M}(c)\succeq \alpha ^V(c)\), and with \(c\succeq c'\) also \(\alpha ^{3M}(c)\succeq \alpha ^V(c')\). Conclude with Theorem 101.
14.4 The Voter bound
Let coalescing random walks start on all \(n\) nodes of the complete graph with self-loops. After \(T\) rounds, Voter has more than \(k\) colours with at most the probability that more than \(k\) walks remain.
Pathwise, the colours of Voter after rounds \(y_1,\dots ,y_T\) are colours of the nodes occupied by the walks moved by \(y_T,\dots ,y_1\); the rounds are i.i.d., so reversing their order does not change the law. The paper proves an equality under a coupling and uses only this inequality.
If \(X_t\) walks remain, \(\mathbb {E}[X_{t+1}\mid X_t=x]\le x-x(x-1)/(3n)\) for every \(x\), hence \(\le x-x^2/(10n)\) for \(x\ge 2\) (Equation (7)). From any set of walks, \(\mathbb {E}X_t\le 1+3n/t\) for \(t\ge 1\).
\(\mathbb {E}[X_{t+1}\mid X_t=x]=n(1-(1-1/n)^x)\), the expected number of occupied cells when \(x\) balls go into \(n\) cells; bound \((1-1/n)^x\) by the Bonferroni inequality of degree 3. The map \(x\mapsto x-x(x-1)/(3n)\) is concave and nondecreasing on \([0,n+1]\), so its tangent-line bound and induction on \(t\) give \(\mathbb {E}X_t\le 1+3n/t\). This replaces the paper’s variable drift argument for \(\mathbb {E}[T^k_C]\le 20n/k\).
For \(n\ge 2\), \(k\ge 1\) and \(T\ge 24(n/k)\log n\), from any configuration Voter has more than \(k\) colours after \(T\) rounds with probability at most \(1/n\).
Blocks of \(\lceil 6n/k\rceil \) rounds: by Markov’s inequality on \(X-1\) (the walks never vanish), each block leaves more than \(k\) walks with probability at most \(1/2\), from any start. Restart over \(\lfloor T/\lceil 6n/k\rceil \rfloor \ge \log _2 n\) blocks (for \(k{\lt}n\); for \(k\ge n\) there is nothing to prove) and use Lemma 104.
14.5 The main theorem
For \(n\ge 2\), \(k\ge 1\) and \(T\ge 24(n/k)\log n\), from any configuration 3-Majority has more than \(k\) colours after \(T\) rounds with probability at most \(1/n\).
For \(\varepsilon {\gt}0\), \(\mathrm{Phase2}(\varepsilon )\) is the proposition (Theorem 3.1 of [ 4 ] , Theorem 8 of [ 3 ] ): there are \(C,N\) such that for \(n\ge N\), from any configuration with colours in \(\{ 0,\dots ,n-1\} \) and \(k\le n^{1/3-\varepsilon }\) colours, 3-Majority has not reached consensus after any \(T\ge C(k^2\sqrt{\log n}+k\log n)(k+\log n)\) rounds with probability at most \(1/n\). This proposition is a hypothesis of Theorem 110; Theorem 125 proves it for every \(\varepsilon {\gt}0\) (Section 15). The cited paper’s “w.h.p.” is \(1-O(n^{-\lambda })\) for some \(\lambda {\gt}0\), which gives the form \(1/n\) by repeating the phase a constant number of times; the proof of Theorem 125 gives the form \(1/n\) directly.
For every \(A\ge 0\) there are \(C,N\) such that for \(n\ge N\) and \(k=\lfloor n^{1/4}\log ^{1/8}n\rfloor \): \(n\ge 2\), \(1\le k\le n^{1/3-1/24}\), and \(24(n/k)\log n+1+A(k^2\sqrt{\log n}+k\log n)(k+\log n)\le Cn^{3/4}\log ^{7/8}n\).
From \(\log y\le y^{1/4}\) and \(\log ^{1/8}y\le y^{1/24}\) for \(y\) large.
Assume \(\mathrm{Phase2}(1/24)\). There are \(C,N\) such that for \(n\ge N\), from any configuration with colours in \(\{ 0,\dots ,n-1\} \), 3-Majority has not reached consensus after any \(T\ge Cn^{3/4}\log ^{7/8}n\) rounds with probability at most \(2/n\).
Let \(k=\lfloor n^{1/4}\log ^{1/8}n\rfloor \) and \(T_1=\lceil 24(n/k)\log n\rceil \). After \(T_1\) rounds, more than \(k\) colours remain with probability at most \(1/n\) (Lemma 107); otherwise the current configuration has at most \(k\le n^{1/3-1/24}\) colours, and \(\mathrm{Phase2}(1/24)\) bounds the failure of the remaining \(T-T_1\) rounds by \(1/n\). Lemma 109 fits both phases in \(Cn^{3/4}\log ^{7/8}n\) rounds. The proof in the paper needs a minor correction: it applies Lemma 3 with \(k=n^{1/4}\), which gives \(O(n^{3/4}\log n)\) rounds for Phase 1; the choice \(k=n^{1/4}\log ^{1/8}n\) balances the two phases and gives the bound as stated.
There are \(C,N\) such that for \(n\ge N\), from any configuration with colours in \(\{ 0,\dots ,n-1\} \), 3-Majority has not reached consensus after any \(T\ge Cn^{3/4}\log ^{7/8}n\) rounds with probability at most \(2/n\).
15 3-Majority with many opinions
This section formalizes the adversary-free case of Becchetti, Clementi, Natale, Pasquale and Trevisan, Stabilizing consensus with many opinions (SODA 2016) [ 4 ] : its Theorem 3.1, with its Lemmas 2.1 and 3.2 to 3.5 and Lemma B.1, in the numbering of arXiv:1508.06782 (v1). The differences from the paper are listed in the repository. Theorem 3.1 is the proposition \(\mathrm{Phase2}(\varepsilon )\) of Definition 108 (Theorem 125), so it makes Theorem 4 of [ 3 ] unconditional (Theorem 111).
The process is the 3-Majority of Definition 95, whose rule is, pointwise, the rule of the paper (three samples uniform with repetition; on three different colours, the first one), with colours in \(\{ 0,\dots ,n-1\} \). We write \(c_a\) for the support of colour \(a\), \(C'_a\) for its support after one round, \(j\) or \(k\) for the number of colours, and \(m=16\sqrt{jn\log n}\). Where the paper assumes \(j\le n^{1/3-\varepsilon }\), the statements below assume \(Cj^3\log n\le n\) for a constant \(C\), which is what the proofs use; it holds for \(j\le n^{1/3-\varepsilon }\) and \(n\) large. The proofs follow the paper’s, with the deviations and the minor corrections noted in each proof.
15.1 One round
For any finite set of colours, any configuration \(c\) and any colour \(a\),
\(C'_a\) is the sum over the agents of independent indicators of adopting \(a\), each with mean \(x_a(1+x_a-\| x\| _2^2)\) for \(x=c/n\) (as in Lemma 102). The inequality is the Cauchy–Schwarz bound \(\sum _b c_b^2\ge n^2/\kappa (c)\).
Let \(\sigma _a^2\) be the sum of the variances of the agents’ indicators of adopting \(a\).
If \(\mathbb {E}[C'_a]\le \mu {\lt}k\), then \(\Pr (C'_a\ge k)\le \exp (-(k-\mu )^2/(k+\mu ))\); if \(0{\lt}k{\lt}\mu \le \mathbb {E}[C'_a]\), then \(\Pr (C'_a\le k)\le \exp (-(\mu -k)^2/(2\mu ))\).
If \(\sigma _a^2\ge 1\), then \(\mathbb {E}|C'_a-\theta |\ge (9/256)\, \sigma _a\) for every \(\theta \in \mathbb {R}\).
If \(c\) has \(j\ge 2\) colours, all with more than \(n/j-nu\) agents, where \(u\ge 0\) and \(ju\le 1/250\), then \(\sigma _a^2\ge n/(4j)\) for every colour \(a\) of \(c\).
(1) The Chernoff bounds of Section 10 for a sum of independent indicators. (2) If \(|\mathbb {E}[C'_a]-\theta |\ge \sigma _a/4\), this is Jensen’s inequality. Otherwise, by the Paley–Zygmund inequality (from the second and fourth moments of a sum of independent centred \(\{ 0,1\} \)-coordinates) the centred sum \(S\) satisfies \(\sigma _a^2\le 4S^2\) with probability at least \(9/64\), and there \(|C'_a-\theta |\ge \sigma _a/2-\sigma _a/4\). (3) The adoption probability \(p\) of Lemma 112 lies between \((1-1/250)^2/j\) and \((1/2+1/250)(1+1/250)\), and \(\sigma _a^2=np(1-p)\).
15.2 Hitting times under a drift
Let \(K\) be a Markov kernel on a finite set, \(I\) a set with \(K(x,I)=1\) for \(x\in I\), \(B\) a target set with hitting time \(\tau \), and \(f\) a real function. Let \(\beta ,\eta \ge 0\), and assume that \(f(x)\le M\) for \(x\in I\) and that, for \(x\in I\setminus B\), \(f(x)\le \beta \), \(\mathbb {E}[f(X_1)\mid X_0=x]\ge f(x)+\lambda \) and \(\Pr (f(X_1){\gt}\beta \mid X_0=x)\le \eta \). Then for every \(a\in I\) with \(f(a)\ge 0\) and every \(t\), \(\lambda t\Pr _a(\tau {\gt}t)\le \beta +M\eta t\).
Let \(X'\) be the chain stopped at \(B\). Summing the drift over the steps before \(\tau \), \(\mathbb {E}_a[f(X'_t)]\ge f(a)+\lambda \mathbb {E}_a[\min (t,\tau )]\ge \lambda t\Pr _a(\tau {\gt}t)\). By a union bound over the steps, \(f(X'_t){\gt}\beta \) with probability at most \(\eta t\), and \(f\le M\), so \(\mathbb {E}_a[f(X'_t)]\le \beta +M\eta t\). The paper bounds \(\mathbb {E}[\tau ]\) by optional stopping, under a hypothesis on the overshoot at time \(\tau \) (Lemma B.1); the finite horizon and the one-step overshoot bound avoid both.
Let \(P\) be an absorbing set for \(K\). If from every state of \(B\) the chain is in \(P\) after \(s\) steps with probability at least \(q\), then from every state \(a\) it is in \(P\) at time \(t+s\) with probability at least \(q\Pr _a(\tau \le t)\).
The strong Markov property at \(\tau \), proved by induction on \(t\) without stopping times: from a state of \(B\), the hypothesis and absorption; otherwise, condition on the first step.
15.3 Symmetry breaking
A configuration \(x\) has broken symmetry for \(j\) colours if \(\kappa (x){\lt}j\), or \(\kappa (x)\le j\) and some colour has between \(1\) and \(n/j-16\sqrt{jn\log n}\) agents.
The paper’s threshold is \(n/j-\sqrt{jn\log n}\); the factor \(16\) is needed in Lemma 120. The death of a colour also breaks the symmetry (the paper’s minimum is over the initial colours, so a dead colour has support \(0\)).
There are \(\delta {\gt}0\) and \(C\) such that, for every configuration \(x\) with \(j=\kappa (x)\ge 2\) colours, \(Cj^3\log n\le n\) and every colour of \(x\) above \(n/j-m\) agents, the smallest support among the colours of \(x\) (a colour that dies counting \(0\)) decreases in expectation by at least \(\delta \sqrt n/(j\sqrt j)\) in one round.
Take \(\delta =1/500\), \(C=1024\) and \(w=\sqrt{n/j}\). If the smallest support \(c_{\min }\) is at most \(n/j-w/250\), Lemma 112 for a smallest colour, with \(c_{\min }\ge n/(2j)\) (Equation (5)), gives the drift. Otherwise all colours are above \(n/j-w/250\). The supports sum to \(n\), so the smallest new support is at most \(n/j-\frac1{2j}\sum _a|C'_a-n/j|\), and \(\mathbb {E}|C'_a-n/j|\ge (9/256)\sigma _a\ge (9/512)w\) by Lemma 113; hence the expected smallest new support is at most \(n/j-9w/1024{\lt}c_{\min }-w/1000\). The paper argues in this case with the Central Limit Theorem and negative association instead.
There is \(C\) such that, under the hypotheses of Lemma 117, one round puts some colour of \(x\) below \(n/j-64\sqrt{jn\log n}\) agents with probability at most \(1/n^2\).
Take \(C=2^{14}\). Every support is at most \(n/j+(j-1)m\), so by Lemma 112 every colour of \(x\) has \(\mathbb {E}[C'_a]\ge n/j-2m\). The Chernoff lower tail at \(n/j-4m\) (Lemma 113) and a union bound over the at most \(n\) colours give \(1/n^2\). The paper bounds the overshoot at the hitting time instead (Lemma B.1); its proof needs a minor correction, since it treats the smallest support as a Markov chain, while it is a function of the configuration. The one-step form avoids this argument.
There is \(C\) such that, from every configuration \(c\) with \(j\ge 2\) colours and \(Cj^3\log n\le n\), 3-Majority reaches broken symmetry for \(j\) colours within any \(t\ge Cj^2\sqrt{\log n}\) rounds with probability at least \(1/2\).
Lemma 114 with \(I=\{ \kappa \le j\} \), \(B\) the configurations with broken symmetry, \(f=n/j\) minus the smallest support among the \(j\) colours (the paper’s \(Y_t\)), \(\lambda =\delta \sqrt n/(j\sqrt j)\) (Lemma 117), \(\beta =64\sqrt{jn\log n}\) and \(\eta =1/n^2\) (Lemma 118), and \(M=n/j\). For \(t\ge Cj^2\sqrt{\log n}\) (the proof takes \(C=145\, 409\)), \(\lambda t\ge 4\beta \) and \(M\eta t\le \lambda t/4\), so \(\Pr (\tau {\gt}t)\le 1/2\).
The paper states the conclusion at the fixed time \(t\), while its proof bounds the hitting time, which is what is stated here; its composition in Theorem 3.1 needs a minor correction, the strong Markov property at the hitting time (Lemma 115). The statement also needs a minor correction: it needs the hypothesis \(j^3\log n=O(n)\), as do the paper’s Lemmas 3.4 and 3.5 (otherwise the threshold \(n/j-\sqrt{jn\log n}\) is negative and the event has probability \(0\)). Finally, its bound \(\mathbb {E}[\tau ]{\lt}j^2\sqrt{\log n}\) should read \(\mathbb {E}[\tau ]\le (2\alpha /\varepsilon )j^2\sqrt{\log n}\).
15.4 Dropping
There is \(C\) such that, for \(j\ge 2\) with \(Cj^3\log n\le n\), from every configuration with at most \(j\) colours and every colour \(a\) with at most \(n/j-16\sqrt{jn\log n}\) agents, at every time \(t\) with \(Cj\log n\le t\le n\) colour \(a\) has more than \(Cj^2\log n\) agents with probability at most \(1/n\).
Take \(C=240\). As in Appendix B of the paper, the gap \(n/j-c_a\) grows by a factor \(1+1/(4j)\) per round until \(c_a\le n/(2j)\), and then \(c_a\) shrinks by a factor \(1-1/(4j)\) per round down to a floor. Here both stages are one moving level, \(\max \{ n/j-m(1+1/(4j))^s,\ (n/(2j))(1-1/(4j))^{s-s_A},\ K\} \) at round \(s\), with \(K=\min \{ 240j^2\log n,n/(2j)\} \) and \(s_A=\lceil 5j\log n\rceil \). By Lemma 112 and the Chernoff upper tail (Lemma 113), \(c_a\) exceeds the level of the next round with probability at most \(1/n^2\); after \(s_A+\lceil 4j\log n\rceil \le 240j\log n\) rounds the level is \(K\), and a union bound over the \(t\le n\) rounds gives \(1/n\).
The proof in the paper needs a minor correction. At its threshold \(n/j-\sqrt{jn\log n}\), and again near its floor \(j^2\log n\), the one-round bound of its Equation (7) is only about \(n^{-1/12}\), and the union bound over the rounds exceeds \(1\) for large \(j\) (for instance \(j\ge 20n^{1/10}\), which \(j\le n^{1/3-\varepsilon }\) allows). The threshold \(16\sqrt{jn\log n}\), which Lemma 119 reaches within the same \(O(j^2\sqrt{\log n})\) rounds, and the floor \(240j^2\log n\) make each round fail with probability at most \(1/n^2\).
There is \(C\) such that, for \(j\ge 2\) with \(Cj^3\log n\le n\), from every configuration with at most \(j\) colours and every colour \(a\) with at most \(n/(2j)\) agents, colour \(a\) has died after any \(t\ge Cj\log n\) rounds with probability at least \(1/2\).
Take \(C=1024\). As in the paper’s sketch, with the potential \(\psi =\min \{ c_a,n/(2j)\} \): Lemma 112 gives \(\mathbb {E}[\psi ']\le (1-1/(2j))\psi +(n/(4j^2))[c_a{\gt}n/(2j)]\), and by the Chernoff upper tail \(c_a\) escapes above \(n/(2j)\) with probability at most \(1/n^4\) per round. Hence \(\mathbb {E}[\psi _s]\le (1-1/(2j))^s\, n/(2j)+(n/(4j^2))\, n^{-4}s^2\), which is at most \(1/2\) at \(s=\lceil 2j\log n\rceil \), and Markov’s inequality gives \(\Pr (c_a\ge 1)\le 1/2\). Later times follow since a dead colour stays dead.
15.5 Consensus
There is \(C\) such that, from every configuration with \(j\ge 2\) colours and \(Cj^3\log n\le n\), after any \(t\ge C(j^2\sqrt{\log n}+j\log n)\) rounds fewer than \(j\) colours remain with probability at least \(1/5\).
From a configuration with broken symmetry, either fewer than \(j\) colours remain, or a colour has at most \(n/j-16\sqrt{jn\log n}\) agents; then Lemma 120 brings it to at most \(240j^2\log n\le n/(2j)\) agents except with probability \(1/n\), and Lemma 121 kills it with probability at least \(1/2\): in total at least \(\frac12(1-\frac1n)\ge \frac25\). Fewer than \(j\) colours is absorbing, so Lemma 115 at the hitting time of broken symmetry and Lemma 119 give \(\frac12\cdot \frac25=\frac15\) (the proof takes \(C=293\, 349\)). The paper’s proof of Theorem 3.1 needs a minor correction here: its probability \(1/4\) ignores the failure probability of Lemma 3.4; any positive constant suffices.
If from every configuration with between \(2\) and \(k\) colours a phase of \(L\) rounds removes a colour with probability at least \(p\le 1\), then from every configuration with at most \(k\) colours consensus fails after \(M\) phases with probability at most \((1-p/2)^M2^k\).
The potential equal to \(2^{\kappa }\) without consensus and to \(0\) at consensus: colours never increase, and with probability at least \(p\) one of them disappears, so over one phase its expectation is multiplied by at most \((1-p)+p/2=1-p/2\). This makes precise the paper’s “standard probabilistic arguments”.
There is \(C\) such that, from every configuration with \(k\) colours and \(Ck^3\log n\le n\), 3-Majority has not reached consensus after any \(T\ge C(k^2\sqrt{\log n}+k\log n)(k+\log n)\) rounds with probability at most \(1/n\).
Phases of \(L=\lceil C_1(k^2\sqrt{\log n}+k\log n)\rceil \) rounds, with \(C_1\) the constant of Lemma 122, which applies to every configuration with \(2\le j\le k\) colours. By Lemma 123 with \(p=1/5\) and \(M=10(k+\lceil \log n\rceil )\) phases, consensus fails after \(ML\) rounds with probability at most \((9/10)^M2^k\le 1/n\), and consensus is absorbing. The proof takes \(C=15(C_1+1)=4\, 400\, 250\).
For every \(\varepsilon {\gt}0\), \(\mathrm{Phase2}(\varepsilon )\) holds: there are \(C,N\) such that for \(n\ge N\), from every configuration with colours in \(\{ 0,\dots ,n-1\} \) and \(k\le n^{1/3-\varepsilon }\) colours, 3-Majority has not reached consensus after any \(T\ge C(k^2\sqrt{\log n}+k\log n)(k+\log n)\) rounds with probability at most \(1/n\).
Theorem 124 with the same \(C\): \(k^3\le n^{1-3\varepsilon }\) and \(|C|\log n\le n^{3\varepsilon }\) for \(n\ge N\), so \(Ck^3\log n\le n\).
With \(\varepsilon =1/24\), Theorem 125 is the hypothesis of Theorem 110, which gives Theorem 111.
16 The Lean library ThreeMajority
Sections 5 to 15 are fully formalized (no sorry) in the library ThreeMajority of this package (namespace ThreeMajority). File structure (dependency order): Prob.lean (Section 7: aliases of the finite-uniform avg/expList machinery of the shared dynamics library, including the independence toolkit avg_prod_pi and friends), Model.lean (Section 5), Bounds.lean (Section 9), the shared Dynamics/Chernoff.lean (Section 10), OneRound.lean (Section 8), Growth.lean (Section 11), Saturation.lean (Section 12), Main.lean (Section 13 and the main theorem). The files AnyStartModel, AnyStartMajorization, AnyStartRinott, AnyStartComparison, AnyStartVsVoter, AnyStartVoter, AnyStartAsymptotics and AnyStartMain formalize Section 14, on the shared finite Distribution and Kernel layer of dynamics; the files ManyOpinionsExpect, ManyOpinionsDrift, ManyOpinionsTails, ManyOpinionsBreaking, ManyOpinionsDropping and ManyOpinionsMain formalize Section 15, with the moment bounds of Moments in dynamics. Design constraint preserved from the push-protocol development (library RumorSpread of the epidemics package): no measure theory, no PMF/ENNReal, no Mathlib ProbabilityTheory kernels: everything is finite sums, plus Real.exp/Real.log where the Chernoff bound genuinely needs them (structurally central here, unlike the push protocol, where Real.exp appears only in a numeric side lemma).
- 1
B. Doerr, L.A. Goldberg, L. Minder, T. Sauerwald, C. Scheideler. Stabilizing consensus with the power of two choices. SPAA 2011.
- 2
L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri. Plurality consensus in the gossip model. SODA 2015.
- 3
P. Berenbrink, A. Clementi, R. Elsässer, P. Kling, F. Mallmann-Trenn, E. Natale. Ignore or comply? On breaking symmetry in consensus. PODC 2017. arXiv:1702.04921.
- 4
L. Becchetti, A. Clementi, E. Natale, F. Pasquale, L. Trevisan. Stabilizing consensus with many opinions. SODA 2016. arXiv:1508.06782.