Gibbs sampling, exact coupling and finite-error certificates

For any fixed site $i$, a configuration sampled from $\pi$ has conditional distribution $q_i(\cdot \mid \eta )$ at $i$ given its exterior $\eta$. Replacing its spin by a fresh draw from that same conditional leaves the joint law unchanged: for each $\eta$ and $s$, the resulting mass is ${\pi }_{V\setminus \{i\}}(\eta )q_i(s\mid \eta )=\pi ({\eta }^{i,s})$. Averaging these invariant updates over the uniform site choice proves that $\pi$ is invariant for $P$.

For probability vectors $p,q$ on a finite set, put $r_s=\min \{p_s,q_s\}$ and $\alpha ={\sum }_s{r}_s$. Assign joint mass $r_s$ to $(s,s)$. If $\alpha <1$, add mass $(p_s-r_s)(q_a-r_a)\mathrm{/}(1-\alpha )$ to each pair $(s,a)$. The residual supports are disjoint, so this added mass is off the diagonal; summing rows and columns gives marginals $p$ and $q$, and the disagreement probability is $1-\alpha =\frac{1}{2}{\sum }_s\mathrm{\mid }{p}_s-q_s\mathrm{\mid }$. If $\alpha =1$, the diagonal masses alone give the required joint law.

If configurations $x,y$ differ on the set $D=\{j:x_j\mathrm{\ne }{y}_j\}$, then for each site $i$ the triangle inequality, applied while changing the differing exterior coordinates one at a time, gives $\mathrm{\parallel }{q}_i(\cdot \mid x_{-i})-q_i(\cdot \mid y_{-i}){\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\le {\sum }_{j\in D}{c}_{ij}$. Use the joint law from step 1.2 to resample the updated spins maximally, and choose the same uniformly random update site in both chains. If $d_H$ is the number of differing coordinates, the expected new Hamming distance is therefore at most $d_H(x,y)-\frac{d_H(x,y)}{n}+\frac{1}{n}{\sum }_{j\in D}{\sum }_i{c}_{ij}\le (1-\frac{1-c}{n})d_H(x,y)\mathrm{.}$ The last inequality uses the column-sum bound in [A1]; the row-sum bound is retained as a stated hypothesis but is not needed for this estimate.

Repeat this joint construction at each update. Conditional expectation and induction give $\mathbb{E}[d_H(X_t,Y_t)]\le n(1-(1-c)\mathrm{/}n{)}^t$ when one chain starts at $x$ and the other starts with law $\pi$: initially $d_H\le n$, and the second marginal remains $\pi$ by step 1.1.

Since ${\mathbf{1}}_{\{X_t\mathrm{\ne }{Y}_t\}}\le d_H(X_t,Y_t)$, for every event $A\subseteq S^V$ the difference $\mathrm{\mid }\mathrm{Pr}(X_t\in A)-\mathrm{Pr}(Y_t\in A)\mathrm{\mid }$ is at most $\mathrm{Pr}(X_t\mathrm{\ne }{Y}_t)$. For finite laws of equal mass, the supremum of this event difference equals half the ${\mathrm{\ell }}^1$ distance: the positive and negative parts of their signed difference have equal mass, each half the sum of absolute values. Taking the supremum over $A$ therefore proves the first total-variation bound in the Statement. For $t=0$ the exponential bound is equality; for $t\ge 1$, $(1-u{)}^t\le e^{-ut}$ with $u=(1-c)\mathrm{/}n\in (0,1]$ gives the stated exponential estimate.

If $a=b$, the observable bound is immediate. Otherwise set $g=(f-a)\mathrm{/}(b-a)$, so $0\le g\le 1$. For the signed measure $\mathrm{\Delta }={\mathcal{L}}_x(X_t)-\pi$, the positive and negative masses both equal $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$ because $\mathrm{\Delta }(S^V)=0$; hence $\mathrm{\mid }{\sum }_{z}g(z)\mathrm{\Delta }(z)\mathrm{\mid }\le \mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$. Multiplying by $b-a$ and using step 4.1 proves the asserted bias bound.

Insert the intermediate real quantities in the order $\tilde{m},\widehat{m},m,{\theta }_T,\theta$ and apply the real triangle inequality repeatedly: $\mathrm{\mid }\tilde{m}-\theta \mathrm{\mid }\le \mathrm{\mid }\tilde{m}-\widehat{m}\mathrm{\mid }+\mathrm{\mid }\widehat{m}-m\mathrm{\mid }+\mathrm{\mid }m-{\theta }_T\mathrm{\mid }+\mathrm{\mid }{\theta }_T-\theta \mathrm{\mid }\mathrm{.}$ This bounds the total error by the sum of its four intermediate discrepancies.

Substitute the four assumed bounds into step 1.1 to obtain $\mathrm{\mid }\tilde{m}-\theta \mathrm{\mid }\le {ϵ}_{\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}}+{ϵ}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}}+{ϵ}_{\mathrm{m}\mathrm{i}\mathrm{x}}+{ϵ}_{\mathrm{t}\mathrm{r}}$. The proof is conditional on the statistical event in [A1] and asserts no confidence level or probability for it.

A discrepancy known to vanish contributes zero in step 1.1, so its budget term can be omitted. For any prescribed nonnegative budgets, set $\theta =0$, ${\theta }_T={ϵ}_{\mathrm{t}\mathrm{r}}$, $m={ϵ}_{\mathrm{t}\mathrm{r}}+{ϵ}_{\mathrm{m}\mathrm{i}\mathrm{x}}$, $\widehat{m}={ϵ}_{\mathrm{t}\mathrm{r}}+{ϵ}_{\mathrm{m}\mathrm{i}\mathrm{x}}+{ϵ}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}}$, and $\tilde{m}={ϵ}_{\mathrm{t}\mathrm{r}}+{ϵ}_{\mathrm{m}\mathrm{i}\mathrm{x}}+{ϵ}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}}+{ϵ}_{\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}}$. All four signed increments are their respective nonnegative budgets, all four hypotheses hold with equality, and the total error equals their sum. Omitting any strictly positive term would make the proposed right-hand side smaller than this attained error, proving the uniform non-omission claim. This does not exclude a smaller bound in a particular instance with cancellations or additional information.

Every one-site conditional probability of either sign is strictly positive, because it is a ratio of positive finite weights and a positive finite sum. There are only finitely many sites and exterior configurations, so $\delta ={\min }_{i\in V,\eta \in \{-1,+1{\}}^{V\setminus \{i\}},s\in \{-1,+1\}}{q}_i(s\mid \eta )>0.$

For a fixed site $i$, the log odds of the plus conditional are $\log \frac{q_i(+1\mid \eta )}{q_i(-1\mid \eta )}=2h_i+2{\sum }_{\{i,j\}\in E}{K}_{\{i,j\}}{\eta }_j\mathrm{.}$ If $\eta \le \zeta$ coordinatewise, the right side for $\eta$ is at most the right side for $\zeta$ because each $K_{\{i,j\}}\ge 0$; hence $q_i(+1\mid \eta )\le q_i(+1\mid \zeta )$. Using the same $U_s$ in both updates therefore preserves coordinatewise order.

The finite Gibbs law $\pi$ is invariant under each heat-bath update: conditional on the spins off site $i$, the original spin and its replacement have the same conditional law $q_i(\cdot \mid \eta )$. Thus replacing the spin preserves every joint probability, and the uniform mixture over sites preserves $\pi$.

Fix an ordering of the $n=\mathrm{\mid }V\mathrm{\mid }$ sites. A block of $n$ successive seeds selects these sites in that order and has every uniform value below $\delta$ with probability $\theta =n^{-n}{\delta }^n>0$. On that event each update sets its selected spin to $+1$, whatever the other spins are, so the block maps every starting configuration to $+$. Disjoint blocks in the past are independent; the probability that none of the first $m$ blocks has this event is $(1-\theta {)}^m\to 0$. Thus with probability one a forcing block lies inside some explored horizon. The two extremes then have the same time-zero image, so the doubling procedure terminates almost surely.

Every state lies between $-$ and $+$. By step 1.2, applying a shared sequence of update maps preserves these inequalities. If the lower and upper outputs agree, every state started at the same horizon has that common output. The algorithm's returned state is therefore the image of every possible initial state under that finite composition.

For each integer time $t$, almost-sure forcing blocks define $X_t$ as the common image at time $t$ of all initial states started sufficiently far in the past. Intersecting these probability-one events over the countably many integer times defines all $X_t$ simultaneously. The construction is consistent because once a composition maps all states to one value, every earlier extension followed by that composition has the same value. The variable $X_{t-1}$ depends only on seeds through time $t-1$, so it is independent of the seed at time $t$, and $X_t=F_t(X_{t-1})$. The two-sided iid stream is shift-invariant and this construction uses the same rule at every time, so the law $\rho$ of $X_t$ does not depend on $t$. It follows from the definition [L1] that $\rho$ is invariant for $P$.

Put $N=\mathrm{\mid }\mathrm{\Omega }\mathrm{\mid }=2^n$. From any state $x$ to any state $y$, the chain can select the fixed site ordering from step 2.1 and set each spin to its value in $y$; this has probability at least $n^{-n}{\delta }^n>0$. Hence every entry of the $n$-step transition matrix $P^n$ is positive. Let $\kappa ={\min }_{x,y}{P}^n(x,y)>0$ and $\lambda =N\kappa \in (0,1]$. If $\lambda <1$, each row of $P^n$ is $\lambda$ times the uniform law on $\mathrm{\Omega }$ plus $(1-\lambda )$ times a probability law $R_x$. For any laws $\mu ,\nu$, the positive and negative parts of $\mu -\nu$ each have mass $\mathrm{\parallel }\mu -\nu {\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$; because $0\le R_x(A)\le 1$, $\mathrm{\mid }(\mu R)(A)-(\nu R)(A)\mathrm{\mid }\le \mathrm{\parallel }\mu -\nu {\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$ for every event $A$. Thus $P^n$ contracts total variation by at most $1-\lambda$. If $\lambda =1$, all rows are uniform. In either case two invariant laws for $P$ must coincide. Since $\pi$ is invariant by step 1.3 and $\rho$ is invariant by step 3.1, $\rho =\pi$.

At time zero, the algorithm returns the common image whenever its explored interval contains a forcing block. By the definition of $X_0$ in step 3.1, this is exactly $X_0$ on the probability-one termination event. Its law is $\rho =\pi$ by step 4.1, proving exactness.

For each fixed spin configuration $\sigma$, summing $W(\sigma ,A)$ over $A\subseteq E$ factors over edges. An unequal-spin edge must be absent and contributes $1$; an equal-spin edge contributes either $1$ or $v_e$. Thus ${\sum }_{A}W(\sigma ,A)={\prod }_{e\in E}(1+v_e{\mathbf{1}}_{\{\sigma (u_e)=\sigma (w_e)\}})=w_P(\sigma )$, which is positive by [F1]. Dividing by this conditional normalizer shows that under $\nu$, given $\sigma$, unequal-spin edges are forced absent and equal-spin edges are independent Bernoulli variables with activation probabilities $v_e\mathrm{/}(1+v_e)$, including probability zero when $v_e=0$. This is exactly the first stage of [F3].

Every edge set produced in step 1.1 has $W(\sigma ,A)>0$: all active edges have $v_e>0$ and equal endpoint spins, while inactive edges contribute $1$. Therefore $\nu (A)>0$. By [F2], conditional on this edge set, its components receive independent uniform colors. This is exactly the second stage of [F3].

Start with $\sigma$ distributed as the spin marginal ${\pi }_P$ of $\nu$. By step 1.1, after the first stage the pair $(\sigma ,A)$ has joint law $\nu$. By step 2.1, the new configuration ${\sigma }^{\mathrm{\prime }}$ is then drawn from the spin conditional law $\nu (\cdot \mid A)$. Summing over the finite edge-set space shows that its marginal is the spin marginal of $\nu$, namely ${\pi }_P$. Hence the update preserves ${\pi }_P$.

The graph has finitely many edges, so the first stage performs one draw per edge; the second stage performs one draw per connected component of a finite graph. Both stages therefore terminate after finitely many operations.