Gibbs sampling, exact coupling and finite-error certificates — Examples

The finite discrete metric on $\mathrm{\Omega }$ is complete and separable, so [F2] makes it Polish; the identity map then verifies [F1]. The weights sum to $4+ϵ$, so $\pi$ is a probability measure by [F3]. Each row of $Q$ is nonnegative and sums to one, and on a finite discrete space every function is measurable; thus [F4] makes $Q$ a probability kernel. Consequently the inputs satisfy [F5].

For states $x,y$ with $Q(x,y)>0$, the forward proposal-flow mass is $\mu (x,y)=\pi (x)Q(x,y)$ and the reversed mass is ${\mu }^{\mathsf{T}}(x,y)=\pi (y)Q(y,x)$. On a finite set the greatest measure dominated by both has point mass $\min \{\mu (x,y),{\mu }^{\mathsf{T}}(x,y)\}$, so [F5] accepts with probability $\min \{1,\pi (y)Q(y,x)\mathrm{/}(\pi (x)Q(x,y))\}$. Symmetry of $Q$ reduces this to $\min \{1,e^{-\beta (E(y)-E(x))}\}$. Hence each $L_i$ and $R_i$ jumps to its partner with probability $1\mathrm{/}4$, jumps to $H$ with probability $ϵ\mathrm{/}4$, and stays put with probability $3\mathrm{/}4-ϵ\mathrm{/}4$; from $H$ it jumps to each of the four well states with probability $1\mathrm{/}4$.

By [F6] and [F7], $\pi$ is invariant for $P$. Also $P^4(x,y)>0$ for all $x,y$: every state reaches $L_0$ in at most two positive-probability transitions, $L_0$ reaches every state in at most two, and any unused steps can be filled by the positive self-transition at $L_0$. Since $\mathrm{\Omega }$ is finite, let $\kappa ={\min }_{x,y}{P}^4(x,y)>0$, $N=\mathrm{\mid }\mathrm{\Omega }\mathrm{\mid }=5$, and $\lambda =N\kappa \in (0,1]$. If $\lambda <1$, each row of $P^4$ is $\lambda$ times the uniform law plus $1-\lambda$ times a probability row. For $\mathrm{\Delta }=\mu -\nu$ with total mass zero, its positive and negative parts each have mass $\mathrm{\parallel }\mu -\nu {\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$; since every residual row assigns a number in $[0,1]$ to an event, integration against $\mathrm{\Delta }$ is bounded in absolute value by $\mathrm{\parallel }\mu -\nu {\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$. Thus for every two laws $\mu ,\nu$, $\mathrm{\parallel }\mu P^4-\nu P^4{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\le (1-\lambda )\mathrm{\parallel }\mu -\nu {\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$. If $\lambda =1$, all rows are uniform. Therefore $\pi$ is the unique invariant law and the chain converges to it.

The target assigns equal mass $1\mathrm{/}(4+ϵ)$ to $L_0,L_1$, so $\pi (\cdot \mid L)$ is uniform and $\pi (L)=2\mathrm{/}(4+ϵ)$. From either state in $L$, the exit probability to $H$ is $ϵ\mathrm{/}4$, while the transition to the other state of $L$ has probability $1\mathrm{/}4$. Conditioning a step on no exit gives flip probability $(1\mathrm{/}4)\mathrm{/}(1-ϵ\mathrm{/}4)=1\mathrm{/}(4-ϵ)$ and stay probability $(3-ϵ)\mathrm{/}(4-ϵ)$. This symmetric two-state chain preserves the uniform law and has nonconstant eigenvalue $(2-ϵ)\mathrm{/}(4-ϵ)\le 1\mathrm{/}2$, giving the stated within-well total-variation bound. The exit probability is constant across both states, so survival for $t$ steps has probability $(1-ϵ\mathrm{/}4{)}^t$.

Survival implies $X_t\in L$, so for the initial law $\pi (\cdot \mid L)$, $\mathrm{Pr}(X_t\in L)\ge (1-ϵ\mathrm{/}4{)}^t$. On a finite space, if $\mathrm{\Delta }=\mu -\nu$ has total mass zero then ${\sup }_A\mathrm{\mid }\mathrm{\Delta }(A)\mathrm{\mid }=\frac{1}{2}{\sum }_x\mathrm{\mid }\mathrm{\Delta }(x)\mathrm{\mid }$, so the event $L$ gives $\mathrm{\parallel }\pi (\cdot \mid L)P^t-\pi {\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\ge (1-ϵ\mathrm{/}4{)}^t-\pi (L)\mathrm{.}$ For any mixture of starting states, the half-${\mathrm{\ell }}^1$ triangle inequality bounds its distance from $\pi$ by the largest component distance. Since $\pi (\cdot \mid L)P^t$ is the mixture of $P^t(L_0,\cdot )$ and $P^t(L_1,\cdot )$ with weights $1\mathrm{/}2$, it follows that $d(t)\ge (1-ϵ\mathrm{/}4{)}^t-2\mathrm{/}(4+ϵ)$. If $t\le \lfloor {ϵ}^{-1}\rfloor$, Bernoulli's inequality gives $(1-ϵ\mathrm{/}4{)}^t\ge 1-tϵ\mathrm{/}4\ge 3\mathrm{/}4$, while $2\mathrm{/}(4+ϵ)<1\mathrm{/}2$; hence $d(t)\ge 1\mathrm{/}4>1\mathrm{/}8$. The definition of $t_{\mathrm{m}\mathrm{i}\mathrm{x}}(1\mathrm{/}8)$ therefore gives the claimed lower bound.