Adaptive MCMC convergence limits — Examples

Since $\mathsf{X}$ and $\mathrm{\Gamma }$ are finite discrete spaces, all kernel evaluations are jointly measurable. Every displayed matrix has probability rows, is symmetric, and has column sums one. Thus each is a probability kernel and $\pi P_i=\pi$ by [F1] and [F3]. For a two-state symmetric kernel with flip probability $q$, $({\delta }_x-\pi )P=(1-2q)({\delta }_x-\pi )$; induction gives $P^m(x,\cdot )-\pi =(1-2q{)}^m({\delta }_x-\pi )$. For $P_0$ and $P_1$, $\mathrm{\mid }1-2q\mathrm{\mid }=4\mathrm{/}5$, while $P_2=\mathrm{\Pi }$ reaches $\pi$ in one step. Since $\parallel {\delta }_x-\pi {\parallel }_{\mathrm{T}\mathrm{V}}=1\mathrm{/}2$ by [F4], ${\sup }_{x\in \mathsf{X},i\in \{0,1,2\}}\parallel P_i^m(x,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\le \frac{1}{2}(4\mathrm{/}5{)}^m(m\ge 0)\mathrm{.}$ The family is simultaneously uniformly ergodic.

For $k\in \mathbb{N}$, let $L_k=2^{2^k}$ and $s_k={\sum }_{j<k}{L}_j$, the number of transitions before block $k$. Since ${\sum }_{j<k}{L}_j\le k{2}^{2^{k-1}}$, $\frac{s_k}{L_k}\le k{2}^{-2^{k-1}}⟶0.$

For each $k$, equip the finite space ${\mathrm{\Omega }}_k=\{0,\dots ,k\}\times \{1,\dots ,10{\}}^{L_k}$ with its uniform probability measure. Write a coordinate as $(J_k,U_{k,0},\dots ,U_{k,L_k-1})$ and put $I_k=1_{\{J_k=0\}}$. Direct counting gives $\mathbb{P}(I_k=1)=1\mathrm{/}(k+1)$; conditional on any value of $J_k$, the $U_{k,t}$ are independent and uniform on $\{1,\dots ,10\}$, with a law not depending on $J_k$. The countable product over $k\in \mathbb{N}$ exists by [F6] under [A1]–[A2].

In block $k$, for its first transition $n=s_k$ set ${\mathrm{\Gamma }}_n=2$ and use $U_{k,0}$ to draw from $P_2$ (the next state is $0$ iff $U_{k,0}\le 5$). For $n=s_k+t$ with $1\le t<L_k$, set ${\mathrm{\Gamma }}_n=2$ if $I_k=0$; if $I_k=1$, set ${\mathrm{\Gamma }}_n=0$ when $X_n=0$ and ${\mathrm{\Gamma }}_n=1$ when $X_n=1$. Use $U_{k,t}$ to sample the selected matrix row: for $P_0$ use thresholds $9$ and $1$ for rows $0$ and $1$ respectively, for $P_1$ use thresholds $1$ and $9$, and for $P_2$ use threshold $5$; the next state is $0$ exactly when $U_{k,t}$ is at most the row's threshold. This recursively defines measurable $X_n$ and ${\mathrm{\Gamma }}_n$. Each next $U_{k,t}$ is independent of the gate and earlier block coordinates by [F2] and the finite product counting in step 1.3; different blocks have the product marginals in [F6]. Therefore conditional on the history, $X_{n+1}$ has law $P_{{\mathrm{\Gamma }}_n}(X_n,\cdot )$, so this is an adaptive MCMC process with the stated kernel family.

If $I_k=0$, every parameter in block $k$ is $2$, and the next block also starts with parameter $2$; hence $D_n=0$ at every transition whose current block has gate zero. If $I_k=1$, then $D_n\le 1$. For each $n$ in block $k$, $\mathbb{P}(D_n>0)\le \mathbb{P}(I_k=1)=1\mathrm{/}(k+1)⟶0$ as $n\to \mathrm{\infty }$, because each block is finite and its index tends to infinity. Thus $D_n\to 0$ in probability by [F5].

Conditional on $I_k=1$, for each $1\le t<L_k$ the active rule uses $P_0$ from state $0$ and $P_1$ from state $1$. In either case the next state is $0$ iff $U_{k,t}\le 9$. Hence $Z_{k,t}:=1_{\{X_{s_k+t+1}=0\}}=1_{\{U_{k,t}\le 9\}}$ are independent Bernoulli variables with success probability $p=9\mathrm{/}10$.

Put $N_k=L_k-1$ and ${\bar{Z}}_k=N_k^{-1}{\sum }_{t=1}^{N_k}{Z}_{k,t}$. Under $I_k=1$, each centered variable $Z_{k,t}-p$ has mean zero and second moment $p(1-p)=9\mathrm{/}100$; distinct centered variables have zero product expectation by the finite product law of the $U_{k,t}$. Expanding the square and using [F8]–[F9] gives $\mathbb{E}[({\bar{Z}}_k-p{)}^2\mid I_k=1]=\frac{9}{100N_k}\mathrm{.}$ Since ${\bar{Z}}_k<4\mathrm{/}5$ implies $({\bar{Z}}_k-p{)}^2>1\mathrm{/}100$, Markov's inequality [F10] yields $\mathbb{P}({\bar{Z}}_k<4\mathrm{/}5\mid I_k=1)\le \frac{9}{N_k}\mathrm{.}$

Let $H_k=\{I_k=1,{\bar{Z}}_k\ge 4\mathrm{/}5\}$. From steps 1.3 and 4.1, $\mathbb{P}(H_k)\ge \frac{1}{k+1}(1-\frac{9}{L_k-1})\ge \frac{1}{2(k+1)}$ for all sufficiently large $k$, so ${\sum }_k\mathbb{P}(H_k)=\mathrm{\infty }$. Each $H_k$ is a function only of coordinate ${\mathrm{\Omega }}_k$, so [F6] makes these events independent. For any fixed $K$, $\mathbb{P}\text{\hspace{0.17em}⁣}\left({\bigcap }_{k=K}^m{H}_k^c\right)={\prod }_{k=K}^m(1-\mathbb{P}(H_k))\le \exp \text{\hspace{0.17em}⁣}(-{\sum }_{k=K}^m\mathbb{P}(H_k))⟶0.$ Thus the probability of no $H_k$ after $K$ is zero; [F7] applied to the countable union over $K$ shows that infinitely many $H_k$ occur almost surely.

At the endpoint $n_k=s_k+L_k$ of any block with $H_k$, the active outputs $X_{s_k+2},\dots ,X_{s_k+L_k}$ contain at least $(4\mathrm{/}5)(L_k-1)$ zeros. Therefore $\frac{1}{n_k}{\sum }_{j=1}^{n_k}{1}_{\{X_j=0\}}\ge \frac{(4\mathrm{/}5)(L_k-1)}{s_k+L_k}⟶\frac{4}{5}$ along the infinitely many such blocks, by step 1.2. But $\pi (1_{\{0\}})=1\mathrm{/}2$. The strong law fails almost surely despite simultaneous uniform ergodicity and diminishing adaptation.

Each row of $P_{\gamma }$ is a probability vector, and for fixed $x$ and $A$ the evaluation $P_{\gamma }(x,A)$ is affine in $\gamma$. Hence the family is jointly measurable on the stated finite discrete state space and Borel parameter space. Also $\pi P_{\gamma }=(1-\gamma )\pi +\gamma \pi =\pi$. The same projection identity ${\mathrm{\Pi }}^2=\mathrm{\Pi }$ gives $P_{\gamma }^m(x,\cdot )=(1-\gamma {)}^m{\delta }_x+(1-(1-\gamma {)}^m)\pi ,$ so $\parallel P_{\gamma }^m(x,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}=(1-\gamma {)}^m\mathrm{/}2\to 0$ for each fixed $\gamma$. Thus all individual kernels are ergodic for the common invariant target.

The difference of two successive rows is $({\mathrm{\Gamma }}_{n+1}-{\mathrm{\Gamma }}_n)(\pi -{\delta }_x)$, so $D_n=\mathrm{\mid }{\mathrm{\Gamma }}_{n+1}-{\mathrm{\Gamma }}_n\mathrm{\mid }\mathrm{/}2\to 0$.

Let $r_0=1$ and $r_n={\prod }_{j=0}^{n-1}(1-{\mathrm{\Gamma }}_j)$. The law recursion ${\mu }_{n+1}={\mu }_n{P}_{{\mathrm{\Gamma }}_n}$ gives ${\mu }_n=r_n{\delta }_0+(1-r_n)\pi$. Since ${\sum }_j{\mathrm{\Gamma }}_j=1\mathrm{/}2$ and ${\mathrm{\Gamma }}_j\le 1\mathrm{/}4$, the elementary bound $\log (1-u)\ge -2u$ for $0\le u\le 1\mathrm{/}2$ yields $r_n\ge \exp (-2{\sum }_j{\mathrm{\Gamma }}_j)=e^{-1}$. Hence $\parallel {\mu }_n-\pi {\parallel }_{\mathrm{T}\mathrm{V}}=r_n\mathrm{/}2\ge e^{-1}\mathrm{/}2$, so the marginal law does not converge to $\pi$.

For $ϵ=1\mathrm{/}4$, the formula in step 1.1 shows $M_{ϵ}(x,{\mathrm{\Gamma }}_n)\to \mathrm{\infty }$ for both states as ${\mathrm{\Gamma }}_n\to 0$. Thus for every finite $N$, the probability of $M_{ϵ}(X_n,{\mathrm{\Gamma }}_n)\le N$ is eventually zero, contradicting containment in [F5].

The matrix of $P_{\gamma }$ is $\left(\begin{array}{cc}1-\gamma \mathrm{/}2& \gamma \mathrm{/}2\\ \gamma \mathrm{/}2& 1-\gamma \mathrm{/}2\end{array}\right)\mathrm{.}$ Its entries are continuous in $\gamma$, so the family is jointly measurable on the stated spaces; its rows are probability vectors by $0\le \gamma \le 1$ and [F1]. The matrix is symmetric, and $\pi$ assigns equal mass to both states, so the four joint-flow atoms are symmetric under coordinate swap. Thus $P_{\gamma }$ is reversible by [F2], and $\pi$ is invariant by [F3].

The kernels satisfy $P_{{\gamma }^{\mathrm{\prime }}}(x,\cdot )-P_{\gamma }(x,\cdot )=({\gamma }^{\mathrm{\prime }}-\gamma )(\pi -{\delta }_x)$, so $D_n=\mathrm{\mid }{\mathrm{\Gamma }}_{n+1}-{\mathrm{\Gamma }}_n\mathrm{\mid }\mathrm{/}2\to 0$. This is diminishing adaptation by [F5].

Since ${\mathrm{\Pi }}^2=\mathrm{\Pi }$ and $I\mathrm{\Pi }=\mathrm{\Pi }I=\mathrm{\Pi }$, induction gives $P_{\gamma }^m=(1-\gamma {)}^{m}I+(1-(1-\gamma {)}^m)\mathrm{\Pi }\mathrm{.}$ For either state $x$, $\parallel {\delta }_x-\pi {\parallel }_{\mathrm{T}\mathrm{V}}=1\mathrm{/}2$, so $\parallel P_{\gamma }^m(x,\cdot )-\pi {\parallel }_{\mathrm{T}\mathrm{V}}=(1-\gamma {)}^m\mathrm{/}2\le 2^{-m-1}$ uniformly in $x$ and $\gamma \in [1\mathrm{/}2,1]$. Therefore the family is simultaneously uniformly ergodic.

Steps 2.1 and 1.2 verify the two hypotheses in alternative 1 of [F6]. Hence $\parallel \mathcal{L}(X_n)-\pi {\parallel }_{\mathrm{T}\mathrm{V}}\to 0$ for every initial state.