Finite Dobrushin bound for random-scan heat-bath sampling

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.