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