The Undecided-State Dynamics

We formalize the basic properties of the synchronous undecided-state dynamics with two opinions on the complete graph: the exact one-round expectations of the three counts, the resulting growth of the bias by the factor \(1+q/n\) (the undecided nodes amplify the current majority), and almost-sure absorption in a monochromatic configuration.

1 The model

Definition 1 Undecided-state dynamics
✓

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\).

Proof ▶

The average over all sampling functions of a function of one coordinate is the uniform average.

Theorem 3 Expected counts and bias
✓

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)\).

Proof ▶

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\).

Proof ▶

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\).

Proof ▶

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.

Proof ▶

\(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\).

Proof ▶

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).

Proof ▶

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\).

Proof ▶

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)\).

Proof ▶

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).

Proof ▶

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)).

Proof ▶

\(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 \).

Lemma 13 First round; Lemma 3
✓
#

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\)).

Proof ▶

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\).

Lemma 14 Descent of the undecided nodes; Lemma 6
✓

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)\).

Proof ▶

(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\).

Lemma 15 Plateau; Lemma 7
✓

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\).

Proof ▶

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\).

Theorem 16 Lower bound; Theorem 8
✓

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\).

Proof ▶

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

Definition 17 Sequential undecided-state dynamics
✓

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\).

Lemma 18 One-step formula
✓

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).

Lemma 19 Weighted supermartingales
✓

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.

Theorem 21 Convergence; AAE Theorem 1
✓

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\).