- 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
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\).
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.
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.
\(\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)).
- Undecided.Plurality.ratioR
- Undecided.Plurality.ratioLam
- Undecided.Plurality.md_le_ratioR
- Undecided.Plurality.ratioR_le_card
- Undecided.Plurality.md_le_ratioLam
- Undecided.Plurality.ratioLam_le_card
- Undecided.Plurality.ratioR_of_und_zero
- Undecided.Plurality.ratioLam_of_und_zero
- Undecided.Plurality.mu_eq_half
- Undecided.Plurality.muU_sub_half
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)\).
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\)).
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\).
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\).
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)\).
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.
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).
Monochromatic configurations are fixed points, and from every configuration the probability of not being monochromatic after \(t\) rounds tends to \(0\).
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)\).
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\).
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).
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\).
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).
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\).
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\).