The shared library uses Cesàro averages of evolved distributions and compactness of the finite probability simplex. This supplies the existence fact recalled before Lemma 2.2; uniqueness is not required.

Take a common block length exceeding all finitely many access times, then a maximum survival probability strictly below one. Iterate the resulting contraction.

A shared library result (roadmap FND-4): decompose the observable pointwise into its values on \(A\) and off \(A\cup B\), take expectations, and bound the second part.

The configuration distribution is the pushforward of the independently sampled neighbors. Factor its equality indicator into a product over vertices.

A coloring without a monochromatic edge would be a proper two-coloring. Starting with a monochromatic edge, each vertex of its region can keep that color by sampling an internal neighbor. Connectedness supplies an edge leaving every proper region. One more vertex can copy across that edge. Induction on the number of vertices outside the region gives consensus.

Every possible copying round has positive probability. Thus graph propagation gives accessibility. Apply the shared finite-chain absorption theorem.

A vertex’s expected next color indicator is \(\sum _jH_{ij}s(j)\). Interchanging finite sums and using \(\pi H=\pi \) proves one-step preservation; induction proves the iterated statement.

Pointwise, the white mass agrees with the all-white indicator on constant configurations and lies in \([0,1]\) elsewhere. Finite-horizon optional stopping, with the two consensus configurations as targets and the invariant of Lemma 2.3, bounds the discrepancy; squeeze it using Lemma 2.1.

Consensus is absorbing, so the probabilities increase and are bounded by one. Their supremum is their limit. Identify this limit using Lemma 2.2.

The degree-sum formula normalizes these weights. In the stationarity equation, the degree cancels the reciprocal sampling degree; undirected adjacency gives the remaining column sum. Equal degrees then give uniform vertex weights.

The color-indicator projection commutes with every copying step and with iterated expectations. Its all-white event is exactly all-\(c\) consensus. Apply Theorem 2.1 to this Boolean projection.

Induction on the list of rounds, since one round maps \(s\) to \(s\circ r\).

The product weights are all \(n^{-n}\); induct on \(T\), peeling off the first round.

Peel off the first round, swap it with the remaining average, and multiply by the one-round probability of not meeting; induct on \(T\).

Consensus holds once every backward walk has met the walk of a fixed vertex; apply the union bound over the other \(n-1\) vertices and the meeting probability, then \((1-1/n)^T\le e^{-T/n}\le n^{-2}\) for \(T\ge 2n\log n\).

As in Lemma 2.1: a boundary vertex copies its neighbour in the region, vertices of the region copy inside it, and all other vertices copy any vertex of positive weight. Possible rounds have positive probability, and the finite-chain absorption theorem applies.

Lemma 2.2 only needs nonconsensus probability to vanish; then project colours as in Section 2.3.

Apply the Remark to \((I+H)/2\); for uniform neighbour sampling use the degree distribution.

The uniform distribution is stationary and every entry is positive. For \(n\ge 3\) the complete graph is nonbipartite and Section 2.3 applies; for every \(n\) the Remark applies.

The voter dynamics on maps started from the identity composes the rounds on the right; composing them on the left gives the same finite-time expectations, since the rounds are independent and identically distributed (induction on \(T\), exchanging two finite expectations). The left composition read at two vertices is the two-token walk. Conclude with the pointwise union bound of Theorem 18.

The diagonal is absorbing, so the probabilities of being apart are submultiplicative in blocks of \(T_0\) steps; apply Lemma 24.

The maximum principle makes the linear system injective, hence surjective. The identity is the symmetry of \(L\). For the bound, \(\psi =h_y-h_x\) has energy \(\psi ^\top L\psi =2\, \mathrm{vol}\, (h_y(x)+h_x(y))\); apply Cauchy–Schwarz along a path from \(x\) to \(y\).

Two inductions on \(T\). When the first token lands on the old position of the second, the second stays put with probability at least \(1/2\).

Apply Lemma 27 to the potential \(h_y(x)-\sum _z d_z h_y(z)/\mathrm{vol}+4n^3\) of Lemma 26, bounded by \(8n^3\), then submultiplicativity.

With \(k=\lfloor T/(51n^3)\rfloor \), Lemma 24 and Theorem 28 bound the failure probability by \((n-1)2^{-k}\le 1/n\).

Reindex the pairs \((x,a)\) by \((x[i\mapsto a],x_i)\); induct over the set of replaced coordinates.

\(\Psi _{t+1}\) is at most the root of the new volume \(P+\sum _u X_u\) of the opinion of \(s_t\). Replace \(X_u\) for \(u\notin s_t\) by \(Y_u=\lambda _u\mathbf{1}[\text{move}]\) (concavity of \(\sqrt{\cdot }\)), expand \(\sqrt{P+x}\) to third order, and use \(\mathbb {E}\Delta '=0\), \(\mathbb {E}\Delta '^2\ge \sum _{s_t}\lambda _ud_u/4\), \(\mathbb {E}\Delta '^3\le 0\). The conductance gives \(\sum _{s_t}\lambda _ud_u\ge d_{\min }\varphi \, \mathrm{vol}(s_t)\).

The drift lemma of the shared library (FND-5) with drift \(d_{\min }\varphi _t/32\); restarting bounds the expected time.

Project each opinion to the two-opinion process “\(i\) against the rest”. From \(\ell \le \theta \) opinions, after \(384\, \mathrm{vol}(V)/(\theta d_{\min }\varphi )\) rounds at most \(5\theta /6\) remain with probability at least \(1/3\) (BGKM16 Lemma 2.3). Summing over the levels \(\theta _j=n(5/6)^j\) gives a geometric series; Markov’s inequality gives the probability form.