Metropolis–Hastings kernels

Put $h=\min \{f,g\}$. It is measurable and nonnegative by [F5]. Thus $\eta (A)={\int }_{A}hd\lambda$ is a measure by [F3]. Since $h\le f,g$, monotonicity [F4] gives $\eta (A)\le \rho (A)$ and $\eta (A)\le \sigma (A)$ for every $A$. In particular $\eta (E)\le \rho (E)<\mathrm{\infty }$, so $\eta$ is finite.

Let $\theta$ be any measure with $\theta \le \rho$ and $\theta \le \sigma$. Then $\theta (E)\le \rho (E)<\mathrm{\infty }$, so $\theta$ is finite. If $\lambda (B)=0$, then $\rho (B)={\int }_{B}fd\lambda =0$; hence $\theta (B)\le \rho (B)=0$. Therefore $\theta \ll \lambda$. It is sigma-finite because it is finite [F1]. By [A1] and [F2], choose a finite-valued nonnegative measurable density $k$ with $\theta (A)={\int }_{A}kd\lambda$ for every $A$.

For each integer $n\ge 1$, set $E_n=\{k\ge f+1\mathrm{/}n\}$. This set is measurable by [F5]. Monotonicity, additivity, and homogeneity [F4] give $\theta (E_n)={\int }_{E_n}kd\lambda \ge {\int }_{E_n}fd\lambda +\frac{\lambda (E_n)}{n}=\rho (E_n)+\frac{\lambda (E_n)}{n}\mathrm{.}$ But $\theta (E_n)\le \rho (E_n)<\mathrm{\infty }$, so $\lambda (E_n)=0$. The same argument with $g$ and $\sigma$ shows that each $G_n=\{k\ge g+1\mathrm{/}n\}$ is $\lambda$-null. Hence $N:={\bigcup }_{n\ge 1}(E_n\cup G_n)$ is $\lambda$-null, and $k\le f$ and $k\le g$, thus $k\le h$, on $E\setminus N$.

Absolute continuity gives $\theta (A)=\theta (A\setminus N)$ for every $A$, and [F6] gives $\eta (A)=\eta (A\setminus N)$. On $A\setminus N$, $k\le h$, so monotonicity [F4] yields $\theta (A)={\int }_{A\setminus N}kd\lambda \le {\int }_{A\setminus N}hd\lambda =\eta (A)\mathrm{.}$ Thus every common lower measure is dominated by $\eta$.

Step 1.1 shows that $\eta$ is dominated by both $\rho$ and $\sigma$; step 3.1 shows every measure dominated by both is itself dominated by $\eta$. Therefore $\eta$ is the greatest common submeasure.

The measure $\lambda =\rho +\sigma$ is finite, and $\rho ,\sigma \ll \lambda$. By [A1], [F1]–[F3], choose finite-valued nonnegative measurable representatives $f=d\rho \mathrm{/}d\lambda$ and $g=d\sigma \mathrm{/}d\lambda$. For every $B\in \mathcal{F}$, ${\int }_B(f+g)d\lambda =\rho (B)+\sigma (B)=\lambda (B)={\int }_{B}1d\lambda \mathrm{.}$ Uniqueness in [F2] gives $f+g=1$ $\lambda$-almost everywhere. On the measurable null set where this fails, replace $f$ by $0$ and $g$ by $1$; the modified functions remain representatives and now satisfy $f+g=1$ everywhere.

The function $h=\min \{f,g\}$ is measurable and nonnegative by [F7]. By [F4], $\eta (A)={\int }_{A}hd\lambda$ defines a measure. Since $h\le f,g$, monotonicity in [F5] and the density identities in step 1.1 give $\eta (A)\le \rho (A)$ and $\eta (A)\le \sigma (A)$ for every $A$. In particular, $\eta (E)\le \rho (E)<\mathrm{\infty }$, so $\eta$ is finite.

Let $\theta$ be any measure with $\theta \le \rho$ and $\theta \le \sigma$. It is finite because $\theta (E)\le \rho (E)<\mathrm{\infty }$, and $\theta \ll \lambda$: if $\lambda (B)=0$, nonnegativity gives $\rho (B)=0$, and hence $\theta (B)=0$. By [A1], [F1]–[F3], choose a finite-valued nonnegative density $k=d\theta \mathrm{/}d\lambda$. For each integer $n\ge 1$, the measurable set $E_n=\{k\ge f+1\mathrm{/}n\}$ satisfies $\theta (E_n)={\int }_{E_n}kd\lambda \ge {\int }_{E_n}fd\lambda +\lambda (E_n)\mathrm{/}n=\rho (E_n)+\lambda (E_n)\mathrm{/}n\mathrm{.}$ Since $\theta (E_n)\le \rho (E_n)<\mathrm{\infty }$, this forces $\lambda (E_n)=0$. Thus $\{k>f\}={\bigcup }_{n\ge 1}{E}_n$ is null; the same argument using $\theta \le \sigma$ gives $k\le g$ almost everywhere. Therefore $k\le h$ outside a measurable $\lambda$-null set. Integrals on that null set vanish by simple approximation and [F5]–[F6], so monotonicity yields $\theta (A)\le \eta (A)$ for all $A$. Together with step 2.1, this proves that $\eta$ is the greatest common submeasure.

For each real $c<0$, $\{a>c\}=E$; for $0\le c<1$, $\{a>c\}=\{f=0\}\cup (\{f>0\}\cap \{g-cf>0\});$ and for $c\ge 1$ the set is empty. By [F7], each such set is measurable, so $a$ is measurable. It lies in $[0,1]$, and $af=\min \{f,g\}$ everywhere: on $\{f>0\}$ this follows by multiplying the ratio by $f$, while on $\{f=0\}$ both sides are zero. For a fixed $A$, approximate $a{\mathbf{1}}_A$ increasingly by simple functions. [F6] gives equality of their integrals against $\rho$ and against $f\lambda$; applying [F5] to both limits gives ${\int }_{A}ad\rho ={\int }_{A}afd\lambda ={\int }_A\min \{f,g\}d\lambda =\eta (A)\mathrm{.}$ Thus $a$ is a nonnegative measurable representative of $d\eta \mathrm{/}d\rho$ with values in $[0,1]$.

Put $\mathrm{\Lambda }=\lambda \otimes \lambda$. The lift $(x,y)\mapsto p(x)$ is product-measurable because the preimage of each Borel set $B$ is the rectangle $p^{-1}(B)\times \mathsf{X}$. Each section $C_x$ is measurable: for fixed $x$, the class of all $D\subseteq {\mathsf{X}}^2$ with $D_x\in \mathcal{X}$ is a sigma-algebra containing every measurable rectangle, so it contains $\mathcal{X}\otimes \mathcal{X}$. Since $q$ and ${\mathbf{1}}_C$ are product-measurable, [F6] makes their product measurable, and [F5] makes $H(x):={\int }_{\mathsf{X}}{\mathbf{1}}_C(x,y)q(x,y)\lambda (dy)=Q(x,C_x)$ measurable, where the equality is the given density identity for $Q(x,\cdot )$. The density identity for $\pi$ and [F10], first for simple functions and then for $H$ by [F9] and monotone convergence, give $\mu (C)={\int }_{\mathsf{X}}H(x)\pi (dx)={\int }_{\mathsf{X}}H(x)p(x)\lambda (dx)\mathrm{.}$ Substituting the expression for $H$ and applying Tonelli [F5] yields $\mu (C)={\int }_{\mathsf{X}}\text{\hspace{0.17em}⁣}{\int }_{\mathsf{X}}{\mathbf{1}}_C(x,y)p(x)q(x,y)\lambda (dy)\lambda (dx)={\int }_{C}md\mathrm{\Lambda }\mathrm{.}$ Thus $m$ is a density of the forward probability flow with respect to $\mathrm{\Lambda }$.

Let $\tau (x,y)=(y,x)$ and define ${\mathrm{\Lambda }}^{\mathsf{T}}(C)=\mathrm{\Lambda }({\tau }^{-1}C)$. By [F7], $\tau$ is measurable, so ${\mathrm{\Lambda }}^{\mathsf{T}}$ is a measure. On a rectangle $A\times B$, ${\mathrm{\Lambda }}^{\mathsf{T}}(A\times B)=\lambda (B)\lambda (A)=\lambda (A)\lambda (B)=\mathrm{\Lambda }(A\times B),$ using the product-measure convention $0\cdot \mathrm{\infty }=0$. Choose increasing measurable $X_n\uparrow \mathsf{X}$ with $\lambda (X_n)<\mathrm{\infty }$. The rectangles $X_n\times X_n$ increase to ${\mathsf{X}}^2$ and have equal finite measure for ${\mathrm{\Lambda }}^{\mathsf{T}}$ and $\mathrm{\Lambda }$. Measurable rectangles form a generating pi-system, so [F3]–[F4] give ${\mathrm{\Lambda }}^{\mathsf{T}}=\mathrm{\Lambda }$. For every nonnegative product-measurable $u$, the identity ${\int }_{{\tau }^{-1}C}ud\mathrm{\Lambda }={\int }_{C}u\circ \tau d\mathrm{\Lambda }$ holds first for indicators from ${\mathrm{\Lambda }}^{\mathsf{T}}=\mathrm{\Lambda }$, then for simple functions by finite addition, and for all such $u$ by [F9]. Applying it to $u=m$ yields ${\mu }^{\mathsf{T}}(C)=\mu ({\tau }^{-1}C)={\int }_{C}m(y,x)d\mathrm{\Lambda }\mathrm{.}$ Hence $m^{\mathsf{T}}(x,y)=p(y)q(y,x)$ is the reverse-flow density.

Apply [F8] to the finite probability measures $\mu ,{\mu }^{\mathsf{T}}$ and the sigma-finite reference measure $\mathrm{\Lambda }$. Their greatest common submeasure $\eta =\mu \wedge {\mu }^{\mathsf{T}}$ has density $h=\min \{m,m^{\mathsf{T}}\}$, so $\eta (C)={\int }_{C}hd\mathrm{\Lambda }(C\in \mathcal{X}\otimes \mathcal{X})\mathrm{.}$

Define ${\alpha }_{\mathrm{c}\mathrm{d}}=h\mathrm{/}m$ on $\{m>0\}$ and ${\alpha }_{\mathrm{c}\mathrm{d}}=1$ on $\{m=0\}$. It takes values in $[0,1]$. For a real $c<0$, $\{{\alpha }_{\mathrm{c}\mathrm{d}}>c\}={\mathsf{X}}^2$; for $0\le c<1$, $\{{\alpha }_{\mathrm{c}\mathrm{d}}>c\}=\{m=0\}\cup (\{m>0\}\cap \{h-cm>0\});$ for $c\ge 1$ the set is empty. Each set is measurable by [F6], so ${\alpha }_{\mathrm{c}\mathrm{d}}$ is jointly measurable. By its definition, ${\alpha }_{\mathrm{c}\mathrm{d}}m=h$ everywhere. For any $C$, choose nonnegative simple $s_n\uparrow {\alpha }_{\mathrm{c}\mathrm{d}}{\mathbf{1}}_C$. The simple density identity [F10] gives $\int s_{n}d\mu =\int s_{n}md\mathrm{\Lambda }$; monotone convergence on both sides then gives ${\int }_C{\alpha }_{\mathrm{c}\mathrm{d}}d\mu ={\int }_C{\alpha }_{\mathrm{c}\mathrm{d}}md\mathrm{\Lambda }={\int }_{C}hd\mathrm{\Lambda }=\eta (C)\mathrm{.}$ Thus ${\alpha }_{\mathrm{c}\mathrm{d}}$ is a version of $d\eta \mathrm{/}d\mu$.

On $\{m>0\}$, algebra gives ${\alpha }_{\mathrm{c}\mathrm{d}}=\frac{\min \{m,m^{\mathsf{T}}\}}{m}=\min \{1,\frac{p(y)q(y,x)}{p(x)q(x,y)}\}\mathrm{.}$ On $\{m=0\}$ its specified value is $1$, which is permissible because $\mu (\{m=0\})={\int }_{\{m=0\}}md\mathrm{\Lambda }=0$. The algorithm's chosen derivative and ${\alpha }_{\mathrm{c}\mathrm{d}}$ are two versions of the same Radon–Nikodym derivative, so [F11] makes them equal $\mu$-almost everywhere. This proves the common-density ratio and the forward-zero convention without asserting pointwise uniqueness on null sets.

The acceptance function satisfies $0\le \alpha \le 1$. For each $x$, $0\le a(x):=\int \alpha (x,y)Q(x,dy)\le 1$ because $Q(x,\cdot )$ is a probability measure. The function $a$ is measurable by [F5], so $r(x)=1-a(x)$ is measurable and takes values in $[0,1]$.

For fixed $x$, the accepted term $A\mapsto \int {\mathbf{1}}_A(y)\alpha (x,y)Q(x,dy)$ is a measure by [F9], since the section $y\mapsto \alpha (x,y)$ is measurable by [F8]. The rejection term $A\mapsto r(x){\mathbf{1}}_A(x)$ is a measure: for disjoint sets at most one can contain $x$. Their sum is a measure by [F10], and its total mass is $a(x)+r(x)=1$. For each fixed $A$, the accepted term is measurable in $x$ by [F5], and the rejection term is measurable since $r$ and ${\mathbf{1}}_A$ are measurable. Thus [F2] applies pointwise and $P$ is a probability kernel.

Define $\delta (x)=(x,x)$. For every measurable rectangle $A\times B$, ${\delta }^{-1}(A\times B)=A\cap B\in \mathcal{X}$. Since these rectangles generate $\mathcal{X}\otimes \mathcal{X}$ by [F7], $\delta$ is measurable. By [F9], $\zeta (D):={\int }_{D}rd\pi$ is a measure on $(\mathsf{X},\mathcal{X})$; it is finite because $0\le r\le 1$ and $\pi (\mathsf{X})=1$. Define $R(C):=\zeta ({\delta }^{-1}C)=\int {\mathbf{1}}_C(x,x)r(x)\pi (dx)$. It vanishes at the empty set, and preimages of disjoint sets under $\delta$ are disjoint; countable additivity of $\zeta$ therefore makes $R$ a finite measure on the product sigma-algebra.

Step 2.1 has established that $P$ is a probability kernel, so [F3] now supplies the joint measure $J_P$. Applying the same joint-law result to the input kernel $Q$ gives the proposal flow $\mu$ and its iterated-integral identity. Thus, for every product-measurable $C$, $J_P(C)=\int \text{\hspace{0.17em}⁣}\int {\mathbf{1}}_C(x,y)\alpha (x,y)Q(x,dy)\pi (dx)+R(C)={\int }_C\alpha d\mu +R(C)=\eta (C)+R(C),$ where the last equality uses $\alpha \mu =\eta$ from [F4].

The coordinate swap $\tau (x,y)=(y,x)$ is measurable by [F7] and is an involution. Define ${\eta }^{\mathsf{T}}(C):=\eta ({\tau }^{-1}C)$. This is a measure: measurability of $\tau$ makes the preimages measurable, and preimages preserve the empty set and disjoint countable unions, so [F4, F13] give the measure properties. Since $\eta$ is the greatest measure dominated by both $\mu$ and ${\mu }^{\mathsf{T}}$, its transpose is also dominated by both: for every $C$, ${\eta }^{\mathsf{T}}(C)\le {\mu }^{\mathsf{T}}(C)$ and ${\eta }^{\mathsf{T}}(C)\le \mu (C)$. Maximality gives ${\eta }^{\mathsf{T}}\le \eta$; transposing this inequality and using ${\tau }^2=\mathrm{i}\mathrm{d}$ gives $\eta \le {\eta }^{\mathsf{T}}$. Hence ${\eta }^{\mathsf{T}}=\eta$.

Since $\tau \circ \delta =\delta$, step 2.2 gives $R(C)=R({\tau }^{-1}C)$ for every product-measurable $C$. Step 4.1 gives the same symmetry for $\eta$, so the decomposition in step 3.1 yields $J_P(C)=J_P({\tau }^{-1}C)$ for every $C$. Thus the joint flow is symmetric, so $P$ is reversible by [F11].

Steps 2.1 and 5.1 prove that $P$ is a probability kernel reversible with respect to $\pi$. The general-state result [F12] applies on this measurable space and gives $\int P(x,A)\pi (dx)=\pi (A)$ for every $A\in \mathcal{X}$. Thus $\pi$ is invariant in the sense of [F6].