Dependencies

For uniform neighbor sampling, \(\pi _i=d_i/(2|E|)\), so all-white consensus has probability \(\sum _{i:s(i)=1}d_i/(2|E|)\). On a regular graph this is the initial fraction of white vertices.

A run applies rounds \(r_1,\dots ,r_T\colon V\to V\) in order. Its backward map is \(r_1\circ r_2\circ \cdots \circ r_T\). The disagreement indicator is \(0\) on constant configurations and \(1\) otherwise. Wright–Fisher sampling picks every row uniformly on \(V\), self included, i.e. the complete graph with self-loops.

\(\mathrm{vol}(S)=\sum _{u\in S}d_u\); the conductance \(\varphi (G)\) is the minimum of \(|\mathrm{cut}(U,V\setminus U)|/\mathrm{vol}(U)\) over \(0{\lt}\mathrm{vol}(U)\le m\); \(\lambda _u\) is the number of neighbours of \(u\) with another opinion; for two opinions \(s_t\) is the side of smaller volume and \(\Psi =\sqrt{\mathrm{vol}(s_t)}\).

For a sampling kernel \(H\), two tokens move with the rounds of the voter dynamics: the token at \(x\) moves to \(r(x)\), where \(r\) is drawn from the independent product of the rows of \(H\). Off the diagonal the tokens make independent \(H\)-steps; on the diagonal they move together. The lazy kernel of a graph samples the vertex itself with probability \(1/2\) and otherwise a uniformly random neighbour. Rounds can also be composed on the left, \(W\mapsto r\circ W\).

A configuration is \(s:V\to C\). Independently sample \(r(i)\) according to row \(H_i\), then set the next configuration to \(i\mapsto s(r(i))\).

A distribution has nonnegative real weights summing to one. A kernel is a family of such distributions, one for each state. Expectations are finite sums. These are shared library definitions, not numbered results of the paper.

Assume \(H_{ij}{\gt}0\) whenever \(i,j\) are adjacent; extra support, such as self-loops, is allowed. Both constant configurations are absorbing, and the probability of remaining nonconstant tends to zero. This is the finite-time survival formulation of the paper’s transience claim.

The discrepancy between expected stationary white mass and all-white probability lies between zero and nonconsensus probability. Consequently all-white probability converges to initial stationary white mass. The implementation combines the paper’s limiting identification with the invariant from Lemma 2.3 when stating the limit.

For any stationary distribution \(\pi \), the expected white mass at every finite time is the initial mass \(\sum _i\pi _i s(i)\). No graph connectivity assumption is imposed on this invariant.

If \(s_t\neq \emptyset \), then \(\mathbb {E}[\Psi _{t+1}\mid s_t]\le \Psi -\sum _{u\in s_t}\lambda _u d_u/(32\Psi ^3) \le \Psi -d_{\min }\varphi /(32\Psi )\). The paper prints the sum over all of \(V\), which fails on the star \(K_{1,15}\); its proof gives the sum over \(s_t\).

On the two-vertex graph, every vertex must copy the other vertex. The alternating coloring flips each round and returns after two rounds; neither coloring is constant. Thus connectedness alone is insufficient.

After rounds \(r_1,\dots ,r_T\) the configuration is \(s\circ r_1\circ \cdots \circ r_T\): running the voter forward reads the initial colours through the backward map, whose point images are coalescing random walks. If the backward map is constant, the configuration is a consensus.

For every sampling kernel, the probability that no consensus is reached after \(T\) rounds is at most the sum over \(v\neq u_0\) of the probability that the tokens started at \(v\) and \(u_0\) are apart after \(T\) steps.

One white vertex on a triangle wins with probability \(1/3\). The stochastic matrix whose two rows are \((1/3,2/3)\) has stationary weights \((1/3,2/3)\), providing a nonuniform invariant example.

On a connected graph with Laplacian \(L\) and \(\mathrm{vol}=\sum _z d_z\), the system \(h(y)=0\), \((Lh)(x)=2d_x\) for \(x\neq y\) has a nonnegative solution \(h_y\), the expected hitting time of \(y\) for the lazy walk. It satisfies \(\sum _z d_z h_y(z)-\mathrm{vol}\, h_y(x)=\sum _z d_z h_x(z)-\mathrm{vol}\, h_x(y)\) and \(h_y(x)+h_x(y)\le 4\, \mathrm{vol}\, (n-1)\le 4n^3\).

Resampling one coordinate of an independent point does not change its law. Consequently centred coordinate functions have additive second and third moments, and if replacing each coordinate function improves \(\mathbb {E}f(z+\cdot )\) for all admissible \(z\), then the replacement of all of them improves \(\mathbb {E}f(c+\sum _i g_i(x_i))\) (BGKM16 Lemma A.1).

Call a round possible for \(H\) when every vertex samples a vertex of positive weight in its row. On a connected graph whose edges are charged by \(H\), a monochromatic region in which every vertex charges a vertex of the region grows to consensus through possible rounds. If \(H_{vv}{\gt}0\) for one vertex \(v\), the region \(\{ v\} \) qualifies, so nonconsensus probability tends to zero, bipartite graphs included.

Two coordinates of a uniform map \(V\to V\) agree with probability \(1/n\). Hence the backward walks from two distinct vertices have not met after \(T\) rounds with probability exactly \((1-1/n)^T\).

For configurations \(s,t\), the transition probability is

For Boolean colors a white target vertex contributes \(\sum _j H_{ij}s(j)\); a black target contributes its complement, giving the paper’s product formula.

On a connected nonbipartite graph every Boolean configuration has a possible finite path to a constant configuration.

Let the two tokens move one at a time, meeting being checked after each move. If a nonnegative potential \(F\) drops by one in expectation under a step of either token, the sequential walks are apart after \(T\) steps with probability at most \(F/T\). For a lazy kernel, the synchronous tokens are apart after \(T+1\) steps with probability at most the average of the indicator of starting apart and the sequential survival; hence at most \(3/4\) once \(T\ge 2\sup F\).

On three individuals, let every offspring pick a uniform parent, itself included. This kernel has self-loops, so it is supported beyond the edges of the triangle. Theorem 2.1 still applies, and one allele copy fixes with probability \(1/3\).

Under Wright–Fisher sampling a round is uniform on \(V\to V\), so the \(T\)-step configuration kernel is the average over \(T\) independent uniform rounds.

Define eventual all-white probability as the supremum of the increasing finite-time all-white probabilities. It equals the initial stationary white mass.

There is a constant \(b\) such that the expected consensus time is at most \(b\, m/(d_{\min }\varphi )\) and consensus holds within \(b\, m/(d_{\min }\varphi )\) rounds with probability at least \(1/2\), for every number of opinions.

If \(128\, \mathrm{vol}(s_0)\le d_{\min }\varphi T\), the opinions still disagree at time \(T\) with probability at most \(1/2\); in particular after \(128m/(d_{\min }\varphi )\) rounds, and the expected consensus time is at most twice that. On dynamic graphs with fixed degrees the same holds once \(128\, \mathrm{vol}(s_0)\le d_{\min }\sum _{t{\lt}T}\varphi _t\).

For a finite color set and any specified color \(c\), its eventual consensus probability is \(\sum _{i:s(i)=c}\pi _i\). These probabilities sum to one.

The probability that no consensus is reached after \(T\) rounds is at most \((n-1)(1-1/n)^T\). Consequently consensus is reached within \(2n\log n\) rounds with probability at least \(1-1/n\).

An absorbing target accessible from every state of a finite chain admits a uniform positive success probability in a fixed number of rounds. The survival probability decays geometrically in blocks and tends to zero.

If from every pair of vertices the tokens are apart after \(T_0\) steps with probability at most \(1/2\), then consensus fails after \(kT_0\) rounds with probability at most \((n-1)2^{-k}\).

On every connected graph with \(n\) vertices and from every initial colouring, the lazy voter dynamics reaches consensus within \(255\, n^3\log n\) rounds with probability at least \(1-1/n\).

The lazy kernel \((I+H)/2\) has the stationary distributions of \(H\) and positive self-loops. On any connected graph the lazy voter \((I+D^{-1}A)/2\) reaches consensus in colour \(c\) with probability \(\sum _{i:s(i)=c} d_i/2m\).

On a connected graph with \(n\) vertices, two lazy walks are apart after \(3(16n^3+1)\le 51n^3\) steps with probability at most \(1/2\), and after \(51kn^3\) steps with probability at most \(2^{-k}\), from every pair of start vertices.

If an observable equals \(\varphi _A\) on \(A\), \(\varphi _B\) on \(B\), lies in \([\varphi _B+m,\varphi _B+M]\) elsewhere, and keeps its expectation up to time \(T\), then \(\varphi (x_0)-\varphi _B-(\varphi _A-\varphi _B)\Pr (X_T\in A)\) lies between \(m\) and \(M\) times the probability of lying in neither event at time \(T\).

On a connected graph, bipartite or not, if \(H\) charges every edge and \(H_{vv}{\gt}0\) for some vertex \(v\), then consensus in colour \(c\) has probability \(\sum _{i:s(i)=c}\pi _i\) for every stationary \(\pi \).

Every finite nonempty stochastic matrix has a stationary distribution.

If every offspring picks a uniform parent, itself included, allele \(a\) fixes with probability \(c_a/n\), where \(c_a\) is its initial number of copies.