The Undecided-State Dynamics
1 The model
Each of \(n\) nodes holds opinion \(a\), opinion \(b\), or is undecided. In a round every node samples a node uniformly at random (with replacement, possibly itself): an undecided node adopts the sampled opinion, and a decided node that samples the other opinion becomes undecided. We write \(a\), \(b\), \(q\) for the numbers of \(a\)-, \(b\)- and undecided nodes.
2 One round in expectation
The state of a node after a round depends only on the node it samples, which is uniform; so an \(a\)-node stays \(a\) with probability \(1-b/n\) and an undecided node becomes \(a\) with probability \(a/n\).
The average over all sampling functions of a function of one coordinate is the uniform average.
After one round, the expected numbers of \(a\)-, \(b\)- and undecided nodes are \(a(n-b+q)/n\), \(b(n-a+q)/n\) and \((q^2+2ab)/n\); hence the expected bias is \((a-b)(1+q/n)\).
Sum Lemma 2 over the nodes; \(a(n-b+q)-b(n-a+q)=(a-b)(n+q)\).
3 Absorption
Monochromatic configurations are fixed points, and from every configuration the probability of not being monochromatic after \(t\) rounds tends to \(0\).
If some node \(w\) is decided, the round in which everybody samples \(w\), repeated twice, makes the configuration monochromatic; it has positive probability. Conclude with the shared absorption theorem.
4 The majority phase (UND-1)
Becchetti, Clementi, Natale, Pasquale and Silvestri (Plurality consensus in the gossip model, SODA 2015, Theorem 11 with \(k=2\)) prove convergence to the majority in \(O(\log n)\) rounds w.h.p. from configurations without undecided nodes and with a bias of order \(n\). The stronger form below, from any configuration with bias \(\Omega (\sqrt{n\log n})\), is Theorem 3.2 of Clementi, Ghaffari, Gualà, Natale, Pasquale and Scornavacca (MFCS 2018). Write \(s=a-b\) for the bias, \(\Lambda =\sqrt{n\log n}\), and call a round good if the new counts of \(a\)-, \(b\)- and undecided nodes are within \(\Lambda \) of their expectations (from below for \(a\), from above for \(b\), both ways for the undecided nodes).
A round is bad with probability at most \(4e^{-2\Lambda ^2/n}=4/n^2\).
Each count after the round is a sum of independent indicators, one per node, depending only on the node it samples; apply Hoeffding’s inequality to the four tails.
After a good round, \(s'{\gt}s(1+q/n)-2\Lambda \) and \(q'{\gt}n/3-s^2/(2n)-\Lambda \). If \(b+2q\le 2n/3\) and \(q\le n/3\), the potential \(\Psi =12b+q\) satisfies \(\mathbb E[\Psi ']\le \frac56\Psi \), hence \(\Psi '{\lt}\frac56\Psi +13\Lambda \) after a good round.
\(a(n-b+q)-b(n-a+q)=(a-b)(n+q)\); \((q^2+2ab)/n-n/3+s^2/(2n)=3(q-n/3)^2/(2n)\); and \(12b(b+2q)+q^2+2ab\le 8bn+qn/3+2bn\).
Let \(2000\Lambda \le n\) and \(p=4/n^2\). (Growth) From \(s\ge 402\Lambda \), after \(T+1\) rounds \(s\ge \min (400\Lambda (201/200)^T,7n/10)\) except with probability \((T+1)p\). (Bridge) From \(s\ge 7n/10\), after \(18\) rounds \(\Psi \le n/3\) except with probability \(18p\). (Final) From \(\Psi \le n/3\), not all nodes hold \(a\) after \(T\) rounds with probability at most \((5/6)^T\Psi +Tp\).
Growth: the sets \(\{ s\ge g,\ (q\ge n/100\text{ or }s\ge g+n/20)\} \) are entered with \(g=400\Lambda \) after one good round and \(g\) grows by \(201/200\) per good round (if \(s\le 4n/5\) then \(q'\ge n/100\)); union bound over rounds with moving targets. Bridge: while \(s\ge 2n/3\), \(\Psi \) shrinks by \(9/10\) per good round and \(s\) loses at most \(2\Lambda \). Final: induction on \(T\), splitting on whether the first round stays in \(\{ \Psi \le n/3\} \); and \(\Psi \ge 1\) unless all nodes hold \(a\).
Let \(C=10^4\). For every \(n\) with \(\log n\ge C\) and every configuration (any number of undecided nodes) with \(|a-b|\ge C\sqrt{n\log n}\), all nodes hold the initial majority opinion after \(\lceil C\log n\rceil \) rounds with probability at least \(1-2/n\). Without undecided nodes and with \(a\ge (1+\alpha )b\), the same holds with a constant depending on \(\alpha \) (SODA 2015, Theorem 11 for two colours).
Run \(T_1+1\) growth rounds with \(T_1=\lceil \log n/\log (201/200)\rceil \), \(18\) bridge rounds and the remaining \(T_3\ge 12\log n\) final rounds, so that \((5/6)^{T_3}\le n^{-2}\); the failure probability is at most \(\lceil C\log n\rceil p+n^{-2}\cdot n/3\le 2/n\). A \(b\)-majority follows by exchanging the opinions. With \(a\ge (1+\alpha )b\) and \(q=0\) the bias is at least \(\alpha n/(2+\alpha )\), which exceeds \(C\sqrt{n\log n}\) once \(\log n\ge C(1+3(2+\alpha )/\alpha )\); extra rounds do not hurt since the all-\(a\) configuration is absorbing.
5 Many colours: plurality consensus (UND-3)
Becchetti, Clementi, Natale, Pasquale and Silvestri (Plurality consensus in the gossip model, SODA 2015) analyse the undecided-state dynamics with \(k\) colours: a state is a colour or the undecided state (Table 1), and with \(c_i\) nodes of colour \(i\) and \(q\) undecided nodes one round gives in expectation \(\mu _i=c_i(c_i+2q)/n\) nodes of colour \(i\) and \(\mu _q=(q^2+(n-q)^2-\sum _i c_i^2)/n\) undecided nodes (their (3)–(4)). The monochromatic distance is \(\mathrm{md}(c)=\sum _i(c_i/c_1)^2\in [1,k]\), \(c_1\) the plurality. For \(k=2\) the dynamics is the binary one.
The range of \(k\) in Theorem 11 of the paper needs a minor correction: its proof invokes Lemma 10, which assumes \(k=O((n/\log n)^{1/4})\), and the round-by-round argument closes for \(k\le \varepsilon (\alpha )(n/\log n)^{1/3}\). The formalized statement takes \(Ck\le (n/\log n)^{1/3}\) with \(C=C(\alpha )\) (details).
Equations (3)–(4) hold, \(1\le \mathrm{md}(c)\le k\), and the two-colour dynamics is the binary dynamics under undecided \(\mapsto u\), colour \(0\mapsto a\), colour \(1\mapsto b\).
Linearity over the nodes, as in the binary case; the binary update is checked on the nine pairs of states.
Let \(\ell =3\log n\) and call a round good if every count is within \(\sqrt{3\ell (\mu +2\ell )}\) of its mean \(\mu \) (Bernstein); a round is bad with probability at most \((k+4)/n^3\). Let \(\theta =1/(1+\alpha )\), \(\kappa =1-\theta \), \(B=2\, \mathrm{md}(x_0)\), \(S\) the nodes of colours other than \(m\), \(c=c_m\), \(\Phi =\mu _m\). If \(n\ge 2\cdot 10^{12}K^2k^3\log n\) with \(K=(1+\alpha )^2/\alpha \), a good round keeps the invariant \(c_i+12\sqrt{\ell c}\le \theta c\) (\(i\ne m\)), \(S+12B\sqrt{\ell c}\le Bc\), multiplies \(\Phi \) by \(1+\kappa /(8000B)\) unless \(4S+q\le n/10\), and keeps \(\{ 4S+q\le n/10\} \); the first round from \(q=0\), \((1+\alpha )c_i\le c_m\) enters the invariant with \(\Phi \ge n/(2k^2)\).
For the ratios: if \(X\le tc/2\) one round cannot double it; if fewer than \(n/20\) nodes are decided, \(c\) grows by \(16/9\), which absorbs the slack; otherwise \(c\ge n/(20(1+B))\) and the deterministic drift \(X\mu _m-\mu _Xc\ge \frac t2\kappa c^3/n\) beats the deviations, which needs \(c^3\gtrsim n^2\log n\), i.e. \(k\lesssim (n/\log n)^{1/3}\). For \(\Phi \): \(\mu _m+2\mu _q=n+(n-c-2q)^2/n+2W/n\) with \(W=\sum _{j\ne m}c_j(c-c_j)\ge \kappa cS\) (the plurality drift, Lemma 1 of the paper). In the first round \(q=0\), so the ratios square and \(\mu _S=(\mathrm{md}-1)\mu _m\).
Let \(\alpha {\gt}0\) and \(C=10^5((1+\alpha )^2/\alpha )^2\). For every \(n\) with \(\log n\ge C\), every \(k\) with \(Ck\le (n/\log n)^{1/3}\) and every configuration without undecided nodes in which colour \(m\) has at least \(1+\alpha \) times as many nodes as every other colour, all nodes hold \(m\) after \(\lceil C\, \mathrm{md}(x)\log n\rceil \) rounds with probability at least \(1-6/n\) (SODA 2015, Theorem 11; the range of \(k\) is discussed in FORMALIZATION_DIFFERENCES.md).
One round into the invariant, then \(T_2=\lceil \log (4k^2)/\log (1+\kappa /(8000B))\rceil \le 96000K\, \mathrm{md}\log n+1\) rounds with moving targets \(\Phi \ge \frac n{2k^2}(1+\kappa /(8000B))^t\) or \(4S+q\le n/10\), which end in \(\{ 4S+q\le n/10\} \) since \(\Phi \le n\); then \(T_3=\lceil 8\log n\rceil \) rounds in which \(4S+q\) contracts by \(3/4\) in expectation. The failure probability is at most \(T(k+4)/n^3+(3/4)^{T_3}n/10\le 6/n\).
6 Many colours: the \(\Omega (\mathrm{md}(c))\) lower bound (UND-3)
The same paper (SODA 2015, Theorem 8) shows that, without any bias, the dynamics needs \(\Omega (\mathrm{md}(c))\) rounds. With \(R(c)=\sum _i c_i/c_1\) and \(\Lambda (c)=R(c)^2/\mathrm{md}(c)\): after the first round most nodes are undecided (Lemma 3); their number \(q\) then descends to about \(n/2\) within \(O(\log n)\) rounds while no colour exceeds \(\gamma n/\mathrm{md}\) (Lemma 6); from there no colour grows faster than by a factor \(1+O(1/\mathrm{md})\) per round (Lemma 7). All constants are existential, “w.h.p.” is \(1-C/n\), and \(k\) ranges over \(Ck\le (n/\log n)^{a}\) with the paper’s exponent \(a\).
Lemmas 6 and 7 need minor corrections: the window \(|Q-n/2|\le 2\gamma ^2/\mathrm{md}(\bar c)\) should read \(2\gamma ^2n/\mathrm{md}(\bar c)\); the proof of (17) uses the initial instead of the current monochromatic distance; in Lemma 7 the growth factor is \(1+(4\gamma ^2+2\gamma +1)/\mathrm{md}\), the lower bound (23) on \(E[\Delta ']\) reverses the Cauchy–Schwarz inequality, and the proof needs \(\gamma \ge 1\) (any \(\gamma {\gt}1/2\) would do) rather than an arbitrary \(\gamma {\gt}0\); and both lemmas must bound the largest colour, not only the initial plurality (details).
\(\mathrm{md}\le R\le k\) and \(\mathrm{md}\le \Lambda \le k\); without undecided nodes \(R=n/c_1\) and \(\Lambda =n^2/\sum _ic_i^2\). With \(\delta =q-n/2\): \(\mu _i=(1+(2\delta +c_i)/n)\, c_i\) and \(E[Q'-n/2]=(2\delta ^2-\sum _jc_j^2)/n\) (the paper’s (20) and (19)).
\(c_i/c_1\in [0,1]\) gives \((c_i/c_1)^2\le c_i/c_1\le 1\); Cauchy–Schwarz gives \(R^2\le k\, \mathrm{md}\). The expectations are (3)–(4) rewritten with \(q=n/2+\delta \).
Let \(Ck\le (n/\log n)^{1/2}\). From a configuration \(x\) without undecided nodes, with plurality colour \(m\), after one round, with probability at least \(1-C/n\): \(c_m\ge n/(2R^2)\), every colour has at most \(2n/R^2\) nodes, and \(n(1-2/\Lambda )\le q\le n(1-1/(2\Lambda ))\) (\(R\), \(\Lambda \) of \(x\)).
With \(q=0\), \(\mu _i=c_i^2/n\le \mu _m=n/R^2\) and \(\mu _q=n-\sum _ic_i^2/n=n(1-1/\Lambda )\); in a good round (Lemma 10, deviation level \(3\log n\)) the deviations are small compared with \(\mu _m\ge n/k^2\ge C^2\log n\) and with \(n/\Lambda \ge n/k\). Proved with \(C=100\).
Let \(Ck\le (n/\log n)^{1/6}\). If \(q=(1+\delta )n/2\) with \(1-\delta \ge 1/(2k)\), then after one round \(Q'\le (1+\delta ^2)n/2\) with probability at least \(1-C/n^2\) (16). If every colour is at most \(\gamma n/D\), with \(\gamma \ge 1\) and \(0{\lt}D\le k\), then \(Q'\ge n/2-2\gamma ^2n/D\) with probability at least \(1-C/n^2\) (17, corrected). Hence there are \(\gamma \ge 1\) and \(C\) such that, for \(x\) without undecided nodes with \(\mathrm{md}(x)\ge C\) and \(y\) satisfying the conclusion of Lemma 13, there is a round \(t\le C\log n\) such that, with probability at least \(1-C/n\), every colour is at most \(\gamma n/\mathrm{md}(x)\) at each round \(s\le t\), and at round \(t\) also \(|q-n/2|\le 2\gamma ^2n/\mathrm{md}(x)\).
(16): \(\mu _q=(1+\delta ^2)n/2-\sum _jc_j^2/n\) and \(\sum _jc_j^2\ge (n-q)^2/k\). (17): \(\mu _q\ge n/2-\sum _jc_j^2/n\) and \(\sum _jc_j^2\le (\max _jc_j)(n-q)\le \gamma n^2/D\). The round \(t\) is deterministic: the first \(s\) with \((1-1/\Lambda )^{2^s}\le 4\gamma ^2/\mathrm{md}\). The colours follow an explicit envelope (at most \(8n/D\), then at most \(\gamma n/D\) with \(\gamma =24\)), iterated with moving targets. Proved with \(\gamma =24\) and \(C=10^6\).
Let \(\gamma \ge 1\) and \(Ck\le (n/\log n)^{1/4}\). If \(C\le D\le k\), \(|q-n/2|\le 2\gamma ^2n/D\) and every colour is at most \(\gamma n/D\), then for every \(T\le D/C\), after \(T\) rounds, with probability at least \(1-C/n\), every colour is at most \(2\gamma n/D\) and \(|q-n/2|\le 2\gamma ^2n/D\).
One round multiplies the bound \(B\in [\gamma n/D,2\gamma n/D]\) on the colours by at most \(1+(4\gamma ^2+2\gamma +1)/D\) and keeps the window, with probability at least \(1-C/n^2\): by (20), \(2\delta +c_i\le (4\gamma ^2+2\gamma )n/D\), and by (19) \(E[\Delta ']\le 8\gamma ^4n/D^2\) and \(E[\Delta ']\ge -(\max _jc_j)(n-q)/n\ge -(4\gamma /3)n/D\). Iterate for \(T\le D/C\) rounds, during which the factor stays at most \(2\). Proved with \(C=30\gamma ^2\).
There is \(C{\gt}0\) such that, for every \(n\) with \(\log n\ge C\), every \(k\) with \(Ck\le (n/\log n)^{1/6}\) and every configuration \(x\) without undecided nodes: for every \(T\) with \(CT\le \mathrm{md}(x)\), after \(T\) rounds every colour has at most \(Cn/\mathrm{md}(x)\) nodes with probability at least \(1-C/n\); and for every \(T\) with \(C(T+1)\le \mathrm{md}(x)\), all nodes hold the same colour after \(T\) rounds with probability at most \(C/n\). Since monochromatic configurations are absorbing, the convergence time is \(\Omega (\mathrm{md}(x))\) with probability at least \(1-C/n\).
Compose Lemma 13, Lemma 14 and Lemma 15 (with the \(\gamma \) of Lemma 14, \(D=\mathrm{md}(x)\)) by the Markov property; a round \(T\) up to the descent round is covered by the bound at every round of Lemma 14. A monochromatic configuration has \(n{\gt}Cn/\mathrm{md}(x)\) nodes of one colour once \(\mathrm{md}(x){\gt}C\). Proved with \(C=1017429\) for the first form and \(2C\) for the second.
7 The sequential dynamics: approximate majority
At each step an ordered pair (initiator, responder) of distinct agents is drawn uniformly among the \(n(n-1)\) such pairs, independently of the past; only the responder updates, by the rule of Definition 1 applied to the initiator’s state. This is the approximate-majority protocol of Angluin, Aspnes and Eisenstat (Distributed Computing 21, 2008), with \(x\), \(y\) and blank written \(a\), \(b\) and \(u\).
The expectation of a function of the next configuration that depends only on the states of the initiator and the responder is its value on idle interactions plus the four state-changing transitions \(xb\), \(yb\), \(xy\), \(yx\), weighted by \(aq\), \(bq\), \(ab\), \(ab\) pairs out of \(n(n-1)\) (with \(q\) the number of blank agents).
If one step never increases \(e^{\varphi }F\) in expectation, then \(e^{\sum _{\text{path}}\varphi }F\) has expectation at most \(F\) at every finite time, and Markov’s inequality bounds the probability that the path sum of \(\varphi \) is large.
The potentials \(1/((a-b)^2+4n)\) (state-changing interactions), \(1\) (central region), \(1/(a+b)\) (blank corner), \(3b+q+1\) and \(3a+q+1\) (the two opinion corners), and \(e^{-\lambda \max (a-b,0)}\) (the gap stays positive) satisfy the hypothesis of Lemma 19 with suitable weights.
For every \(c\) there is \(C\) such that from every non-blank configuration of \(n\ge 2\) agents, after \(T\ge Cn\log n\) interactions all agents agree, with probability at least \(1-C/n^c\).
For every \(c\) there is \(C\) such that if initially \(a-b\ge C\sqrt n\log n\), then after \(T\ge Cn\log n\) interactions all agents hold \(a\), with probability at least \(1-C/n^c\).