- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
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\).
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.
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\).
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')\).
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)\).
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).
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 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.
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]\).
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\).
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.
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 \).
\(\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\).
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.
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.
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.
\(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.
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\).
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 \(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)\).
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.
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.
\(\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.
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.
\(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.
\(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.
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\).
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)\).
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\)
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\).
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\).
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 \(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 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\).
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 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\).
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)\).
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\).
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.
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.
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.
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\).
\(\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.
- ThreeMajority.avg_nonneg
- ThreeMajority.avg_le_avg
- ThreeMajority.avg_add
- ThreeMajority.avg_sub
- ThreeMajority.avg_const_mul
- ThreeMajority.avg_sum
- ThreeMajority.avg_indicator
- ThreeMajority.avg_const
- ThreeMajority.expList_nonneg
- ThreeMajority.expList_le_expList
- ThreeMajority.expList_add
- ThreeMajority.expList_const_mul
- ThreeMajority.expList_const
- ThreeMajority.expList_append
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)\).
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|\).
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.
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).
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\).
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.
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}\).
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 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.
A node adopts \(j\) with probability at most \(x_j + \frac{h^2}{2}x_j^2\).
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 \).
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).
If \(n \ge 5\) and \(|s| \le 4\sqrt n/25\), then \(|s'| \ge \sqrt n/5\) with probability at least \(9/64\).
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.
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 \(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 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.
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.
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.
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\).
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\).
For any finite set of colours, any configuration \(c\) and any colour \(a\),
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.
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\).
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\).
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\).
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\).
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).
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\).
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\).
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).
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.
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).
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\).
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\).
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}\).
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\).
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\).
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.
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\).
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.
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\).
With \(k = 2\) the set of nodes of color \(1\) evolves exactly as the binary 3-majority process of Section 5 (Lemma 96, with the colors renamed). Hence, if \(c_1 \ge \frac35 n\) and \(\log n \ge 30\), all nodes support color \(1\) after \(O(\log n)\) rounds with probability at least \(1 - 500/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.
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}\).
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\).
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\).
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\).