Diminishing adaptation and uniform ergodicity need not give a strong law

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.