Adaptive MCMC convergence limits

Fix $f:\mathsf{X}\to [0,1]$ measurable. For $i=0,\dots ,N$, set $g_i=P_{{\mathrm{\Gamma }}_n}^{N-i}f$, so $g_N=f$. Joint kernel measurability and [F3] make each $g_i$ measurable in $({\mathrm{\Gamma }}_n,x)$ and $0\le g_i\le 1$. Also $g_i=P_{{\mathrm{\Gamma }}_n}{g}_{i+1}$.

The conditional transition rule [F1] and the identity in step 1.1 give $\mathbb{E}[f(X_{n+N})]-\mathbb{E}[P_{{\mathrm{\Gamma }}_n}^{N}f(X_n)]={\sum }_{i=0}^{N-1}\mathbb{E}\text{\hspace{0.17em}⁣}[(P_{{\mathrm{\Gamma }}_{n+i}}-P_{{\mathrm{\Gamma }}_n})g_{i+1}(X_{n+i})]\mathrm{.}$ Indeed, each summand is the difference between $\mathbb{E}[g_{i+1}(X_{n+i+1})]$ and $\mathbb{E}[g_i(X_{n+i})]$, and these differences telescope from $i=0$ through $N-1$.

By [F2] and the triangle inequality applied pointwise to successive kernels, $\mid (P_{{\mathrm{\Gamma }}_{n+i}}-P_{{\mathrm{\Gamma }}_n})g_{i+1}(X_{n+i})\mid \le {\sum }_{j=0}^{i-1}{D}_{n+j}$. Both sides are measurable, by step 1.1 and the assumed measurability of the $D_m$. Taking expectations bounds the absolute value of the $i$th summand in step 2.1 by ${\sum }_{j=0}^{i-1}\mathbb{E}[D_{n+j}]$. Summing gives the displayed bound for every such $f$; take the supremum using [F2]. For pairwise disjoint $A_{\mathrm{\ell }}$, countable additivity of each $P_{{\mathrm{\Gamma }}_n}^N(X_n,\cdot )$ and [F4] give $Q_{n,N}({\bigcup }_{\mathrm{\ell }}{A}_{\mathrm{\ell }})={\sum }_{\mathrm{\ell }}{Q}_{n,N}(A_{\mathrm{\ell }})$ by monotone convergence; also $Q_{n,N}(\mathsf{X})=1$. Thus $Q_{n,N}$ is a probability measure.

We record the finite-horizon construction used below. If $T$ is a probability kernel on $(S,\mathrm{\Sigma })$, start with any probability measure ${\mu }_0$ on $S$ (in particular ${\mu }_0={\delta }_s$ for a fixed start $s$). Given a probability measure ${\mu }_m$ on $S^{m+1}$, the map ${\widehat{T}}_m((s_0,\dots ,s_m),A):=T(s_m,A)$ is a probability kernel from $S^{m+1}$ to $S$, since the last-coordinate projection is measurable. For $E\in {\mathrm{\Sigma }}^{\otimes (m+2)}$, set ${\mu }_{m+1}(E):={\int }_{S^{m+1}}{\int }_S{1}_E((s_0,\dots ,s_m),z)T(s_m,dz){\mu }_m(d(s_0,\dots ,s_m))\mathrm{.}$ The inner integral is measurable by [F6]. Sections of product-measurable sets are measurable, and countable additivity of the rows of $T$ together with [F7] gives countable additivity of ${\mu }_{m+1}$; its total mass is one. For every measurable prefix set $A\subseteq S^{m+1}$ and $B\in \mathrm{\Sigma }$, ${\mu }_{m+1}(A\times B)={\int }_{A}T(s_m,B){\mu }_m(d(s_0,\dots ,s_m))\mathrm{.}$ Thus this recursion gives a probability law for each finite path, with the stated one-step transition identity; the identity for all prefix events is the displayed formula for arbitrary product-measurable $A$. Kernel integration of a nonnegative measurable test $g$ has the corresponding form ${\int }_{A\times S}g(z){\mu }_{m+1}(d(w,z))={\int }_A{\int }_{S}g(z)T(s_m,dz){\mu }_m(dw),$ first for simple $g$ and then by [F7]. These identities are exactly the finite-horizon conditional transition and expectation rules used below. Kernel compositions used below are kernels as well: iterating $(K_1{K}_2)(x,A)=\int K_2(y,A)K_1(x,dy)$ preserves measurable evaluations by [F6] and countable additivity by [F7]. This applies to probability kernels and finite subprobability kernels.

Fix any $\gamma$. For $r\ge 1$, set $V_r=V\wedge r$. By [F2], $\int (P_{\gamma }{V}_r-V_r)d\pi =0$. On $C$ the integrand is at most $\lambda v+b$; on $C^c\cap \{V\le r\}$ it is at most $-(1-\lambda )V$; and on $C^c\cap \{V>r\}$ it is at most zero, because $P_{\gamma }{V}_r\le \min (P_{\gamma }V,r)$. Hence $(1-\lambda ){\int }_{C^c\cap \{V\le r\}}Vd\pi \le (\lambda v+b)\pi (C)\le \lambda v+b\mathrm{.}$ Letting $r\to \mathrm{\infty }$ by [F7] gives the uniform finite bound $\pi V\le v+(\lambda v+b)\mathrm{/}(1-\lambda )=:K_{\pi }$.

Put ${\lambda }^{\mathrm{\prime }}=(1+\lambda )\mathrm{/}2$ and $c=b\mathrm{/}(1-{\lambda }^{\mathrm{\prime }})$. Choose $d\ge v$ so $2c\mathrm{/}(d+1)<1\mathrm{/}4$, then choose $N\ge 1$ with $d({\lambda }^{\mathrm{\prime }}{)}^N\le 1\mathrm{/}2$, and finally choose $L>N+1$ with $({\lambda }^{\mathrm{\prime }}{)}^L<1\mathrm{/}4$. Let $D=\{x:V(x)\le d\}$. For fixed $\gamma$, the killed subprobability kernel $K_{\gamma }(x,A)=1_{C^c}(x)P_{\gamma }(x,A)$ satisfies $K_{\gamma }V\le {\lambda }^{\mathrm{\prime }}V$. To make its finite paths explicit, adjoin a cemetery point $†$ and equip $\bar{\mathsf{X}}=\mathsf{X}\bigsqcup \{†\}$ with $\bar{\mathcal{X}}=\{A,A\cup \{†\}:A\in \mathcal{X}\}$. Define the probability kernel ${\bar{K}}_{\gamma }$ on this measurable space by ${\bar{K}}_{\gamma }(x,A)=K_{\gamma }(x,A\cap \mathsf{X})+1_C(x)1_{\{†\in A\}}$ for $x\in \mathsf{X}$, and ${\bar{K}}_{\gamma }(†,A)=1_{\{†\in A\}}$. This is measurable: the first term is a kernel evaluation, the second is measurable, and each row has mass one. Step 1.1 constructs its finite path laws. Let $\bar{V}=V$ on $\mathsf{X}$ and $\bar{V}(†)=0$; then $\bar{V}$ is $\bar{\mathcal{X}}$-measurable, ${\bar{K}}_{\gamma }\bar{V}=K_{\gamma }V$ on $\mathsf{X}$, ${\bar{K}}_{\gamma }\bar{V}(†)=0$, and by iteration ${\bar{K}}_{\gamma }^{N+1}\bar{V}(x)=K_{\gamma }^{N+1}V(x)$. The event that the killed path is in $\mathsf{X}$ after $N+1$ transitions has probability $K_{\gamma }^{N+1}1(x)$. Under the finite $P_{\gamma }$-path law from step 1.1, the same recursive formula inserts $1_{C^c}$ at each current state, so for ${\tau }_C=\inf \{m\ge 0:X_m\in C\}$ one has ${\mathbb{P}}_x({\tau }_C>N)=K_{\gamma }^{N+1}1(x)$. ${\mathbb{P}}_x({\tau }_C>N)=K_{\gamma }^{N+1}1(x)\le K_{\gamma }^{N+1}V(x)\le ({\lambda }^{\mathrm{\prime }}{)}^{N+1}V(x)\le 1\mathrm{/}2$ for every $x\in D$. Hence ${\mathbb{P}}_x({\tau }_C\le N)\ge 1\mathrm{/}2$.

Since ${\nu }_{\gamma }(C)=1$, the minorization gives ${\nu }_{\gamma }{P}_{\gamma }\ge \delta {\nu }_{\gamma }$, and induction gives ${\nu }_{\gamma }{P}_{\gamma }^q\ge {\delta }^q{\nu }_{\gamma }$ for every $q\ge 0$. Split the $L$-step transition according to the first hit time $t\le N$ of $C$. From a state in $C$, the first step minorizes by $\delta {\nu }_{\gamma }$ and the remaining $L-t-1$ steps preserve at least ${\delta }^{L-t-1}{\nu }_{\gamma }$. Hence, for every $x\in D$ and measurable $A$, $P_{\gamma }^L(x,A)\ge {\sum }_{t=0}^N{\mathbb{P}}_x({\tau }_C=t){\delta }^{L-t}{\nu }_{\gamma }(A)\ge \frac{{\delta }^L}{2}{\nu }_{\gamma }(A)\mathrm{.}$ Thus $D$ is one-step small for $Q_{\gamma }=P_{\gamma }^L$, with common $ϵ={\delta }^L\mathrm{/}2$.

Iterating $P_{\gamma }V\le \lambda V+b{1}_C\le {\lambda }^{\mathrm{\prime }}V+b$ gives $Q_{\gamma }V\le ({\lambda }^{\mathrm{\prime }}{)}^{L}V+c$. Put $h(x,y)=(V(x)+V(y))\mathrm{/}2$. Outside $D\times D$, at least one coordinate has $V>d$ and the other has $V\ge 1$, so $(Q_{\gamma }\otimes Q_{\gamma })h(x,y)\le ({\lambda }^{\mathrm{\prime }}{)}^{L}h(x,y)+c\le ah(x,y),a:=({\lambda }^{\mathrm{\prime }}{)}^L+\frac{2c}{d+1}<1.$ This $a$ is independent of $\gamma$.

For $x\in D$, $Q_{\gamma }V(x)\le d+c$. The residual probability $R_{\gamma ,x}=(Q_{\gamma }(x,\cdot )-ϵ{\nu }_{\gamma })\mathrm{/}(1-ϵ)$ is well-defined by step 3.1 and satisfies $R_{\gamma ,x}V\le (d+c)\mathrm{/}(1-ϵ)$. Consequently $R_{\gamma ,x}\otimes R_{\gamma ,y}(h)\le H:=(d+c)\mathrm{/}(1-ϵ)$ for $x,y\in D$. All constants here are independent of $\gamma$.

Fix $\gamma$. Let $\mathrm{\Delta }(z)=(z,z)$; this map from $(\mathsf{X},\mathcal{X})$ to $({\mathsf{X}}^2,\mathcal{X}\otimes \mathcal{X})$ is measurable, since inverse images of rectangles are measurable intersections. Write ${\mathrm{\Delta }}_{\ast }\eta (E)=\eta ({\mathrm{\Delta }}^{-1}(E))$ for the image of a measure $\eta$. Extend the residual rows to all $x\in \mathsf{X}$ by setting $R_x=(Q_{\gamma }(x,\cdot )-ϵ{\nu }_{\gamma })\mathrm{/}(1-ϵ)$ on $D$ and $R_x=\pi$ on $D^c$; this is a probability kernel by step 3.1 and measurable piecewise definition. On $\mathsf{S}={\mathsf{X}}^2\times \{0,1\}$, for a measurable $E\subseteq \mathsf{S}$ write $E_i=\{(u,v):(u,v,i)\in E\}$. Define a transition $T_{\gamma }$ as follows: - from $((x,y),0)$ with $(x,y)\mathrm{\notin }{D}^2$, its row on flag $0$ is $Q_{\gamma }(x,\cdot )\otimes Q_{\gamma }(y,\cdot )$; - from $((x,y),0)$ with $(x,y)\in D^2$, its row is $(1-ϵ)(R_x\otimes R_y)$ on flag $0$ plus $ϵ{\mathrm{\Delta }}_{\ast }{\nu }_{\gamma }$ on flag $1$; - from $((x,y),1)$, its row is ${\mathrm{\Delta }}_{\ast }{Q}_{\gamma }(x,\cdot )$ on flag $1$. Here each $E_i$ is measurable by sectioning the finite flag coordinate, and the displayed measures on ${\mathsf{X}}^2$ are placed on their indicated flag sections. The maps $(x,y)\mapsto Q_{\gamma }(x,A)$ and $(x,y)\mapsto Q_{\gamma }(y,A)$ (and the analogous maps for $R$) are measurable by the coordinate projections, so [F5] gives the two product-kernel rows. The image-kernel rows are measurable by measurability of $\mathrm{\Delta }$ and of $Q_{\gamma }(x,A)$. Since $D^2$ is measurable, the three cases define a measurable probability kernel on $\mathsf{S}$. At flag $0$, each coordinate marginal is its corresponding $Q_{\gamma }$ row, because on $D$ one has $ϵ{\nu }_{\gamma }+(1-ϵ)R_x=Q_{\gamma }(x,\cdot )$. At flag $1$ the coordinates coincide on every reachable state and both then advance with $Q_{\gamma }$. Applying the finite-horizon construction in step 1.1 to $T_{\gamma }$ defines the finite path laws used below. Starting from $B_0=0$, once $B_k=1$ the coordinates remain equal; $\{B_k=1\}$ is measurable and on it $X_k=Y_k$.

Let $T=\inf \{m\ge 1:B_m=1\}$ and let $N_k$ count failed split attempts in the first $k$ transitions. Choose $B\ge \max \{1,(1-ϵ)H\mathrm{/}a\}$ and define $Z_k=a^{-k}{B}^{-N_k}h(X_k,Y_k)1_{\{T>k\}}\mathrm{.}$ For each finite horizon, the coordinate process under its path law from step 1.1 is a nonnegative supermartingale with respect to its coordinate filtration: on $\{T>k\}$ an outside-$D\times D$ update contracts expected $h$ by step 3.2 and leaves the flag and failure count unchanged; on $D\times D$ a successful split makes the indicator zero, while the failed-split contribution has ratio at most $(1-ϵ)H\mathrm{/}(aBh(X_k,Y_k))\le 1$ because $h\ge 1$. Since $T\ge 1$, $Z_0=h(x,y)$, and therefore ${\mathbb{E}}_{x,y}{Z}_k\le h(x,y)$ for every finite $k$.

For every integer $j\ge 1$, the probability of at least $j$ failed split attempts is at most $(1-ϵ{)}^j$, by conditioning successively at the first $j$ attempts. On $\{T>k,N_k<j\}$, $Z_k\ge a^{-k}{B}^{-(j-1)}$, so Markov's inequality [F8] gives ${\mathbb{P}}_{x,y}(T>k)\le (1-ϵ{)}^j+a^k{B}^{j-1}h(x,y)\mathrm{.}$ Choose $\theta >0$ with $a{B}^{\theta }<1$ and take $j=\max (1,\lfloor \theta k\rfloor )$. Both terms are bounded by $M_{0}h(x,y){\rho }_0^k$ for constants $M_0<\mathrm{\infty }$, $0<{\rho }_0<1$ determined only by $a,B,ϵ$. On the measurable event $\{T\le k\}$ the flagged chains agree, so [F4] yields $\parallel Q_{\gamma }^k(x,\cdot )-Q_{\gamma }^k(y,\cdot ){\parallel }_{\mathrm{T}\mathrm{V}}\le M_{0}h(x,y){\rho }_0^k\mathrm{.}$

For each finite $k$, start the flagged path law with initial measure ${\delta }_x\otimes \pi \otimes {\delta }_0$ on $\mathsf{S}$, which exists by [F5] and step 1.1. The second coordinate has initial law $\pi$ and transition marginal $Q_{\gamma }$, so invariance gives $Y_k\sim \pi$. Integrating step 6.1 over $Y_0$ and using step 1.2 yields $\parallel Q_{\gamma }^k(x,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le \frac{M_0}{2}(V(x)+\pi V){\rho }_0^k\le \frac{M_0}{2}(1+K_{\pi })V(x){\rho }_0^k\mathrm{.}$ This bound is uniform in $\gamma$.

Write $n=Lk+s$ with $0\le s<L$. By kernel contraction and $\pi P_{\gamma }^s=\pi$, $\parallel P_{\gamma }^n(x,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le \parallel Q_{\gamma }^k(x,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\mathrm{.}$ Set $\rho ={\rho }_0^{1\mathrm{/}L}$ and enlarge the constant by ${\rho }^{-(L-1)}$. The resulting $M$ is finite and depends only on $v,\delta ,\lambda ,b$, proving the stated bound.

Since $0\le D_n\le 1$ and $D_n\to 0$ in probability, for each fixed $j\ge 0$ we have $\mathbb{E}{D}_{n+j}\to 0$: for any $t>0$, $\mathbb{E}{D}_{n+j}\le t+\mathbb{P}(D_{n+j}>t)$; first let $n\to \mathrm{\infty }$ and then $t\downarrow 0$.

Assume simultaneous uniform ergodicity and fix a desired tolerance $\eta >0$. Choose $N=N(\eta \mathrm{/}2)$ as in alternative 1. For the frozen mixture $Q_{n,N}$ from [F6], every state and parameter has $\parallel P_{{\mathrm{\Gamma }}_n}^N(X_n,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le \eta \mathrm{/}2$, so convexity of the setwise supremum gives $\parallel Q_{n,N}-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le \eta \mathrm{/}2$.

Now assume containment. Fix $\eta >0$, take $ϵ=\delta =\eta \mathrm{/}3$, and choose $N$ from alternative 2. On the event $M_{ϵ}(X_n,{\mathrm{\Gamma }}_n)\le N$, the definition gives an iterate $m\le N$ within $ϵ$ of $\pi$; [F5] propagates this bound to the $N$th iterate. On the complementary event total variation is at most one. Therefore the frozen mixture satisfies $\parallel Q_{n,N}-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le ϵ+\delta =2\eta \mathrm{/}3$ for every $n$.

For this fixed $N$, [F6] and step 1.1 imply $\parallel \mathcal{L}(X_{n+N})-Q_{n,N}{\parallel }_{\mathrm{T}\mathrm{V}}\to 0$, since its upper bound is a finite sum of expectations tending to zero. The triangle inequality and step 1.2 yield ${\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}\parallel \mathcal{L}(X_{n+N})-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le \eta \mathrm{/}2$. As $n+N$ ranges over all sufficiently large times and $\eta >0$ is arbitrary, the asserted convergence follows in alternative 1.

The same fixed-block bound [F6] tends to zero by step 1.1. The triangle inequality gives ${\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}\parallel \mathcal{L}(X_{n+N})-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le 2\eta \mathrm{/}3<\eta$. Again $N$ is fixed and $\eta$ is arbitrary, proving the asserted convergence in alternative 2.

For each $r$, the conditional transition rule [F1] and the drift inequality [F3] give $\mathbb{E}[(V\wedge r)(X_{n+1})\mid {\mathcal{F}}_n]\le \lambda V(X_n)+b$. Take expectations and let $r\to \mathrm{\infty }$ by [F6]; assuming $\mathbb{E}V(X_n)<\mathrm{\infty }$, this gives $\mathbb{E}V(X_{n+1})\le \lambda \mathbb{E}V(X_n)+b$. Starting from the finite initial moment and iterating yields ${\sup }_{n\ge 0}\mathbb{E}V(X_n)\le \mathbb{E}V(X_0)+\frac{b}{1-\lambda }=:K<\mathrm{\infty }\mathrm{.}$

Fix $ϵ,\delta >0$. Choose $R\ge K\mathrm{/}\delta$ and then an integer $N\ge 1$ such that $MR{\rho }^N\le ϵ$. Markov's inequality [F7] and the moment bound in step 1.1 give $\mathbb{P}(V(X_n)>R)\le \delta$ for every $n$. On the complementary event [F4] gives $\parallel P_{{\mathrm{\Gamma }}_n}^N(X_n,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le ϵ$, so $M_{ϵ}(X_n,{\mathrm{\Gamma }}_n)\le N$. This proves containment as defined in [F2].

Diminishing adaptation is [F1], and containment is step 2.1. The containment branch of [F5] therefore gives $\parallel \mathcal{L}(X_n)-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\to 0$.