Dependencies

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.

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

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

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