Exactness and almost-sure termination of finite monotone CFTP

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.