3.1. Definitions and notation

Let $\pi$ be a probability measure on a measurable space $({\mathcal{X}}, \Sigma)$. We make considerable use of the following norms on signed measures and their corresponding Banach spaces:

\begin{align*} { \Vert {\lambda} \Vert_{\text{TV}}} & = \sup\limits_{A\in\Sigma} \vert {{\lambda(A)}} \vert , & \mathcal{M}(\Sigma) & = \{ {\text{bounded signed measures on }({\mathcal{X}}, \Sigma)} \}, \\ \Vert {{\lambda}}\Vert_{L_2(\pi)} & = \left( {\int\left({{\frac{{\textrm{d}}\lambda}{{\textrm{d}}\pi}}}\right)^2 {\textrm{d}}\pi} \right)^{1/2}, & L_2(\pi) & = \{ {{\nu\ll\pi \,{:}\, \Vert {{\nu}}\Vert_{L_2(\pi)} <\infty }} \},\\ \Vert {{\cdot}}\Vert_{L_{2,0}(\pi)} & = \Vert {{\cdot}}\Vert_{L_2(\pi)} \vert_{{L_{2,0}(\pi)}}, & L_{2,0}(\pi) & = \{ {\nu\in L_2(\pi) \,{:}\,\nu({\mathcal{X}}) = 0} \},\\ \Vert {{\lambda}}\Vert_{L_1(\pi)} & = \int \vert {{{\frac{{\textrm{d}}\lambda}{{\textrm{d}}\pi}}}} \vert {\textrm{d}}\pi, & L_{1}(\pi) & = \{ {\nu\ll\pi \,{:}\, \Vert {{\nu}}\Vert_{L_1(\pi)} <\infty} \},\\ \Vert {\lambda} \Vert_{L_{\infty}(\pi)} & =\text{ess}\sup\limits_{X\sim\pi}{\frac{{\textrm{d}}\lambda}{{\textrm{d}}\pi}}(X), & L_{\infty}(\pi) & = \left\{ {{\nu\ll\pi \,{:}\, (\exists b>0)\left({ \vert {{{\frac{{\textrm{d}}\nu}{{\textrm{d}}\pi}}}} \vert < b \quad \pi\text{a.e.}}\right)}} \right\}. \end{align*}

Note that $L_{2,0}(\pi)$ is a complete subspace of $L_2(\pi)$. Let

\begin{align*}\mathcal{M}_{+,1} = \{ {\lambda\in\mathcal{M}\,{:}\, [\forall A \in \Sigma\quad \lambda(A)\geq 0] \ \text{and}\ [\lambda({\mathcal{X}}) = 1]} \}\end{align*}

be the set of probability measures on $({\mathcal{X}}, \Sigma )$. Note that for any probability measure $\pi$, $L_\infty(\pi)\subset L_2(\pi) \subset L_1(\pi) \subset \mathcal{M}(\Sigma)$, though in general they are not complete subspaces of each other when their corresponding norms are not equivalent. For a norm $ \Vert {\cdot} \Vert$ on a vector space, we also write $ \Vert {\cdot} \Vert$ for the corresponding operator norm on the space of bounded linear operators from V to itself, $\mathcal{B}(V)$.

3.2. Assumptions

We assume throughout that P is the transition kernel for a Markov chain on a countably generated state space $\mathcal{X}$ with $\sigma$-algebra $\Sigma$, which is reversible with respect to a stationary probability measure $\pi$, and is $\pi$-irreducible and aperiodic. We call the Markov chain induced by P the ‘original’ chain. The $\pi$-reversibility of P makes it natural to work in $L_2(\pi)$, since in this case P is a self-adjoint linear operator on a Hilbert space. This allows us access to the rich, elegant, and mature spectral theory of such operators. See for example [33, Chapter 12] and [9, Chapter 22]. We further assume that P is $L_2(\pi)$-GE with factor $0<(1-\alpha)<1$. Equivalent definitions of $L_2(\pi)$-GE are given in Proposition 2. This assumption is weaker than the Doeblin condition used by [Reference Johndrow, Mattingly, Mukherjee and Dunson18], which implies uniform ergodicity.

Next, we assume that $P_\epsilon$ is a second, ‘perturbed’ transition kernel, such that

\begin{equation*} \Vert {{P-P_\epsilon}}\Vert_{L_2(\pi)} \leq \epsilon\end{equation*}

for some fixed $\epsilon>0$, and that

\begin{equation*}P_\epsilon \vert_{{L_2(\pi)}} \in \mathcal{B}(L_2(\pi)),\end{equation*}

i.e. that the perturbed transition kernel maps $L_2(\pi)$ measures to $L_2(\pi)$ measures. The norm condition quantifies the intuition that the perturbation is ‘small’. We assume that $P_\epsilon$ is $\pi$-irreducible and aperiodic. We demonstrate (in Theorem 1) that under these assumptions $P_\epsilon$ has a unique stationary distribution, denoted by $\pi_\epsilon$, with $\pi_\epsilon\in L_2(\pi)$.

Note that when $\mu\in L_1(\pi)$ we have

\begin{equation*}{ \Vert {\mu-\pi} \Vert_{\text{TV}}} =\frac{1}{2} \Vert {{\mu-\pi}}\Vert_{L_1(\pi)} .\end{equation*}

On the other hand, ${ \Vert {\cdot} \Vert_{\text{TV}}}$ applies to all bounded measures, while $ \Vert {{\cdot}}\Vert_{L_1(\pi)} $ applies only to the subspace of $L_1(\pi)$ measures. Note also that if $\pi \sim \pi_\epsilon$ (the two measures are mutually absolutely continuous), then $L_1(\pi)$ and $L_1(\pi_\epsilon)$ are equal as spaces and their norms are always equal, so in this case we need not distinguish between them.

To summarize, we assume the following.

The assumption that $P_\epsilon: L_2(\pi)\to L_2(\pi)$ and that $ \Vert {{P_\epsilon}}\Vert_{L_2(\pi)} <\infty$ may seem difficult to verify. However, the following proposition shows us that it is satisfied for $P_\epsilon$ constructed based on the Metropolis–Hastings algorithm with suitable jump kernels. As long as the jump kernel, J, has $ \Vert {{J}}\Vert_{L_2(\pi)} <\infty$, the assumption will be satisfied. Therefore, this assumption is not excessively restrictive for MCMC applications. The jump kernel J describes the conditional distribution of a new point in the chain proposed from x given that the proposal is accepted; it is related to the proposal kernel, Q, by $\alpha(x) J(x,A) = \int_A a(x,y) Q(x, dy), $ where a(x, y) is the Metropolis–Hastings acceptance ratio and $\alpha(x) = \int_{\mathcal{X}} a(x,y) Q(x, dy)$ is the implied local jump-intensity.

Proposition 1. If $P_\epsilon(x,\cdot) = (1-\alpha(x))\delta_x +\alpha(x)J(x,\cdot)$ with $\alpha\,{:}{\mathcal{X}}\to[0,1]$ measurable, and $J \,{:}\, L_2(\pi)\to L_2(\pi)$ and $ \Vert {{J}}\Vert_{L_2(\pi)} <\infty$, then

(2) \begin{equation}\begin{aligned} \Vert {{P_\epsilon}}\Vert_{L_2(\pi)} \leq 1 + \Vert {{J}}\Vert_{L_2(\pi)} .\end{aligned}\end{equation}

Proof of Proposition 1. Consider the operator A on $L_2(\pi)$ given by the formula $[\nu A](C) = \int_C \alpha(x)\nu(dx)$ for all measurable sets C. Its adjoint, $A'$, is given by the formula $[A' f] (x) = \alpha(x) f(x)$ for all $x \in {\mathcal{X}}$ and $f\in L_2^{\prime}(\pi)$. Since $\alpha \,{:}\, {\mathcal{X}} \to [0,1]$, we have $A'\,{:}\,L_2^{\prime}(\pi)\to L_2^{\prime}(\pi)$ with $ \Vert {{A'}}\Vert_{L^{\prime}_2(\pi)} \leq 1$. Thus $A \,{:}\, L_2(\pi)\to L_2(\pi)$ with $ \Vert {{A}}\Vert_{L_2(\pi)} \leq 1 $. The same also holds for $I-A$. Now, $P_\epsilon = A + (I-A) J$, so

\begin{align*} \Vert {{P_\epsilon}}\Vert_{L_2(\pi)} \leq 1 + \Vert {{J}}\Vert_{L_2(\pi)} .\\[-35pt]\end{align*}

Verifying that $ \Vert {P-P_\epsilon}\Vert_{L_2(\pi)} $ is finite and sufficiently small will be the main analytic burden faced when trying to apply our results to more general settings. The development of further tools to determine whether $ \Vert {P-P_\epsilon}\Vert_{L_2(\pi)} $ is finite and to bound it quantitatively would be an interesting line of future research.

3.3. Convergence rates and closeness of stationary distributions

Theorem 1. (Geometric ergodicity of the perturbed chain and closeness of the stationary distributions in original norm, $L_2(\pi)$) Under the assumptions of Section 3.2, if in addition $\epsilon<\alpha$, then $\pi_\epsilon\in L_2(\pi)$,

\begin{align*}0\leq \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} \leq\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}} \ ,\end{align*}

$P_\epsilon$ is $L_2(\pi)$-geometrically ergodic with factor $1-(\alpha-\epsilon)$, and for any initial probability measure $\mu\in L_2(\pi)$,

\begin{align*} \Vert { \mu P_\epsilon^n -\pi}\Vert_{L_2(\pi)} & \leq (1-(\alpha-\epsilon))^n \Vert {\mu-\pi_\epsilon}\Vert_{L_2(\pi)} + \frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}} \ .\end{align*}

The proof of this result is the content of Appendix A.1. We follow the derivation in [Reference Johndrow, Mattingly, Mukherjee and Dunson18] with minimal structural modification, though the technicalities must be handled differently and additional theoretical machinery is required. We use the fact that the existence of a spectral gap for the restriction of P to $L_{2,0}(\pi)$ yields an inequality of the same form as the uniform contractivity condition, but in the $L_{2}(\pi)$-norm as opposed to the total variation norm (cf. Theorem 2.1 of [Reference Roberts and Rosenthal29]).

Remark 2. Bounds on the differences between measures in $L_2(\pi)$-norm can be converted into bounds on the total variation distance, since, by Cauchy–Schwarz, for any measure $\lambda$ and any signed measure $\nu \in L_2(\lambda)$, we have

\begin{equation*}{ \Vert {\nu} \Vert_{\text{TV}}} = \frac{1}{2} \Vert {\nu} \Vert_{L_1(\lambda)} \leq \frac{1}{2} \Vert {\nu} \Vert_{L_2(\lambda)}.\end{equation*}

Thus, for example, under the assumptions of Theorem 1,

\begin{align*} { \Vert { \mu P_\epsilon^n -\pi} \Vert_{\text{TV}}}\leq \frac{1}{2} \left[ {(1-(\alpha-\epsilon))^n \Vert {\mu-\pi_\epsilon}\Vert_{L_2(\pi)} + \frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}} \right] . \end{align*}

Similarly, under the assumptions of Theorem 1, we find that $P_\epsilon$ is $(L_2(\pi),{ \Vert {\cdot} \Vert_{\text{TV}}})$-GE with factor $1-(\alpha-\epsilon)$ (see Definition 2 below).

In some situations, such as the computation of mean squared errors in Theorem 5, it may be inconvenient or impossible to use the $L_2(\pi)$ norm when studying some aspects of $P_\epsilon$. The next theorem will allow us to ‘switch’ to other norms which may be more natural for a given task. First, however, we need to introduce one more notion of geometric ergodicity.

P is $(V, \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\cdot} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert)$-geometrically ergodic with factor $\rho$ if there exists $C\,{:}\, V\cap \mathcal{M}_{+,1}\to\mathbb{R}_+$ such that for every $\nu\in V\cap \mathcal{M}_{+,1}$ and for all $n\in\mathbb{N}$,

\begin{align*} \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\nu P^n - \pi} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert\leq C(\nu) \rho^n \ . \end{align*}

The optimal rate for $(V, \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\cdot} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert)$-geometric ergodicity is the infimum over factors for which the above definition holds:

\begin{align*} \rho^\star = \textrm{inf}\left \{{\rho>0\,{:}\, \exists C\,{:}\,V\cap \mathcal{M}_{+,1}\to\mathbb{R}_+ \ \text{s.t.}\ \forall n\in\mathbb{N}, \, \nu\in V\cap \mathcal{M}_{+,1} \quad \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\nu P^n - \pi} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert \leq C(\nu) \rho^n}\} \right.. \end{align*}

We will be interested in this definition for the cases that $V = L_\infty(\pi)$ and $ \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\cdot} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert$ is either $ \Vert {\cdot}\Vert_{L_2(\pi)} $ or $ \Vert {{\cdot}}\Vert_{L_1(\pi)} $.

In Appendix C we give an example where the optimal rates for $L_2(\pi)$-GE and $(L_\infty(\pi), \Vert {\cdot} \Vert_{L_2(\pi)})$-GE are distinct when P is not reversible. If P is $\pi$-reversible then the factors for $L_2(\pi)$-GE, $(L_\infty(\pi), \Vert {\cdot} \Vert_{L_2(\pi)})$-GE, and $(L_\infty(\pi), \Vert {\cdot} \Vert_{L_1(\pi)})$-GE must be the same. This result combines a comment and Theorem 3 of [Reference Roberts and Tweedie32], both stated but not proved. The formal statement of that result and its proof may be found in Appendix D.

Finally, note that by definition $L_2(\pi)$-GE is equivalent to $(L_2(\pi), \Vert {\cdot}\Vert_{L_2(\pi)} )$ with the same coefficient functions and factors, and that a.e.-TV-GE is equivalent to $(D,{ \Vert {\cdot} \Vert_{\text{TV}}})$-GE where we can take $D = \text{span} ( { \{ {\pi} \}\cup \{ {\delta_x\,{:}\, x\in {\mathcal{X}}\setminus{N}, r\in\mathbb{R}} \}} ) $ for some $\pi$-null set N. The null set N can be taken to be the same for all factors $\rho$ by taking the union over the null sets for factors $\rho\in\mathbb{Q}$ (since a countable union of null sets is still null).

Lemma 1. (Characterization of optimal rates for $(V, \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\cdot} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert)$-GE chains) If P is $(V, \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\cdot} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert)$-GE with stationary measure $\pi$, then the optimal rate for $(V, \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\cdot} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert)$-GE is equal to

(3) \begin{equation}\begin{aligned} \sup\limits_{\mu\in V\cap \mathcal{M}_{+,1}} \limsup_{n\to\infty} \vert{\kern-0.25ex{ \vert{\kern-0.25ex{ \vert {\mu P^n -\pi} \vert}\kern-0.25ex}\vert}\kern-0.25ex}\vert^{1/n} \ . \end{aligned}\end{equation}

The proof of this result is found in Appendix D.

Theorem 1 controls the convergence of the perturbed chain $P_\epsilon$ in terms of the ‘original’ norm (from $L_2(\pi)$). We also demonstrate that $P_\epsilon$ is geometrically ergodic in the $L_2(\pi_\epsilon)$ norm, as this would also allow us to use the equivalences in [Reference Roberts and Rosenthal29]. The following two results allow us to transfer the geometric ergodicity of $P_\epsilon$ in $L_2(\pi)$ to other notions of geometric ergodicity. Theorem 3 handles the case that the perturbed kernel is reversible, while Theorem 2 handles both the case that the perturbed kernel is reversible and the case that it is non-reversible.

The proof of this result is found in Appendix A.2.

Example 1. For example, consider perturbations of a Gaussian $\text{AR}(1)$ process. Let $Z_i{\stackrel{{iid}}{\sim{\mathcal{N}}}}(0,\sigma^2)$ and let $W_i{\stackrel{{iid}}\sim{\mu}}$. Take

(4) \begin{equation}\begin{aligned} X_{t+1} | X_t & = (1-\alpha) X_t + Z_{t+1},\\[3pt] X_{t+1}^\epsilon|X_t^\epsilon & = (1-\alpha) X_t^\epsilon + W_{t+1} . \end{aligned}\end{equation}

Then the original chain $ \{ {X_t} \}_{t\in\mathbb{N}}$ is not uniformly ergodic, but it is geometrically ergodic. Hence, the results of [Reference Alquier, Friel, Everitt and Boland1,Reference Johndrow, Mattingly, Mukherjee and Dunson18] do not apply. The stationary measure of the exact chain is

\begin{equation*}\pi\equiv \mathcal{N}(0,\frac{\sigma^2}{\alpha(2-\alpha)}),\end{equation*}

it is reversible, and the rate of geometric ergodicity is $(1-\alpha)$. Note that the perturbed chain, which we will call a $\mu\text{AR}(1)$ process, may not be reversible, and whether it is geometrically ergodic generally depends on the distribution $\mu$.

Now, letting $\phi_{\sigma^2}$ be the $\mathcal{N}(0,\sigma^2)$ density, for any $\mu$ with ${\frac{{\textrm{d}}\mu}{\textrm{d} \phi_{\sigma^2}}}\in [1-\epsilon,1+\epsilon]$,

(5) \begin{equation}\begin{aligned} \Vert {P - P_\epsilon}\Vert_{L_2(\pi)} ^2 & = \int_{-\infty}^\infty \int_{-\infty}^\infty \left( { \frac{\mu(y-(1-\alpha)x)}{\pi(y)} - \frac{\phi_{\sigma^2}(y-(1-\alpha)x)}{\pi(y)}} \right)^2 \pi(y)dy\ \pi(x)dx \\[3pt] & \leq \int_{-\infty}^\infty\int_{-\infty}^\infty \epsilon^2 \left( {\frac{\phi_{\sigma^2}(y-(1-\alpha)x)}{\pi(y)} dy} \right)^2 \pi(y)dy\ \pi(x)dx \\[3pt] & = \epsilon^2 \Vert {P}\Vert_{L_2(\pi)} \\[3pt] & = \epsilon^2. \end{aligned}\end{equation}

Therefore, when $\epsilon<\alpha$ we can extend the geometric ergodicity of the Gaussian AR process to the $\mu-\text{AR}(1)$ process using Theorem 2. We can also bound the discrepancy of the stationary measure of the perturbed chain from that $\mathcal{N}(0,\frac{\sigma^2}{\alpha(2-\alpha)})$ using Theorem 1. The subsequent results, Corollary 1 and Theorem 4 of this section, may also be applied to this example to bound the discrepancy between the marginal distributions of the $\mu\hbox{-}\text{AR}(1)$ from an $\mathcal{N}(0,\frac{\sigma^2}{\alpha(2-\alpha)})$ at any time, as well as the approximation error of the time-averaged law of the $\mu\hbox{-}\text{AR}(1)$ from $\mathcal{N}(0,\frac{\sigma^2}{\alpha(2-\alpha)})$.

The proof of this result is found in Appendix A.2. We turn our attention to bounds on the error of estimation measures of the form $\frac{1}{t} \sum_{k=0}^{t-1} \mu P^k$, and estimates of the form $\frac{1}{t} \sum_{k=0}^{t-1} f(X_k)$. Firstly, when computing Monte Carlo estimates, the bias is controlled by a time-averaged marginal distribution of the form $\frac{1}{t}\sum_{k=0}^{t-1} \mu P_\epsilon^k $. This leads us to the following result.

Theorem 4. (Convergence of time-averaged marginal distributions) Under the assumptions of Section 3.2, suppose $\epsilon<\alpha$ and $\pi_\epsilon\in L_2(\pi)$. Then for any probability distribution $\mu\in L_2(\pi)$,

\begin{align*} \bigg\Vert {\pi -\frac{1}{t}\sum_{k=0}^{t-1} \mu P_\epsilon^k}\bigg\Vert_{L_2(\pi)} & \leq \frac{1-(1-(\alpha-\epsilon))^t}{t(\alpha-\epsilon)} \Vert { \pi_\epsilon-\mu}\Vert_{L_2(\pi)} +\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}.\end{align*}

If additionally $ \Vert {P-P_\epsilon} \Vert_{L_2(\pi_\epsilon)} \leq \varphi$, then the following hold:

1. (i) If $P_\epsilon$ is $\pi_\epsilon$-reversible and $\varphi<\alpha-\epsilon$, then

   \begin{align*} \bigg\Vert {{\pi -\frac{1}{t}\sum_{k=0}^{t-1} \mu P_\epsilon^k}}\bigg\Vert_{L_2(\pi_\epsilon)} &\leq \frac{1-(1-(\alpha-\epsilon))^t}{t(\alpha-\epsilon)} \Vert {{ \pi_\epsilon-\mu}}\Vert_{L_2(\pi_\epsilon)} +\frac{\varphi}{\sqrt{(\alpha-\epsilon)^2-\varphi^2}} \ .\end{align*}

2. (ii) If $\pi\in L_\infty(\pi_\epsilon)$ and $\varphi<1$, and if $\mu\in L_\infty(\pi_\epsilon)$, then

   \begin{align*} \bigg\Vert {{\pi -\frac{1}{t}\sum_{k=0}^{t-1} \mu P_\epsilon^k}}\bigg\Vert_{L_2(\pi_\epsilon)} &\leq \frac{1-(1-(\alpha-\epsilon))^t}{t(\alpha-\epsilon)} \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}^{1/2} \Vert {{ \pi_\epsilon-\mu}}\Vert_{L_2(\pi_\epsilon)} \\[3pt] &\qquad +\frac{\varphi + \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}^{1/2}\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}(1-(\alpha-\epsilon))}{1-\varphi}.\end{align*}

The proof of this result is found in Appendix A.3.1. Relative to the uniform closeness of kernels (in total variation) required in [Reference Johndrow, Mattingly, Mukherjee and Dunson18], our assumption that the approximating kernel is close in the operator norm induced by $L_2(\pi)$ is non-comparable. This is because our bound is in terms of the $L_2$ distance, which always upper-bounds the total variation distance (up to a constant factor of $1/2$), but our assumption also does not require spatial uniformity, which that of [Reference Johndrow, Mattingly, Mukherjee and Dunson18] does. Thus, this paper’s assumptions are neither weaker nor stronger than those in [Reference Johndrow, Mattingly, Mukherjee and Dunson18]. Comparing the above results to the corresponding $L_1$ result of [Reference Johndrow, Mattingly, Mukherjee and Dunson18], we see that the transient phase bias part of our $L_2$ bounds differ from the $L_1$ transient phase bias bound of [Reference Johndrow, Mattingly, Mukherjee and Dunson18] only by a factor which is constant in time, but varies with the initial distribution (as is to be expected when moving from uniform ergodicity to geometric ergodicity).

3.4. Mean squared error bounds for Monte Carlo estimates

Suppose that $ ( {X^\epsilon_k} )_{k\in{\mathbb{N}\cup{\{0\}}}}$ is a realization of the Markov chain with transition kernel $P_\epsilon$ and initial distribution $\mu$. The mean squared error of a Monte Carlo estimate of $\pi f$ made using $ ( {X^\epsilon_k} )_{k\leq t}$ is given by

(6) \begin{equation}\begin{aligned} {MSE}^{{\epsilon}}_{{t}} ( {{\mu},{f}} ) & = \mathbb{E}\left[\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1} f(X^\epsilon_k)\right)^2\right].\end{aligned}\end{equation}

The proof of this result is found in Appendix A.3.3. Perturbation bounds based upon drift and minorization conditions could provide similar mean squared error bounds for functions in $L_2(\pi_\epsilon)$ with

\begin{equation*}\sup\limits_{x\in{\mathcal{X}}} \frac{ \vert {{f}} \vert }{\sqrt{V}} <\infty\end{equation*}

(where V is the function appearing in the drift condition), as in [Reference Johndrow and Mattingly17]. While that may be a larger class of functions than $L_4^{\prime}(\pi_\epsilon)$ (depending on what V happens to be), the class $L_4^{\prime}(\pi_\epsilon)$ is quite rich, making this bound still useful. Moreover, the class of functions to which our mean squared error bounds apply, and the value of the bound itself, depend only on intrinsic features of the Markov chains under consideration. In contrast, bounds based on drift and minorization conditions include extrinsic features—introduced by the user for analytic purposes (such as the drift function, V)—for which many choices might exist, each leading to different function classes and different bounds.

4.1. Noisy and approximate MCMC

The noisy (or approximate) Metropolis–Hastings (nMH) algorithm, as found in [Reference Alquier, Friel, Everitt and Boland1] (see also [Reference Medina-Aguayo, Lee and Roberts25]), was briefly described above. The algorithm is defined exactly the same way as the MH algorithm, except that the acceptance ratio, $a(Y_t|X_{t-1})$, is replaced by a (possibly stochastic) approximation $\widehat a(Y_t|X_{t-1}, Z_t)$. Here $Z_t$ denotes some random element providing an additional source of randomness, so that $a(Y_t|X_{t-1}, Z_t)$ is not $\sigma(Y_t, X_{t-1})$-measurable when the approximation $\widehat a(Y_t|X_{t-1}, Z_t)$ is stochastic. In the case of a deterministic approximation, $Z_t$ can be ignored or treated as a constant. The approximation can typically be thought of as replacing the target density in the acceptance ratio with some approximation. This includes most approximate MCMC algorithms which preserve the state space and the Markov property, such as those replacing $\pi$ with a deterministic approximation or an independent stochastic approximation at each step (as in Monte Carlo within Metropolis). It does not include algorithms which retain the Markov property only for an augmented state space, such as the pseudo-marginal approach of [Reference Andrieu and Roberts2].

For our analysis of these algorithms, P will represent the transition kernel for the MH algorithm, while $\widehat P$ will represent the kernel for the corresponding nMH chain. The key step in applying our results from Section 3 will be to show the $L_2(\pi)$ closeness of the nMH transition kernel to the MH transition kernel. Again, $ \Vert {\cdot}\Vert_{L_2(\pi)} $ is the norm on $L_2(\pi)$ and the corresponding operator norm. We will assume that $\pi$ and $\{Q(x,\cdot)\}_{x\in {\mathcal{X}}}$ are all absolutely continuous with respect to the Lebesgue measure and have densities $\pi$ and $ \{ {q(\cdot\vert x)} \}_{x\in{\mathcal{X}}}$ respectively. All arguments used would still apply if there were an arbitrary dominating measure in place of the Lebesgue measure. Let $F_{y\vert x}$ be the regular conditional distribution for Z given $X=x$ and $Y=y$, and let $f_{y\vert x}$ be its Lebesgue density. Define the perturbation function for the nMH algorithm as

\begin{align*}r(y|x) &= {\stackrel{\mathbb{E}}{{Z\sim F_{y| x}}}} \left( {{a}}(y|x)-{\widehat{a}}(y|x,Z)\right) = \int \left( {{a}}(y|x)-{\widehat{a}}(y|x,z)\right) f_{y| x}(z) dz.\end{align*}

Theorem 6. (Geometric ergodicity and closeness of stationary distributions for nMH) Let P be the transition kernel for an MH algorithm with proposal distribution Q, target distribution $\pi$, and acceptance ratio $a(\cdot\vert \cdot)$. Let $\widehat P$ be the transition kernel for a corresponding nMH algorithm with approximate/noisy acceptance ratio $\widehat a(\cdot\vert \cdot, \cdot)$. Let $r(\cdot\vert \cdot)$ be the corresponding perturbation function.

If $ \Vert {Q}\Vert_{L_2(\pi)} <\infty$ and $\sup_{x,y} \vert {{r(y|x)}} \vert \leq R$, then

(7) \begin{equation}\begin{aligned} \Vert {{ \widehat P - P}}\Vert_{L_2(\pi)} \leq R (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )\ .\end{aligned}\end{equation}

Furthermore, if P is reversible and $L_2(\pi)$-GE with geometric contraction factor $(1-\alpha)$, and $\epsilon = R (1+ \Vert {{Q}}\Vert_{L_2(\pi)} ) <\alpha$, then $\widehat P$ has a stationary distribution $\widehat\pi$, and the assumptions outlined in Section 3.2 hold with $P_\epsilon = \widehat P$ and $\pi_\epsilon =\widehat\pi$.

Therefore, Theorems 1 to 5 and Corollary 1 can all be applied. In particular, $\widehat P$ is $L_2(\pi)$-GE with factor $1-(\alpha-R (1+ \Vert {{Q}}\Vert_{L_2(\pi)} ))$, it is a.e.-TV-GE, and

(8) \begin{equation}\begin{aligned} \Vert {\widehat \pi - \pi}\Vert_{L_2(\pi)} \leq \frac{R (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )}{\sqrt{\alpha^2 - R^2 (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )^2}} \ ;\end{aligned}\end{equation}

furthermore, if $\widehat P$ is reversible, then it is $L_2(\widehat\pi)$-GE with factor $(1-(\alpha-R (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )))$.

The above theorem provides an alternative to the analogous result of Corollary 2.3 from [Reference Alquier, Friel, Everitt and Boland1], relaxing the uniform ergodicity assumption. In particular, it requires that $Q\in\mathcal{B}(L_2(\pi))$ and that $R(1+ \Vert {{Q}}\Vert_{L_2(\pi)} )<\alpha$. The first of these requirements is not dramatically limiting since the user has control over the choice of Q. The second requirement is also not dramatically limiting, as control over R may be interpreted as limiting the amount of noise in the nMH algorithm, and such control is required regardless in order to ensure the accuracy of approximation in both the geometrically ergodic and uniformly ergodic cases.

4.2. Application to fixed deterministic approximations

Suppose we run a fixed MH algorithm, but replace the target density with one which is close everywhere. Perhaps this alternative density is easier to compute (e.g. replacing an integral with a Laplace approximation as in [Reference Kass, Tierney and Kadane19], or replacing a full sample with a coreset for sub-sampled Bayesian inference as in [Reference Campbell and Broderick8]). By construction we would know that the approximate target distribution is close to the ideal target distribution. The question still remains whether geometric ergodicity is preserved. We resolve this question in the case that the approximation has constant relative error.

Corollary 2. Suppose we can approximate the unnormalized target density, $C\pi$, by $\widehat \pi$, with a $\theta$-bounded relative error:

(9) \begin{equation}\begin{aligned} \sup\limits_{x\in{\mathcal{X}}} \vert {{\log\frac{C\pi(x)}{\widehat\pi(x)}}} \vert \leq \theta \ . \end{aligned}\end{equation}

If the MH algorithm with proposal kernel Q is $L_2(\pi)$-GE with factor $(1-\alpha)$, and if

\begin{equation*}\theta < \frac{\alpha}{2(1+ \Vert {{Q}}\Vert_{L_2(\pi)} )},\end{equation*}

then the corresponding approximate transition kernel, $\hat P$, is $L_2(\widehat \pi)$-GE, and

(10) \begin{equation}\begin{aligned} \Vert {{\widehat \pi - \pi}}\Vert_{L_2(\pi)} \leq \frac{2\theta (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )}{\sqrt{\alpha^2 - 4\theta^2 (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )^2}} \ . \end{aligned}\end{equation}

Proof. Since the function $x\mapsto 1\wedge \exp(x)$ is 1-Lipschitz, we have

(11) \begin{equation}\begin{aligned} \vert {{r(y\vert x)}} \vert & = \left\vert {{a(y\vert x) - \widehat a(y\vert x)}} \right\vert \\[3pt] & \leq \left\vert {\log\frac{\pi(y)q(x\vert y)}{\pi(x)q(y\vert x)} - \log\frac{\widehat \pi(y)q(x\vert y)}{\widehat\pi(x)q(y\vert x)} } \right\vert \\[3pt] & = \left\vert {{\log\frac{C\pi(y)}{\widehat \pi(y)} - \log\frac{C\pi(x)}{\widehat\pi(x) }}} \right\vert \\[3pt] & \leq 2 \theta. \end{aligned}\end{equation}

So $\widehat P$ will be $L_2(\pi)$-GE as long as P was geometrically ergodic with some factor $0\leq(1-\alpha)<1$ and

(12) \begin{equation}\begin{aligned} \theta < \frac{\alpha}{2(1+ \Vert {{Q}}\Vert_{L_2(\pi)} )} \ . \end{aligned}\end{equation}

Moreover, in this case, $\widehat P$ is reversible. Thus, we can use Theorem 3 to obtain $L_2(\widehat \pi)$-GE of $\widehat P$, with factor $1- \alpha + 2\theta(1+ \Vert {{Q}}\Vert_{L_2(\pi)} )$.

In this scenario, we can also use Theorem 5 to get quantitative bounds for the mean squared error of any Monte Carlo estimates made using $\widehat P$, or any of our other results in Theorems 1 to 4 and Corollary 1 as needed.

This can be approached in two ways. One option is to obtain samples for the random effects and parameters jointly given the data, and discard the random effects to get marginal posterior samples for the parameters. The second option is to approximate the likelihood by integrating (numerically) over the random effects, and using the resulting approximate likelihood in the calculations involving the unnormalized posterior for the parameters.

In the second case, when the prior for the parameters is compactly supported, if one had established a result saying that a particular MH procedure for the exact posterior distribution of the parameters would be geometrically ergodic, then one could directly transfer this result to the approximate posterior computed using a Laplace approximation, at least for large enough samples. This is valid since the Laplace approximation has constant relative error on compact sets, and the relative error decreases with sample size (see [Reference Tierney and Kadane37]). Hence, for a large enough sample size, Equation (12) will be satisfied regardless of what the proposal kernel Q was (as long as $ \Vert {{Q}}\Vert_{L_2(\pi)} $ was finite).

Theorem 3.2 of [Reference Campbell and Broderick8] provides the guarantee that, with probability $(1-\delta)$, the unnormalized approximate posterior $\hat C \hat \pi$ based on a uniform coreset of size M will satisfy

(13) \begin{equation}\begin{aligned} \sup\limits_{x\in {\mathcal{X}}}\frac{1}{ \vert {{\mathcal{L}(x)}} \vert } \left\vert {{\log \frac{\hat C \hat \pi(x)}{C\pi(x)}}} \right\vert \leq \frac{\sigma }{\sqrt{M}} \left( {\frac{3}{2}D +\overline \eta\sqrt{2\log({1/\delta}})} \right), \end{aligned}\end{equation}

where $\sigma = \sum_{n=1}^N \sigma_n$, N is the number of observations,

\begin{equation*}\sigma_n = \sup\limits_{x\in {\mathcal{X}}} \vert {{\frac{\mathcal{L}_i(x)}{\mathcal{L}(x)}}} \vert ,\end{equation*}

$\mathcal{L}_i(x)$ is the log-likelihood of parameter x at the ith observation, $\mathcal{L}(x) = \sum_{i=1}^N \mathcal{L}_i(x)$ is the log-likelihood of the dataset

(14) \begin{equation}\begin{aligned} \overline \eta = \max_{i,j\in \{ {1,\dots,N} \}} \sup\limits_{x\in {\mathcal{X}}}\frac{1}{ \vert {\mathcal{L}(x)} \vert } \vert {\frac{\mathcal{L}_i(x)}{\sigma_i} - \frac{\mathcal{L}_j(x)}{\sigma_j}} \vert , \end{aligned}\end{equation}

and D is the approximate dimension of $ \{ {\mathcal{L}_i} \}_{i=1}^n$ ([Reference Campbell and Broderick8, Definition 3.1]).

If, in addition to assuming that $ \{ {\sigma_i} \}_{i=1}^N$ are all finite as in [8, Section 3], one were to assume that $ \vert {\mathcal{L}(x)} \vert $ is bounded as a function of x, then the uniform coreset result would imply the conditions of our Corollary 2, namely that

(15) \begin{equation}\begin{aligned} \sup\limits_{x\in{\mathcal{X}}} \left\vert {\log\frac{C\pi(x)}{\widehat\pi(x)}} \right\vert & \leq \frac{\sigma \Vert {\mathcal{L}} \Vert_\infty}{\sqrt{M}} \left( {\frac{3}{2}D +\overline \eta\sqrt{2\log({1/\delta}})} \right), \end{aligned}\end{equation}

with high probability. Consequently, for any proposal kernel $Q\,{:}\,L_2(\pi)\to L_2(\pi)$ we should be able to choose M sufficiently large so that with high probability

(16) \begin{equation}\begin{aligned} \frac{\sigma \Vert {\mathcal{L}} \Vert_\infty}{\sqrt{M}} \left( {\frac{3}{2}D +\overline \eta\sqrt{2\log({1/\delta}})} \right) < \frac{\alpha}{2(1+ \Vert {{Q}}\Vert_{L_2(\pi)} )}. \end{aligned}\end{equation}

Hence the approximating Markov chain will be geometrically ergodic with high probability.

4.3. Application to Monte Carlo within Metropolis

Following [Reference Medina-Aguayo, Rudolf and Schweizer24], we can get bounds for the simple Monte Carlo within Metropolis algorithm (MCwM). This is the special case of nMH where we approximate the likelihood ratio

\begin{equation*}\frac{\pi(y)}{\pi(x)} = \frac{{\mathbb{E}}\Pi(y,Z)}{{\mathbb{E}}\Pi(x,Z)}\end{equation*}

by

\begin{equation*}\widehat{\left ({\frac{\pi(y)}{\pi(x)}} \right)} = \frac{\sum_{i=1}^N \Pi(y,Z_{i})}{\sum_{i=N+1}^{2N} \Pi(x,Z_{i})}\end{equation*}

using a new independent sample taken each time the likelihood is evaluated. In the notation of the previous section,

(17) \begin{equation}\begin{aligned} \widehat a(y\vert x,z) = 1 \wedge \frac{q(x\vert y)\sum_{i=1}^N \Pi(y,z_{i})}{q(y\vert x)\sum_{i=N+1}^{2N} \Pi(x,z_{i})}.\end{aligned}\end{equation}

Let

(18) \begin{equation}\begin{aligned} W_k(x) & = \frac{1}{k \pi(x)} \sum_{i=1}^k \Pi(x,Z_{i}), \\[3pt] i_{k}(x)^2 & = {\mathbb{E}}[W_k(x)^{-2}],\\[3pt] s(x) & = \frac{1}{\sqrt{\pi(x)}} \textrm{StdDev}(\Pi(x,Z_1)). \\\end{aligned}\end{equation}

Lemma 14 of [Reference Medina-Aguayo, Rudolf and Schweizer24] tells us that if there is a $k\in {\mathbb{N}}$ such that $i_{k}(x)<\infty$ for all $x\in{\mathcal{X}}$, then for $N\geq k$,

(19) \begin{equation}\begin{aligned} \vert {{r(y\vert x)}} \vert & \leq a(y\vert x) \frac{1}{\sqrt{N}} i_k(y)\left ({s(x)+s(y)} \right) \\ &\leq \frac{1}{\sqrt{N}} i_k(y)\left ({s(x)+s(y)} \right).\end{aligned}\end{equation}

Corollary 3. Let P be the MH transition kernel for the target density $\pi$ and proposal kernel Q. Let $\widehat P_N$ be the corresponding MCwM transition kernel when $\pi(\cdot)$ is approximated by $\frac{1}{N} \sum_{i=1}^N \Pi(\cdot,Z_{i})$.

Assume that s and the $i_k$ as defined above are uniformly bounded for some $k\in\mathbb{N}$. Suppose further that

\begin{equation*}N_0= \textrm{max}\Big({k, \frac{4 \Vert {i_k} \Vert_\infty^2 \Vert {s} \Vert_\infty^2 (1+ \Vert {{Q}}\Vert_{L_2(\pi)} )^2}{\alpha^2}} \Big),\end{equation*}

and $N\geq \lfloor {N_0} \rfloor+1$.

Then $\widehat P_N$ is reversible and $L_2(\pi)$-GE with factor

\begin{equation*} 1- \alpha + \frac{1}{\sqrt{N/N_0}},\end{equation*}

and it has a stationary distribution

\begin{equation*}\widehat{\pi}_N(x) \propto \frac{\pi(x)}{N\ {\mathbb{E}} \left[{\left({\sum_{i=1}^N \Pi(x,Z_i)} \right)^{-1}} \right]}\end{equation*}

with

(20) \begin{equation}\begin{aligned} \Vert {{\pi - \widehat \pi_N}}\Vert_{L_2(\pi)} \leq \sqrt{\frac{N_0}{N\alpha^2 -N_0}}. \end{aligned}\end{equation}

Proof. Suppose that $N\geq \lfloor {N_0} \rfloor+1$. From Theorem 1, we know that the perturbed chain $\widehat P_N$ is $L_2(\pi)$-GE with factor $ 1- \alpha + \frac{1}{\sqrt{N/N_0}}$ and has a stationary distribution $\widehat\pi_N$ with

(21) \begin{equation}\begin{aligned} \Vert {{\pi - \widehat \pi_N}}\Vert_{L_2(\pi)} \leq \sqrt{\frac{N_0}{N\alpha^2 -N_0}} \ .\end{aligned}\end{equation}

Moreover, by inspection, $\widehat P_N$ is reversible with respect to

\begin{align*}\widehat{\pi}_N(x) \propto \frac{\pi(x)}{N\ {\mathbb{E}} \left [{\left ({\sum_{i=1}^N \Pi(x,Z_i)}\right) ^{-1}} \right]}.\end{align*}

Thus, we can use Theorem 3 to obtain $L_2(\widehat \pi_N)$-GE of $\widehat P_N$, with factor $1- \alpha + \frac{1}{\sqrt{N/N_0}}$.

Remark 6. A simple scenario under which these $i_k$ and s are uniformly bounded is when the joint density of x and Z is bounded above and below by a multiple of the marginal of x, so that

(22) \begin{equation}\begin{aligned} \frac{\Pi(x,z)}{\pi(x)} \in [c,C] \end{aligned}\end{equation}

for all $(x,z)\in{\mathcal{X}}\times\mathcal{Z}$. This condition is essentially tight if we wish to take $k=1$ and take the base measure to be the Lebesgue measure restricted to $U\subset\mathbb{R}^d$; in this case the condition $ \Vert {i_k(x)} \Vert_{L_\infty}<\infty$ implies that

(23) \begin{equation}\begin{aligned} \int_{U} \frac{\pi(x)}{\Pi(x,z)} dz = {\mathbb{E}}_{Z\sim\frac{\Pi(x,\cdot)}{\pi(x)}} \frac{\pi(x)^2}{\Pi(x,\cdot)^2} <\infty \end{aligned}\end{equation}

for all x. That is, the reciprocal of the conditional density of Z given $X=x$ has a finite integral for each x.

Remark 7. More generally, [Reference Medina-Aguayo, Rudolf and Schweizer24, Lemma 23] tells us that if ${\mathbb{E}}[W_{k_0}(x)^{-p}]<\infty$ for some $k_0\in\mathbb{N}$ and $p>0$, then for $k\geq k_0 \lceil {\frac{2}{p}} \rceil$, $i_{k}(x)^2 < {\mathbb{E}}[W_{k_0}(x)^{-p}]$. Therefore, in order to uniformly bound $i_k(x)$, it is sufficient to bound ${\mathbb{E}}[W_{k_0}(x)^{-p}]$ uniformly in x for some $k_0\in\mathbb{N}$, $p>0$. This is much less restrictive than trying to bound $i_1(x)$. In the case that $p<1$, $k_0=1$, this is much less restrictive than when $p=2$, $k_0=1$; it is equivalent to requiring that tempered versions of the conditional distribution

\begin{equation*}\frac{\Pi(x,\cdot)}{\pi(x)}\end{equation*}

can be normalized by uniformly bounded normalizing constants. This would be true if, for example, $(Z| X=x)\sim\mathcal{N}(\mu(x),\sigma^2(x))$ with $\sigma^2(x)$ uniformly bounded in x. More generally, using $0<p<1$ instead of $p=2$, whenever the conditional law of Z has uniform exp-poly tails, i.e.

\begin{equation*}\frac{\Pi(x,z)}{\pi(x)}\leq \exp( -C \vert {{z-\mu(x)}} \vert ^\alpha)\end{equation*}

with $\alpha>0$, the p-version of the condition would hold.

We could also use Theorem 5 to get quantitative bounds for the mean squared error of any Monte Carlo estimates made using $\widehat P_N$, or any of our other results in Theorems 1 to 4 and Corollary 1 as needed.

Medina-Aguayo et al. [Reference Medina-Aguayo, Rudolf and Schweizer24] also consider a case where the assumption that s and the $i_k$ are uniformly bounded is dropped, and instead, the perturbed kernel is restricted to a bounded region. We do not address this case here.

A.1 Proof of Theorem 1

The following lemma is contained in the remark after Theorem 2.1 of [Reference Roberts and Rosenthal29]; we prove it here as well since the proof is so simple.

Lemma 3. (Remark in [Reference Roberts and Rosenthal29].) For any probability measure $\mu\in L_2(\pi)$,

\begin{align*} \Vert {{ \mu - \pi}}\Vert_{L_2(\pi)} ^2 = \Vert {{\mu}}\Vert_{L_2(\pi)} ^2 -1.\end{align*}

Proof.

\begin{align*}0\leq \Vert {{\mu-\pi}}\Vert_{L_2(\pi)} ^2 &=\int \left ({{\frac{{\textrm{d}}\mu}{{\textrm{d}}\pi}} -1}\right)^2 {\textrm{d}}\pi =\int \left ({\left ({{\frac{{\textrm{d}}\mu}{{\textrm{d}}\pi}}}\right)^2 -2 {\frac{{\textrm{d}}\mu}{{\textrm{d}}\pi}} +1 }\right) \textrm{d}\pi\\ &=\int \left ({{\frac{{\textrm{d}}\mu}{{\textrm{d}}\pi}}}\right)^2\textrm{d}\pi-2\int \textrm{d}\mu +\int \textrm{d}\pi = \Vert {\mu^2-1}\Vert_{L_2(\pi)} .\end{align*}

We will make use of the following simplified version of Theorem 2.1 from [Reference Roberts and Rosenthal29] as well.

Note that while when the kernel is reversible we may take $C(\mu) = \Vert {{\mu-\pi}}\Vert_{L_2(\pi)} $ in the bound corresponding to $L_2(\pi)$-GE with optimal rate $\rho$, this is not true for non-reversible chains. By applying the above theorem in our context we have the following.

Lemma 4. Under the assumptions of Section 3.2,

\begin{align*} \Vert {{ \nu_1 P^n - \nu_2 P^n}}\Vert_{L_2(\pi)} \leq (1-\alpha)^n \Vert {{\nu_1-\nu_2}}\Vert_{L_2(\pi)} \end{align*}

for any probability distributions $\nu_1,\nu_2\in L_2(\pi)$. In particular, taking $\nu_2=\pi$,

\begin{align*} \Vert {{\nu_1 P^n - \pi}}\Vert_{L_2(\pi)} \leq (1-\alpha)^n \Vert {{\nu_1-\pi}}\Vert_{L_2(\pi)} =(1-\alpha)^n \sqrt{ \Vert {{ \nu_1}}\Vert_{L_2(\pi)} ^2-1},\end{align*}

and applying Cauchy–Schwarz yields

\begin{align*} \Vert {{\nu_1 P^n - \pi}}\Vert_{L_1(\pi)} \leq \Vert {{ \nu_1 P^n - \pi}}\Vert_{L_2(\pi)} \leq(1-\alpha)^n \Vert {{ \nu_1 - \pi}}\Vert_{L_2(\pi)} .\end{align*}

We begin with a first result giving sufficient conditions under which the stationary distribution $\pi_\epsilon$ of the perturbed chain is in $L_2(\pi)$.

Proof. Since $P_\epsilon$ is $\pi$-irreducible and aperiodic, it has at most one stationary distribution, $\pi_\epsilon$, with $\pi_\epsilon\ll \pi$ (see for example [Reference Douc, Moulines, Priouret and Soulier9, Corollary 9.2.16]).

Suppose for now that $\pi P_\epsilon^n$ has an $L_2(\pi)$ limit, $\pi_\epsilon$. Then, using the triangle inequality, the contraction property (${ \Vert {P_\epsilon} \Vert_{\text{TV}}} = 1$), and Cauchy–Schwarz, we have

\begin{align*} { \Vert {\pi_\epsilon P_\epsilon - \pi_\epsilon} \Vert_{\text{TV}}} & \leq { \Vert {\pi_\epsilon P_\epsilon - \pi P_\epsilon^{n}}\Vert_{\text{TV}}} + { \Vert {\pi P_\epsilon^{n} - \pi_\epsilon} \Vert_{\text{TV}}}\\[3pt] & \leq { \Vert {\pi_\epsilon - \pi P_\epsilon^{n-1}} \Vert_{\text{TV}}} + { \Vert {\pi P_\epsilon^{n} - \pi_\epsilon} \Vert_{\text{TV}}}\\[3pt] & \leq \Vert {{\pi_\epsilon - \pi P_\epsilon^{n-1}}}\Vert_{L_2(\pi)} + \Vert {{\pi P_\epsilon^{n} - \pi_\epsilon}}\Vert_{L_2(\pi)} {\stackrel{{n\to\infty}}{\to}}{0};\end{align*}

thus we find that $\pi_\epsilon$ must be stationary for $P_\epsilon$.

It remains to verify that $\{\pi P_\epsilon^n\}_{n\in\mathbb{N}}$ is an $L_2(\pi)$-Cauchy sequence, and thus from completeness it must have an $L_2(\pi)$-limit. To this end, define $Q_\epsilon = (P_\epsilon - P)$. Let $\textbf{2}^k=\{0,1\}^k$ for all $k\in\mathbb{N}$. We will expand $\pi(P+Q_\epsilon)^n$ and use the following facts:

• A. $\forall R\in\mathcal{B}(L_2(\pi))\ [\pi P^n R = \pi R]$.

• B. $Q_\epsilon \,{:}\, L_2(\pi)\to L_{2,0}(\pi)$.

• C. $P\vert_{L_{2,0}(\pi)}\in\mathcal{B}(L_{2,0}(\pi))$ and $ \Vert {{P\vert_{L_{2,0}(\pi)}}}\Vert_{L_{2,0}(\pi)} \leq (1-\alpha)$.

Since the operators P and $Q_\epsilon$ do not (necessarily) commute, when we expand $(P+Q)^n$ we must have one distinct term per binary sequence of length n. We can then group terms by the number of leading Ps, and use (A) to cancel the leading terms.

Let $m,n\in\textbf{N}$ be arbitrary with $m\leq n$. Then

\begin{align*}& \Vert {{ \pi P_\epsilon^n -\pi P_\epsilon^m}}\Vert_{L_2(\pi)} \\[3pt] &= \Vert {{ \pi (P+Q_\epsilon)^n - \pi (P+Q_\epsilon)^m}}\Vert_{L_2(\pi)} \\[3pt] &= \left\Vert {{\pi \left [{\left ({\sum_{\textbf{b}\in\textbf{2}^n}\prod_{j=1}^n P^{b_j} Q_\epsilon^{1-b_j} }\right)-\left ({\sum_{\textbf{b}\in\textbf{2}^m} \prod_{j=1}^m P^{b_j} Q_\epsilon^{1-b_j} }\right)}\right]}}\right\Vert_{L_2(\pi)} \\[3pt] & =\Bigg \Vert\pi\Bigg[\left ({P^n+\sum_{k=0}^{n-1}P^{n-k-1}Q_\epsilon\sum_{\textbf{b}\in\textbf{2}^{k}}\prod_{j=1}^{k} P^{b_j} Q_\epsilon^{1-b_j}}\right) \\[3pt]&\qquad - \left ({P^m+\sum_{k=0}^{m-1}P^{m-k-1}Q_\epsilon\sum_{\textbf{b}\in\textbf{2}^{k}} \prod_{j=1}^{k} P^{b_j} Q_\epsilon^{1-b_j} }\right) \Bigg] \Bigg\Vert_{L_2(\pi)}\\[3pt] & = \left \Vert{\left ({\pi+\sum_{k=0}^{n-1}\pi Q_\epsilon\sum_{\textbf{b}\in\textbf{2}^{k}} \prod_{j=1}^{k} P^{b_j} Q_\epsilon^{1-b_j} }\right) -\left ({\pi+\sum_{k=0}^{m-1}\pi Q_\epsilon\sum_{\textbf{b}\in\textbf{2}^{k}} \prod_{j=1}^{k} P^{b_j} Q_\epsilon^{1-b_j} }\right) } \right\Vert_{L_2(\pi)}\\[3pt] & = \left\Vert {{\pi \sum_{k=m}^{n-1}Q_\epsilon\sum_{\textbf{b}\in\textbf{2}^{k}} \prod_{j=1}^{k} P^{b_j} Q_\epsilon^{1-b_j}}}\right\Vert_{L_2(\pi)} \\[3pt] &\leq \epsilon \sum_{k=m}^{n-1}\sum_{\textbf{b}\in\textbf{2}^{k}} \prod_{j=1}^{k} (1-\alpha)^{b_j} \epsilon^{1-b_j}\\[3pt] &=\epsilon \sum_{k=m}^{n-1}(1-\alpha+\epsilon)^{k}\\[3pt] &\leq \frac{\epsilon}{\alpha-\epsilon} (1-\alpha+\epsilon)^m.\end{align*}

Since this upper bound on $ \Vert {{\pi P_\epsilon^n - \pi P_\epsilon^m}}\Vert_{L_2(\pi)} $ decreases to 0 monotonically in $m=\textrm{min}(m,n)$, the sequence must be $L_2(\pi)$-Cauchy.

Now, to bound the norm of $\pi_\epsilon$, we take $m=0$ and we get that for all $n\in \mathbb{N}$,

\begin{align*} \Vert {{ \pi P_\epsilon^n -\pi}}\Vert_{L_2(\pi)} \leq \frac{\epsilon}{\alpha-\epsilon}.\end{align*}

From the continuity of the norm, it must be the case that $ \Vert {{\pi_\epsilon- \pi}}\Vert_{L_2(\pi)} \leq \frac{\epsilon}{\alpha-\epsilon} $.

Lemma 6. Under the assumptions of Section 3.2, if in addition $\epsilon<\alpha$, then

\begin{align*}1\leq \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} \leq\frac{\alpha}{\sqrt{\alpha^2-\epsilon^2}}\end{align*}

and

\begin{align*}0\leq \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} \leq\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}.\end{align*}

Proof. The two lower bounds are immediate from Lemma 3 and the positivity of norms:

\begin{align*}0 \leq \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} ^2 = \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} ^2-1.\end{align*}

To derive the first upper bound, we apply Lemma 3, our assumptions about the operators P and $P_\epsilon$, and the triangle inequality to $\Vert \pi-\pi_\epsilon\Vert_2$:

\begin{align*}\sqrt{ \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} ^2-1}= \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} &= \Vert {{\pi P - \pi_\epsilon P+ \pi_\epsilon P - \pi_\epsilon P_\epsilon}}\Vert_{L_2(\pi)} \\ &\leq \Vert {{\pi P - \pi_\epsilon P}}\Vert_{L_2(\pi)} + \Vert {{ \pi_\epsilon P - \pi_\epsilon P_\epsilon}}\Vert_{L_2(\pi)} \\ &\leq (1-\alpha) \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} +\epsilon \Vert {{ \pi_\epsilon}}\Vert_{L_2(\pi)} \\ &= (1-\alpha)\sqrt{ \Vert {{ \pi_\epsilon}}\Vert_{L_2(\pi)} ^2-1}+\epsilon \Vert {{ \pi_\epsilon}}\Vert_{L_2(\pi)} .\end{align*}

Collecting the square roots and squaring both sides yields

\begin{align*}\alpha^2\left ({ \Vert {{ \pi_\epsilon} }\Vert_{L_2(\pi)} ^2-1}\right) &\leq \epsilon^2 \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} ^2,\end{align*}

which implies that

\begin{align*} \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} ^2 &\leq \frac{\alpha^2}{\alpha^2-\epsilon^2}.\end{align*}

Finally, the second upper bound is derived from the first one, again using Lemma 5.1:

\begin{align*} \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} ^2 = \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} ^2-1 \leq \frac{\alpha^2}{\alpha^2-\epsilon^2} - 1 = \frac{\epsilon^2}{\alpha^2-\epsilon^2}.\end{align*}

We next observe that our assumptions imply that for small enough perturbations, the perturbed chain $P_\epsilon$ is geometrically ergodic in the $L_2(\pi)$ norm.

Proof. Suppose that $\nu\in L_{2,0}(\pi)$. Then

\begin{align*} \Vert {{\nu P_\epsilon}}\Vert_{L_2(\pi)} & \leq \Vert {{\nu (P_\epsilon -P)}}\Vert_{L_2(\pi)} + \Vert {{\nu P}}\Vert_{L_2(\pi)} \\ & \leq \epsilon \Vert {{\nu}}\Vert_{L_2(\pi)} + (1-\alpha) \Vert {{\nu}}\Vert_{L_2(\pi)} \\ & =(1-\alpha+\epsilon) \Vert {{\nu}}\Vert_{L_2(\pi)} \, .\end{align*}

Thus, for any probability measure $\mu\in L_2(\pi)$, since $\pi_\epsilon \in L_2(\pi)$ we have

\begin{align*} \Vert {{\mu P_\epsilon^n -\pi_\epsilon}}\Vert_{L_2(\pi)} & = \Vert {{(\mu-\pi_\epsilon) P_\epsilon^n}}\Vert_{L_2(\pi)} \\ & \leq (1-(\alpha-\epsilon))^n \Vert {{\mu -\pi_\epsilon}}\Vert_{L_2(\pi)} \, .\end{align*}

Combining Lemmas 5 to 7 together with the triangle inequality immediately yields combinedthm.

A.2. Proofs of Theorem 2, Theorem 3, and Corollary 1

Definition 3. Following [Reference Roberts and Rosenthal29], a subset $S\subset{\mathcal{X}}$ is called hyper-small for the $\pi$-irreducible Markov kernel P with stationary measure $\pi$ if $\pi(S)>0$ and there exist $\delta_S>0$ and $k\in\mathbb{N}$ such that for all $x,y\in\mathcal X$,

\begin{equation*}{\frac{{\textrm{d}}P^k(x,\cdot)}{{\textrm{d}}\pi}} (y)\geq \delta_S\textbf{1}_S(x)\textbf{1}_S(y),\end{equation*}

or equivalently, if $P^k(x,A)\geq \delta_S\pi(A)$ for all $x\in S$ and $A\subset S$ measurable.

Lemma 4 of [Reference Jain and Jamison15] states that on a countably generated state space (as we have assumed herein), every set of positive $\pi$-measure contains a hyper-small subset.

Lemma 8. (Existence of hyper-small subsets from [Reference Jain and Jamison15].) Suppose that $({\mathcal{X}},\Sigma)$ is countably generated. Suppose that X is a $\phi$-irreducible Markov chain on ${\mathcal{X}}$ with kernel P for some $\sigma$-finite measure $\phi$ on ${\mathcal{X}}$. Then any set $K\subset {\mathcal{X}}$ with $\phi(K)>0$ contains a set $S_K$ such that (for some $n_{K}\in\mathbb{N}$)

\begin{align*} \inf\limits_{(x,y) \in S_K\times S_K} {\frac{{\textrm{d}}P^{n_K}(x,\cdot)}{{\textrm{d}}\pi}} (y) = \delta >0.\end{align*}

In the case that a stationary distribution $\pi$ for P exists, without loss of generality we can take $\phi=\pi$. In this case, it is immediate that any set $(S_K, n_K)$ satisfying Lemma 8 also satisfies Definition 3.

Also of importance to us is the following variant of Proposition 2.1 of [Reference Roberts and Rosenthal29], which provides a characterization of geometric ergodicity in terms of convergence to a hyper-small set.

Proof of Theorem 2.

1. (i) Let S be a hyper-small set for $P_\epsilon$ (which must exist from Lemma 8, since $P_\epsilon$ is $\pi_\epsilon$-irreducible). Then the measure $\mu_S$ defined by

   \begin{equation*}{\frac{{\textrm{d}}\mu_S}{\textrm{d} \pi}} = \frac{1_{S}}{\pi_\epsilon(S)} {\frac{\textrm{d} \pi_\epsilon}{\textrm{d} \pi}}\end{equation*}
   satisfies (by Hölder’s inequality, and since $\pi_\epsilon\in L_2(\pi)$)
   \begin{align*} \Vert {{\mu_S}}\Vert_{L_2(\pi)} ^2 \leq \Vert {{\pi_\epsilon}}\Vert_{L_2(\pi)} ^2 \pi_\epsilon(S)^{-2}<\infty, \end{align*}
   and hence $\mu_S\in L_2(\pi)$. Then (by Cauchy–Schwarz again)
   \begin{align*} { \left\Vert {\int \frac{\textbf{1}_S(y)\pi_\epsilon({\textrm{d}}y)}{\pi_\epsilon(S)} P_\epsilon^n(y,\cdot) -\pi_\epsilon} \right\Vert_{\text{TV}}} \leq \frac{1}{2} \Vert {{\mu_S P_\epsilon^n -\pi_\epsilon}}\Vert_{L_2(\pi)} \leq \Vert {{\mu_S - \pi_\epsilon}}\Vert_{L_2(\pi)} (1-\alpha +\epsilon)^n, \end{align*}
   which, along with Proposition 3, establishes that $P_\epsilon$ is $\pi_\epsilon$-a.e.-TV-GE with some factor $\rho_{\text{TV}}\in(0,1)$.

2. (ii) Suppose that $\mu\in L_\infty(\pi_\epsilon)$. Then $\mu \in L_2(\pi)$ since

   \begin{equation*}{\frac{{\textrm{d}}\mu}{\textrm{d} \pi}} \leq \Vert {\mu} \Vert_{L_\infty(\pi_\epsilon)} {\frac{{\textrm{d}}\pi_\epsilon}{\textrm{d} \pi}}.\end{equation*}
   Since $\mu P_\epsilon^n - \pi_\epsilon \in L_1(\pi_\epsilon)\subset L_1(\pi)$,
   (25) \begin{equation}\begin{aligned} \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{L_1(\pi_\epsilon)} = \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{L_1(\pi)} = 2{ \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{\text{TV}}}. \end{aligned}\end{equation}
   Applying this equality as well as Cauchy–Schwarz, we get
   (26) \begin{equation}\begin{aligned} \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{L_1(\pi_\epsilon)} & = \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{L_1(\pi)} \\[2pt] & \leq \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{L_2(\pi)} \\[2pt] & \leq \Vert {{\mu-\pi_\epsilon}}\Vert_{L_2(\pi)} (1-\alpha-\epsilon)^n. \end{aligned}\end{equation}

3. (iii) If $\pi\in L_\infty(\pi_\epsilon)$ and $\mu\in L_2(\pi_\epsilon)$, then

   (27) \begin{equation}\begin{aligned} \Vert {\mu P_\epsilon^n - \pi_\epsilon} \Vert_{L_2(\pi_\epsilon)}^2 & = \int \bigg ({{\frac{{\textrm{d}}\mu P_\epsilon^n - \pi_\epsilon}{{\textrm{d}}\pi_\epsilon}}}\bigg)^2 d \pi_\epsilon \\ & = \int \bigg({{\frac{{\textrm{d}}\mu P_\epsilon^n - \pi_\epsilon}{{\textrm{d}}\pi}}}\bigg)^2 {\frac{{\textrm{d}}\pi}{{\textrm{d}}\pi_\epsilon}} d \pi\\ &\leq \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}\int \bigg({{\frac{{\textrm{d}}\mu P_\epsilon^n - \pi_\epsilon}{{\textrm{d}}\pi}}}\bigg)^2 d \pi\\ & = \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)} \Vert {{\mu P_\epsilon^n - \pi_\epsilon}}\Vert_{L_2(\pi)} ^2\\ & \leq \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)} \Vert {{\mu-\pi_\epsilon}}\Vert_{L_2(\pi)} ^2(1-(\alpha-\epsilon))^{2n}. \end{aligned}\end{equation}

Proof of Theorem 3. From [Reference Baxter and Rosenthal4, Lemma 1], since $P_\epsilon$ has stationary measure $\pi_\epsilon$, we have $P_\epsilon\,{:}\, L_2(\pi_\epsilon)\to L_2(\pi_\epsilon)$. Since $P_\epsilon$ is $(L_\infty(\pi_\epsilon), \Vert {\cdot} \Vert_{L_1(\pi_\epsilon)})$-GE with factor $\rho_1 \leq (1-(\alpha-\epsilon))$ (as established by Theorem 2) and $P_\epsilon$ is reversible, it must also be $L_2(\pi_\epsilon)$-GE with factor $\rho =\rho_1$ by Lemma 2.

Proof of Corollary 1. Note that the assumption that $ \Vert {{P-P_\epsilon}}\Vert_{L_2(\pi_\epsilon)} <\varphi$ implies $P-P_\epsilon \,{:}\, L_2(\pi_\epsilon)\to L_2(\pi_\epsilon)$.

1. (i) Since $P_\epsilon$ is $L_2(\pi_\epsilon)$-GE with factor $(1-(\alpha-\epsilon))$ and $\pi_\epsilon$-reversible, we can reverse the roles of P and $P_\epsilon$, so the result follows by Theorem 1.

2. (ii) Taking $\mu = \pi$ and $n=1$ in Theorem(iii), we have

   (28) \begin{equation}\begin{aligned} \Vert {\pi P_\epsilon - \pi_\epsilon} \Vert_{L_2(\pi_\epsilon)}^2 & \leq \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)} \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} ^2(1-(\alpha-\epsilon))^2 \\ &\leq \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}\frac{\epsilon^2}{\alpha^2-\epsilon^2}(1-(\alpha-\epsilon))^2.\end{aligned}\end{equation}
   Hence,
   (29) \begin{equation}\begin{aligned} \Vert {\pi - \pi_\epsilon} \Vert_{L_2(\pi_\epsilon)} &\leq \Vert {\pi P - \pi P_\epsilon} \Vert_{L_2(\pi_\epsilon)} + \Vert {\pi P_\epsilon - \pi_\epsilon} \Vert_{L_2(\pi_\epsilon)} \\[2pt] & \leq \varphi \Vert {{\pi}}\Vert_{L_2(\pi_\epsilon)} + \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}^{1/2}\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}(1-(\alpha-\epsilon))\\[2pt] & = \varphi\sqrt{ \Vert {{\pi-\pi_\epsilon}}\Vert_{L_2(\pi_\epsilon)} ^2+1} + \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}^{1/2}\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}(1-(\alpha-\epsilon))\\[2pt] & \leq \varphi( \Vert {{\pi-\pi_\epsilon}}\Vert_{L_2(\pi_\epsilon)} +1) + \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}^{1/2}\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}(1-(\alpha-\epsilon)).\end{aligned}\end{equation}
   Hence,
   (30) \begin{equation}\begin{aligned} \Vert {{\pi-\pi_\epsilon}}\Vert_{L_2(\pi_\epsilon)} \leq \frac{\varphi + \Vert {\pi} \Vert_{L_\infty(\pi_\epsilon)}^{1/2}\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}(1-(\alpha-\epsilon))}{1-\varphi}.\end{aligned}\end{equation}
   Finally,
   \begin{align*} \Vert {{\mu P_\epsilon^n -\pi}}\Vert_{L_2(\pi_\epsilon)} & \leq \Vert {{\mu P_\epsilon^n -\pi_\epsilon}}\Vert_{L_2(\pi_\epsilon)} + \Vert {{\pi_\epsilon - \pi}}\Vert_{L_2(\pi_\epsilon)} .\end{align*}
   The first term is bounded by Theorem 2(iii), and the second term is bounded by (30).

A.3. Proofs of Theorem 4 and Theorem 5

A.3.1 Time-averaging of marginal distributions

Proof of Theorem 4. The first result of Theorem 4 follows from the triangle inequality and Theorem 1:

\begin{align*} \left\Vert {{\pi -\frac{1}{t}\sum_{k=0}^{t-1} \mu P_\epsilon^k}}\right\Vert_{L_2(\pi)} &\leq \frac{1}{t} \sum_{k=0}^{t-1} \left\Vert {{\pi - \mu P_\epsilon^k }}\right\Vert_{L_2(\pi)} \\[3pt] &\leq \frac{1}{t} \sum_{k=0}^{t-1}\left[(1-(\alpha-\epsilon))^k \Vert {{\pi_\epsilon-\mu}}\Vert_{L_2(\pi)} +\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}}\right]\\[3pt] & \leq \frac{1-(1-(\alpha-\epsilon))^t}{t(\alpha-\epsilon)} \Vert {{ \pi_\epsilon-\mu}}\Vert_{L_2(\pi)} +\frac{\epsilon}{\sqrt{\alpha^2-\epsilon^2}} \ .\end{align*}

The subsequent results follow similarly via Theorems 2 and 3 and Corollary 1.

A.3.2 Covariance bounds

We turn our attention to the covariance structure of the original and perturbed chains. There is an obvious isometric isomorphism between the space of measures $L_2(\pi)$ and the function space

\begin{align*} L^{\prime}_2(\pi) = \{ {f\,{:}\,{\mathcal{X}}\to\mathbb{R} \ \text{s.t.}\ \int f(x)^2\pi(dx) <\infty} \}\end{align*}

equipped with the norm $ \Vert {f} \Vert^2_{L^{\prime}_2(\pi)} = \int f(x)^2\pi(dx)$, where a measure $\mu$ is mapped to its Radon–Nikodym derivative, $\mu\mapsto {\frac{{\textrm{d}}\mu}{{\textrm{d}}\pi}}$. For this reason, we need not distinguish between these spaces, and when dealing with a function $f\in L^{\prime}_2(\pi)$ we may occasionally abuse notation and treat it as its associated measure. Let $X_t$ and $X^\epsilon_t$ denote the original and perturbed chains run from some initial measure $\mu\in L_2(\pi)$.

Corollary 4. Under the assumptions of Section 3.2,

1. (a) if $X_0\sim\pi$ (the initial distribution is the stationary distribution), then for $f,g\in L^{\prime}_2(\pi)$,

   (31) \begin{equation}\begin{aligned} \textrm{Cov} [f(X_t),g(X_s)]\leq (1-\alpha)^{|t-s|} \Vert {{f-\pi f}}\Vert_{L^{\prime}_2(\pi)} \Vert {{g-\pi g}}\Vert_{L^{\prime}_2(\pi)} \ ;\end{aligned}\end{equation}

2. (b) if $\epsilon<\alpha$, and $P_\epsilon$ is $\pi_\epsilon$-reversible, $\rho_2 = (1-(\alpha-\epsilon))$, and $X^\epsilon_0\sim\pi_\epsilon$, then for $f,g\in L_2^{\prime}(\pi_\epsilon)$,

   (32) \begin{equation}\begin{aligned} \textrm{Cov} [f(X^\epsilon_t),g(X^\epsilon_s)]\leq \rho_2^{|t-s|} \Vert {{ f - \pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} \Vert {{g - \pi_\epsilon g}}\Vert_{L^{\prime}_2(\pi_\epsilon)} \ ,\end{aligned}\end{equation}

where for a function $h\,{:}\,{\mathcal{X}}\to\mathbb{R}$, $\pi h$ is the constant function equal to $\int h(s)\pi(ds)$ everywhere.

Proof. The proof of this result follows that of Corollary B.5 in [Reference Johndrow, Mattingly, Mukherjee and Dunson18]. We only show the proof for the original chain; however, the proof for the perturbed chain is the same, since it is reversible and $L_2(\pi_\epsilon)$-GE with the appropriate factor, from Theorem 3.

Define the subspace

\begin{align*}L^{\prime}_{2,0}(\pi) = \{h\in L^{\prime}_2(\pi)\,{:} \int h(s)\pi(d s) = 0\},\end{align*}

and define the operator $F \in \mathcal{B}(L^{\prime}_{2,0}(\pi))$ by

\begin{align*}[F f](x) = \int P(x,d y)f(y) = \mathbb{E}[f(X_1)|X_0=x].\end{align*}

From Lemma 12.6.4 of [Reference Liu21],

\begin{align*} \sup\limits_{f,g\in L_2^{\prime}(\pi)} \text{corr}(f(X_0),g(X_t)) = \sup\limits_{\substack{ \Vert {{f}}\Vert_{L^{\prime}_2(\pi)} =1= \Vert {{g}}\Vert_{L^{\prime}_2(\pi)} \\f,g\in L^{\prime}_{2,0}(\pi)}} \langle f,F^t g\rangle = \Vert {F^t} \Vert_{L_{2,0}^{\prime}(\pi)}.\end{align*}

Consider the canonical isomorphism between $L_2(\pi)$ and $L^{\prime}_2(\pi)$. The restriction of this isomorphism (on the right) to elements of $L^{\prime}_{2,0}(\pi)$ yields $L_{2,0}(\pi)$ (on the left)—the signed measures with total measure 0. The image of F under the restricted isomorphism is the adjoint operator of P restricted to $L_{2,0}(\pi)$. Since P is $\pi$-reversible, it is self-adjoint in $L_2(\pi)$, so $ \Vert {F} \Vert_{L_{2,0}^{\prime}(\pi)}= \Vert {P} \Vert_{L_{2,0}(\pi)}$. Thus

\begin{align*} \Vert {F^t} \Vert_{L_{2,0}^{\prime}(\pi)} \leq \Vert {F} \Vert_{L_{2,0}^{\prime}(\pi)}^t = \Vert {P\big\vert_{L_{2,0}(\pi)}} \Vert^t \leq(1-\alpha)^t.\end{align*}

Therefore

\begin{align*} \textrm{Cov}(f(X_0),g(X_t))\leq \Vert {{f - \pi f}}\Vert_{L^{\prime}_2(\pi)} \Vert {{g-\pi g}}\Vert_{L^{\prime}_2(\pi)} (1-\alpha)^t.\end{align*}

Since Cov is symmetric, the shifted and symmetrized result holds for any $f,g\in L^{\prime}_2(\pi)$:

(33) \begin{equation}\begin{aligned} \textrm{Cov} [f(X_t),g(X_s)]\leq (1-\alpha)^{|t-s|} \Vert {{f -\pi f}}\Vert_{L^{\prime}_2(\pi)} \Vert {{ g - \pi g}}\Vert_{L^{\prime}_2(\pi)} .\end{aligned}\end{equation}

We present further bounds for the case that the initial distribution is not the stationary distribution in Corollary 5.

Remark 8. Note in Corollary 4 that

\begin{align*} \Vert {{h - \pi h}}\Vert_{L^{\prime}_2(\pi)} = \sqrt{ \Vert {{ h}}\Vert_{L^{\prime}_2(\pi)} ^2-(\pi h)^2}\leq \Vert {{h}}\Vert_{L^{\prime}_2(\pi)} \ .\end{align*}

Also note that

(34) \begin{equation}\begin{aligned} \Vert {{h}}\Vert_{L^{\prime}_2(\pi)} \leq \Vert {{h-\pi(h)}}\Vert_{L^{\prime}_2(\pi)} + |\pi(h)| \ .\end{aligned}\end{equation}

Corollary 5. Under the assumptions of Section 3.2,

1. (a) if $X_0\sim\mu$, then for $f,g\in L^{\prime}_4(\pi)$,

   \begin{align*}&\textrm{Cov}(f(X_t),g(X_{t+s}))\\ &\qquad\leq (1-\alpha)^s \Vert {{f -\pi f}}\Vert_{L^{\prime}_2(\pi)} \Vert {{ g - \pi g}}\Vert_{L^{\prime}_2(\pi)} \\ &\qquad\qquad + 2^{3/2}(1-\alpha)^{t+s/2} \Vert {{\mu-\pi}}\Vert_{L_2(\pi)} \Vert {f -\pi f} \Vert_{L_4^{\prime}(\pi)} \Vert { g - \pi g} \Vert_{L_4^{\prime}(\pi)}\\ &\qquad\qquad -(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right);\end{align*}

2. (b) if $\epsilon<\alpha$, and $P_\epsilon$ is $\pi_\epsilon$-reversible, $\rho_2 = (1-(\alpha -\epsilon))$, and $X^\epsilon_0\sim\mu$, then for $f,g\in L^{\prime}_4(\pi_\epsilon)$,

   \begin{align*}&\textrm{Cov}(f(X^\epsilon_t),g(X^\epsilon_{t+s}))\\ &\qquad\leq \rho_2^s \Vert {{f -\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} \Vert {{ g - \pi_\epsilon g}}\Vert_{L^{\prime}_2(\pi_\epsilon)} \\ &\qquad\qquad + 2^{3/2}\rho_2^{t+s/2} \Vert {{\mu-\pi}}\Vert_{L_2(\pi_\epsilon)} \Vert {f -\pi_\epsilon f} \Vert_{L_4^{\prime}(\pi_\epsilon)} \Vert { g - \pi_\epsilon g} \Vert_{L_4^{\prime}(\pi_\epsilon)}\\ &\qquad\qquad -(\mu P_\epsilon^t f-\pi_\epsilon f)\left(\mu P_\epsilon^{t+s} g -\pi_\epsilon g\right).\end{align*}

Proof. This will use the following shorthand notation. Let

\begin{align*}f_0 &= f-\pi f,\\g_0 &= g-\pi g,\\\Vert h\Vert_\star &= \left(\int (h(x)-\pi h)^2\pi(d x)\right)^{1/2},\\\Vert h\Vert_{{}_{\star\star}} &= \left(\int (h(x)-\pi h)^4\pi(d x)\right)^{1/4},\\C_\mu &= \Vert \mu -\pi\Vert_2.\end{align*}

We can interpret $\Vert\cdot\Vert_{{}_{\star\star}}$ as a centred 4-norm. It is certainly bounded above by $\Vert\cdot\Vert_4$, the norm on $L^{\prime}_4(\pi)$. For some results regarding the properties of a Markov transition kernel as an operator on $L^{\prime}_p(\pi)$ for general p given an $L_2$-spectral gap (as is implied by $L_2$-GE), please refer to [Reference Rudolf34].

We only show the proof for the original chain. The result for the perturbed chain has essentially the same proof.

By definition we can express the covariance by the triple integral below. We re-express this integral as a sum of two integrals involving the chain run from stationarity. This will allow us to apply Corollary 4. We have

\begin{align*}&\textrm{Cov}(f(X_t),g(X_{t+s}))\\ &\ = \iiint (f(y)-\mu P^t f)(g(z)-\mu P^{t+s} g)\mu(d x)P^t(x,d y)P^s(y,dz)\\ &\ = \iiint (f(y)-\mu P^t f)(g(z)-\mu P^{t+s} g)\left[\frac{d\mu}{d\pi}(x)-1\right] \pi(d x)P^t(x,d y)P^s(y,dz)\\ &\ \quad +\iiint(f(y)-\mu P^t f)(g(z)-\mu P^{t+s} g)\pi(d x)P^t(x,d y)P^s(y,dz).\end{align*}

We will simplify each of these expressions separately, starting with the second term:

\begin{align*}&\iiint(f(y)-\mu P^t f)(g(z)-\mu P^{t+s} g)\pi(d x)P^t(x,d y)P^s(y,dz)\\ &\qquad = \iint(f(y)-\mu P^t f)(g(z)-\mu P^{t+s} g)\pi(d y)P^s(y,dz)\\ &\qquad = \iint f(y)g(z)\pi(d y)P^s(y,dz) \\ &\qquad \qquad - (\mu P^t f)(\pi g)-(\pi f)(\mu P^{t+s} g)+(\mu P^t f)(\mu P^{t+s} g)\\ &\qquad = \iint f_0(y)g_0(z) \pi(d y)P^s(y,dz) +(\pi f)(\pi g)\\ &\qquad \qquad - (\mu P^t f)(\pi g)-(\pi f)(\mu P^{s+t} g)+(\mu P^t f)(\mu P^{t+s} g)\\ &\qquad = \left\langle f_0, F^s g_0 \right\rangle +(\mu P^t f-\pi f )(\mu P^{s+t} g - \pi g ).\end{align*}

For the first term we find that

\begin{align*}&\iiint (f(y)-\mu P^t f)(g(z)-\mu P^{t+s} g)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^t(x,d y)P^s(y,dz)\\ &\qquad = \iiint f(y)g(z)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^t(x,d y)P^s(y,dz)\\ &\qquad\qquad-(\mu P^t f)\iint g(z)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^{t+s}(x,dz)\\ &\qquad\qquad-(\mu P^{s+t} g)\iint f(y)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^{t}(x,d y)\\ &\qquad\qquad+(\mu P^t f)(\mu P^{s+t} g)\int\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)\\ &\qquad = \iiint f_0(y) g_0(z)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^t(x,d y)P^s(y,dz) \\ \end{align*}

\begin{align*} \\[-30pt] &\qquad\qquad-(\mu P^t f-\pi f)\iint g(z)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^{t+s}(x,dz)\\ &\qquad\qquad-(\mu P^{s+t} g -\pi g)\iint f(y)\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)P^{t}(x,d y)\\ &\qquad\qquad -(\pi f)(\pi g)\int\left(\frac{d\mu}{d\pi}(x)-1\right)\pi(d x)\\ &\qquad =\left\langle\frac{d\mu}{d\pi}-1, F^t (f_0\otimes (F^s g_0))\right\rangle\\ &\qquad \qquad -(\mu P^t f-\pi f)\left\langle \frac{d\mu}{d\pi}-1,F^{t+s} g\right\rangle-(\mu P^{t+s} g -\pi g)\left\langle \frac{d\mu}{d\pi}-1,F^{t} f\right\rangle\\ &\qquad =\left\langle\frac{d\mu}{d\pi}-1, F^t (f_0\otimes (F^s g_0))\right\rangle-2(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right),\end{align*}

where $f_0\otimes F^s g_0$ is defined by

\begin{align*} [f_0\otimes F^s g_0](y) = f_0(y) \int g_0(z)P^s(y,dz).\end{align*}

Putting these together,

\begin{align*} &\textrm{Cov}(f(X_t),g(X_{t+s}))\\[2pt] &\qquad = \left\langle f_0, F^s g_0 \right\rangle +(\pi f -\mu P^t f)(\pi g - \mu P^{s+t} g)\\[2pt] &\qquad \qquad + \left\langle\frac{d\mu}{d\pi}-1, F^t (f_0\otimes (F^s g_0))\right\rangle-2(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right)\\[2pt] &\qquad = \left\langle f_0, F^s g_0 \right\rangle + \left\langle\frac{d\mu}{d\pi}-1, F^t (f_0\otimes (F^s g_0))\right\rangle -(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right)\\[2pt] &\qquad \leq (1-\alpha)^s \Vert f\Vert_\star \Vert g\Vert_\star + (1-\alpha)^{t}\Vert \mu-\pi\Vert_2 \Vert f_0\otimes F^s g_0\Vert_2\\[2pt] &\qquad\qquad -(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right)\\[2pt] &\qquad \leq (1-\alpha)^s \Vert f\Vert_\star \Vert g\Vert_\star + (1-\alpha)^{t}\Vert \mu-\pi\Vert_2 \Vert f_0 \Vert_4\Vert F^s g_0\Vert_4\\[2pt] &\qquad\qquad -(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right)\\[2pt] &\qquad \leq (1-\alpha)^s \Vert f\Vert_\star \Vert g\Vert_\star + (1-\alpha)^{t}\Vert \mu-\pi\Vert_2 \Vert f_0 \Vert_4\Vert g_0\Vert_4 \left\Vert F^s\big\vert_{L^{\prime}_{4,0}}\right\Vert_4\\[2pt] &\qquad\qquad -(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right)\\[2pt] &\qquad \leq (1-\alpha)^s \Vert f\Vert_\star \Vert g\Vert_\star + 2^{3/2}(1-\alpha)^{t+s/2}\Vert \mu-\pi\Vert_2 \Vert f \Vert_{{}_{\star\star}}\Vert g\Vert_{{}_{\star\star}}\\[2pt] &\qquad\qquad -(\mu P^t f-\pi f)\left(\mu P^{t+s} g -\pi g\right).\end{align*}

The $\left\langle f_0, F^s g_0 \right\rangle$ term is bounded using Corollary 4, where we have taken the result in its equivalent form using the $\langle\cdot,\cdot\rangle$ notation and the forward operator F. The term

\begin{equation*}\left\langle\frac{d\mu}{d\pi}-1, F^t (f_0\otimes (F^s g_0))\right\rangle\end{equation*}

is bounded following the methodology of the proof of [Reference Rudolf34, Lemma 3.39] (in order, the inequalities are Cauchy–Schwarz, $\Vert F^s g_0\Vert \leq \Vert F^s\Vert\Vert g_0\Vert$ for any norm $\Vert\cdot\Vert$, and Proposition 3.17 of [Reference Rudolf34]).

The main motivation in establishing the covariance bounds in Corollaries 4 and 5 is that we will need to sum up covariances in order to establish bounds on the variance component of mean squared error for estimation of $\pi(f)$ via the dependent sample means

\begin{equation*}\frac{1}{t}\sum_{j=0}^{t-1} f(X_j), \qquad \frac{1}{t}\sum_{j=0}^{t-1} f(X^\epsilon_j)\end{equation*}

for an arbitrary starting measure. To this end we will be interested in the following summation result.

Corollary 6. Under the assumptions of Section 3.2,

1. (a) if $X_0\sim\mu$, then for $f,g\in L^{\prime}_4(\pi)$,

   \begin{align*}&\frac{1}{t^2}\sum_{m=0}^{t-1}\sum_{n=0}^{t-1} \textrm{Cov} (f(X_j),f(X_k)) \\ &\qquad\leq \frac{2 \Vert {{f - \pi f}}\Vert_{L^{\prime}_2(\pi)} ^2}{\alpha t} + \frac{2^{7/2} \Vert {{\mu -\pi}}\Vert_{L_2(\pi)} \Vert {f -\pi f} \Vert_{L_4^{\prime}(\pi)}^2}{\alpha^2 t^2} -\left(\frac{1}{t}\sum_{m=0}^{t-1}\mu P^m f-\pi f\right)^2;\end{align*}

2. (b) if $\epsilon<\alpha$, and $P_\epsilon$ is $\pi_\epsilon$-reversible, $\rho_2 = (1-(\alpha-\epsilon))$, and $X^\epsilon_0\sim\mu$, then for $f,g\in$ $L^{\prime}_4(\pi_\epsilon)$,

   \begin{align*}&\frac{1}{t^2}\sum_{m=0}^{t-1}\sum_{n=0}^{t-1} \textrm{Cov} (f(X_j^\epsilon),f(X_k^\epsilon)) \\[3pt] &\qquad\leq \frac{2 \Vert {{f - \pi f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} ^2}{(1-\rho_2) t} + \frac{2^{7/2} \Vert {{\mu -\pi}}\Vert_{L_2(\pi_\epsilon)} \Vert {f -\pi f} \Vert_{L_4^{\prime}(\pi_\epsilon)}^2}{(1-\rho_2)^2 t^2} -\left(\frac{1}{t}\sum_{m=0}^{t-1}\mu P_\epsilon^m f-\pi f\right)^2.\end{align*}

Proof. We only show the proof for the original chain. The results for the perturbed chain have essentially the same proof. The proof is largely an exercise in summation of geometric series and meticulous bookkeeping. The first inequality is due to Corollary 5. The second inequality makes use of the fact that $0<\alpha<1$. To simplify notation, $C_\mu = \Vert {{\mu-\pi}}\Vert_{L_2(\pi)} $. We have

\begin{align*} &\frac{1}{t^2}\sum_{m=0}^{t-1}\sum_{n=0}^{t-1} \textrm{Cov} (f(X_j),f(X_k))\\[2pt] &\qquad = \frac{\Vert f\Vert_\star^2}{t^2}\sum_{m=0}^{t-1}\sum_{n=0}^{t-1} (1-\alpha)^{\vert m - n\vert} -\frac{1}{t^2}\sum_{m=0}^{t-1}\sum_{n=0}^{t-1}(\mu P^m f-\pi f)\left(\mu P^n f -\pi f\right)\\[2pt] &\qquad\qquad + \frac{2^{3/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{t^2}\sum_{m=0}^{t-1}\sum_{n=0}^{t-1} (1-\alpha)^{(m+n)/2}\\[2pt] \end{align*}

\begin{align*} &\qquad = \frac{\Vert f\Vert_\star^2}{t^2}\sum_{m=0}^{t-1} \left(1+2\sum_{s=1}^{t-m-1} (1-\alpha)^{s}\right) -\left(\frac{1}{t}\sum_{m=0}^{t-1}(\mu P^m f-\pi f)\right)^2\\[2pt] &\qquad\qquad+ \frac{2^{3/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{t^2}\sum_{m=0}^{t-1}(1-\alpha)^m\left(1+2\sum_{s=1}^{t-m-1} (1-\alpha)^{s/2}\right)\\[2pt] &\qquad = \frac{\Vert f\Vert_\star^2}{t^2}\sum_{m=0}^{t-1} \left(1+2\frac{(1-\alpha)-(1-\alpha)^{t-m}}{\alpha}\right) -\left(\frac{1}{t}\sum_{m=0}^{t-1}(\mu P^m f-\pi f)\right)^2\\[2pt] &\qquad\qquad+ \frac{2^{3/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{t^2}\sum_{m=0}^{t-1}(1-\alpha)^m\left(1+2\frac{\sqrt{1-\alpha}-\sqrt{1-\alpha}^{t-m}}{1-\sqrt{1-\alpha}}\right)\\[2pt] &\qquad = \frac{\Vert f\Vert_\star^2}{t^2}\sum_{m=0}^{t-1} \left(\frac{2-\alpha}{\alpha} -\frac{2}{\alpha}(1-\alpha)^{t-m}\right) -\left(\frac{1}{t}\sum_{m=0}^{t-1}(\mu P^m f-\pi f)\right)^2\\[2pt] &\qquad\qquad+ \frac{2^{3/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{t^2}\sum_{m=0}^{t-1}\left((1-\alpha)^m\frac{1+\sqrt{1-\alpha}}{1-\sqrt{1-\alpha}}-2\frac{\sqrt{1-\alpha}^{t+m}}{1-\sqrt{1-\alpha}}\right)\\[2pt] &\qquad = \frac{\Vert f\Vert_\star^2}{t^2} \left(\frac{2-\alpha}{\alpha}t -\frac{2}{\alpha}\frac{(1-\alpha) - (1-\alpha)^{t+1}}{\alpha}\right) -\left(\frac{1}{t}\sum_{m=0}^{t-1}(\mu P^m f-\pi f)\right)^2\\[2pt] &\qquad\qquad+ \frac{2^{3/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{t^2}\left(\left[\frac{1+\sqrt{1-\alpha}}{1-\sqrt{1-\alpha}}\right]\left[\frac{1-(1-\alpha)^t}{\alpha}\right]\right.\\ &\qquad\qquad\left.-\left[\frac{2\sqrt{1-\alpha}^t}{1-\sqrt{1-\alpha}}\right]\left[\frac{1-\sqrt{1-\alpha}^{t}}{1-\sqrt{1-\alpha}}\right]\right) \\ &\qquad = (2-\alpha)\frac{\Vert f\Vert_\star^2}{\alpha t} - 2(1-\alpha)\frac{1-(1-\alpha)^t}{\alpha^2 t^2} -\left(\frac{1}{t}\sum_{m=0}^{t-1}(\mu P^m f-\pi f)\right)^2\\ &\qquad\qquad+ \frac{2^{3/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{t^2}\left(\frac{1+\sqrt{1-\alpha}}{\alpha}\right)^2(1-(1-\alpha)^{t/2})^2\\ &\qquad \leq \frac{2\Vert f\Vert_\star^2}{\alpha t} + \frac{2^{7/2} C_\mu \Vert f \Vert_{{}_{\star\star}}^2}{\alpha^2 t^2} -\left(\frac{1}{t}\sum_{m=0}^{t-1}(\mu P^m f-\pi f)\right)^2. \end{align*}

A.3.3 Mean squared error bounds

\begin{align*} \\[-35pt] \end{align*}

Theorem 7. Under the assumptions of Section 3.2, if $X_0\sim\mu\in L_2(\pi)$, then

\begin{align*}&\mathbb{E}\left[\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1}f(X_k)\right)^2\right] \leq \frac{2\Vert f - \pi f\Vert_2^2}{\alpha t} + \frac{2^{7/2} \Vert \mu -\pi\Vert_2 \Vert f -\pi f \Vert_4^2}{\alpha^2 t^2}.\end{align*}

Proof. The proof proceeds by partitioning the mean squared error via the bias-variance decomposition, then bounding the variance term and noting that our bound for the variance contains an expression which exactly cancels the bias term. We compute that

\begin{align*}& \mathbb{E}\left[\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1}f(X_k)\right)^2\right]\\ &=\mathbb{E}\left[\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1} [\mu P^k](f) - \frac{1}{t}\sum_{k=0}^{t-1} (f(X_k)-[\mu P^k](f))\right)^2\right]\\ &=\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1} [\mu P^k](f)\right)^2 +\mathbb{E}\left[\left(\frac{1}{t}\sum_{k=0}^{t-1} (f(X_k)-[\mu P^k](f))\right)^2\right]\\ &=\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1} [\mu P^k](f)\right)^2 +\frac{1}{t^2}\sum_{j=0}^{t-1}\sum_{k=0}^{t-1} \textrm{Cov} (f(X_j),f(X_k)).\end{align*}

The variance term is bounded using Corollary 6:

\begin{align*}&\frac{1}{t^2}\sum_{j=0}^{t-1}\sum_{k=0}^{t-1} \textrm{Cov} (f(X_j),f(X_k))\\ &\qquad\frac{2\Vert f - \pi f\Vert_2^2}{\alpha t} + \frac{2^{7/2} \Vert \mu -\pi\Vert_2 \Vert f -\pi f \Vert_4^2}{\alpha^2 t^2} -\left(\frac{1}{t}\sum_{m=0}^{t-1}\mu P^m f-\pi f\right)^2.\end{align*}

Putting these together yields the desired result.

Remark 9. We note that, as per Remark 8, $\Vert f - \pi f\Vert \leq \Vert f\Vert_2 $. Similarly $\Vert f-\pi f\Vert_4\leq \Vert f\Vert_4$. Also, in the case that f is is $\pi$-essentially bounded, $\Vert f\Vert_2 \leq \Vert f\Vert_\infty$ and $\Vert f\Vert_4 \leq \Vert f\Vert_\infty$. These alternative norms may be substituted into the result as necessary in order to make the bounds tractable for a given application.

Remark 10. Comparing our above geometrically ergodic results to the $L_1$ results of [Reference Johndrow, Mattingly, Mukherjee and Dunson18] in the uniformly ergodic case, we see that the $L_2$ and $L_1$ bounds we establish above differ from the corresponding $L_1$ bound of [Reference Johndrow, Mattingly, Mukherjee and Dunson18] only by a factor, which is constant in time, but varies with the initial distribution (as is to be expected when moving from uniform ergodicity to geometric ergodicity). For the mean squared error results, the $\Vert\cdot\Vert_\star$-norm in that paper is based on the midrange-centred infinity norm, which as per Remark 9 is an upper bound on what we have.

Proof of Theorem 5. For the first result, we proceed via bias-variance decomposition, as in the corresponding result for the exact chain. However, now the bias under consideration is itself decomposed as the square of a sum of two components. The squared sum is expanded simultaneously with the bias-variance expansion. We compute that

\begin{align*}& \mathbb{E}\left[\left(\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1}f(X^\epsilon_k)\right)^2\right]\\ &=\mathbb{E}\left[\left(\pi(f) - \pi_\epsilon(f) + \frac{1}{t}\sum_{k=0}^{t-1} \left[\pi_\epsilon - \mu P_\epsilon^k\right](f) - \frac{1}{t}\sum_{k=0}^{t-1} (f(X^\epsilon_k)-[\mu P_\epsilon^k](f))\right)^2\right] \end{align*}

\begin{align*} \\[-25pt] &=\left([\pi-\pi_\epsilon](f)\right)^2 +2\left([\pi-\pi_\epsilon](f)\right)\left(\pi_\epsilon(f) - \frac{1}{t}\sum_{k=0}^{t-1} [\mu P_\epsilon^k](f)\right)\\[3pt] & + \left(\pi_\epsilon(f) - \frac{1}{t}\sum_{k=0}^{t-1} [\mu P_\epsilon^k](f)\right)^2 +\frac{1}{t^2}\sum_{j=0}^{t-1}\sum_{k=0}^{t-1} \textrm{Cov} (f(X^\epsilon_j),f(X^\epsilon_k)).\end{align*}

We bound the first component of the bias term using versions of Lemma 6:

\begin{align*} \left([\pi-\pi_\epsilon](f)\right)^2 & = \left([\pi-\pi_\epsilon](f-\pi_\epsilon f)\right)^2 \\[3pt] & \leq \begin{cases} \Vert {\pi-\pi_\epsilon}\Vert_{L_2(\pi)} ^2 \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi)} ^2 & \\[3pt] \Vert {{\pi-\pi_\epsilon}}\Vert_{L_2(\pi_\epsilon)} ^2 \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} ^2 & \\[3pt] \end{cases}\\[3pt] & \leq \begin{cases} \frac{\epsilon^2}{\alpha^2 - \epsilon^2} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi)} ^2 & \\[3pt] \frac{\varphi^2}{(1-\rho_2)^2 - \varphi^2} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} ^2 &:\text{given } (*). \end{cases}\end{align*}

We bound the variance term using Corollary 6:

\begin{align*}& \frac{1}{t^2}\sum_{j=0}^{t-1}\sum_{k=0}^{t-1} \textrm{Cov}(f(X^\epsilon_j),f(X^\epsilon_k))\\[3pt] &\qquad\leq \frac{2 \Vert {{ f - \pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} ^2}{(1-\rho_2) t} + \frac{2^{7/2} \Vert {{ \mu -\pi_\epsilon}}\Vert_{L_2(\pi_\epsilon)} \Vert {f -\pi_\epsilon f } \Vert_{L_4^{\prime}(\pi_\epsilon)}}{(1-\rho_2)^2 t^2} -\left(\frac{1}{t}\sum_{m=0}^{t-1}\mu P_\epsilon^m f-\pi_\epsilon f\right)^2.\end{align*}

The negative term in this expression exactly cancels out the third bias term in the expansion.

Finally, we bound the second bias term using Lemma 6 and Theorem 4:

\begin{align*} & 2\left ({[\pi-\pi_\epsilon](f)}\right) \left ({\pi_\epsilon(f) -\frac{1}{t}\sum_{k=0}^{t-1} [\mu P_\epsilon^k](f)}\right)\\[3pt] & = 2\left ({[\pi-\pi_\epsilon](f-\pi_\epsilon f)}\right) \left ({\left [{\pi_\epsilon-\frac{1}{t}\sum_{k=0}^{t-1} \mu P_\epsilon^k }\right] (f-\pi_\epsilon f)}\right) \\[3pt] & \leq 2 \begin{cases} \frac{\varphi}{\sqrt{(1-\rho_2)^2 - \varphi^2}} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi)} \frac{1-(1-(\alpha-\epsilon))^t}{t(\alpha-\epsilon)} \Vert {{ \pi_\epsilon-\mu}}\Vert_{L_2(\pi)} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi)} & \\[3pt] \frac{\varphi^2}{(1-\rho_2)^2 - \varphi^2} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} ^2 \frac{1-\rho_2^t}{t(1-\rho_2)} \Vert {{ \pi_\epsilon-\mu}}\Vert_{L_2(\pi_\epsilon)} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} &:\,\text{given } (*) \end{cases} \\[3pt] & \leq 2 \begin{cases} \frac{\epsilon}{\sqrt{\alpha^2 - \epsilon^2}}\frac{1}{t(\alpha-\epsilon)} \Vert {{\pi_\epsilon-\mu}}\Vert_{L_2(\pi)} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi)} ^2 & \\[3pt] \frac{\varphi}{\sqrt{(1-\rho_2)^2 - \varphi^2}} \frac{1}{t(1-\rho_2)} \Vert {{ \pi_\epsilon-\mu}}\Vert_{L_2(\pi_\epsilon)} \Vert {{f-\pi_\epsilon f}}\Vert_{L^{\prime}_2(\pi_\epsilon)} ^2 &:\text{given } (*). \end{cases}\end{align*}

Putting these together yields the first and third results.

For the second and fourth results we use the fact that for any random variable Z and for any $a,b\in\mathbb{R}$ the following holds:

\begin{align*}\mathbb{E}[(Z-a)^2] &= 2\mathbb{E}[(Z-b)^2]+2(a-b)^2 - \mathbb{E}[(Z+a-2 b)^2]\\ &\leq 2\mathbb{E}[(Z-b)^2]+2(a-b)^2.\end{align*}

We have

\begin{align*}& \mathbb{E}\left [{\left ({\pi(f) - \frac{1}{t}\sum_{k=0}^{t-1}f(X^\epsilon_k)}\right)^2}\right]\\ &\qquad\leq 2([\pi-\pi_\epsilon](f))^2 +2 \mathbb{E}\left [{\left ({\pi_\epsilon(f) - \frac{1}{t}\sum_{k=0}^{t-1} f(X^\epsilon_k)}\right)^2}\right]\\ &\qquad= 2([\pi-\pi_\epsilon](f-\pi_\epsilon f))^2 \\ &\qquad\qquad+2 \mathbb{E}\left [{\left ({\pi_\epsilon(f)-\frac{1}{t}\sum_{k=0}^{t-1} [\mu P_\epsilon^k](f) - \frac{1}{t}\sum_{k=0}^{t-1} (f(X^\epsilon_k)-[\mu P_\epsilon^k](f))}\right)^2}\right] \end{align*}

\begin{align*} \\[-35pt] &\qquad= 2([\pi-\pi_\epsilon](f-\pi_\epsilon f))^2 +2\left ({\pi_\epsilon(f)-\frac{1}{t}\sum_{k=0}^{t-1}[\mu P_\epsilon^k](f)}\right)^2\\ &\qquad\qquad+2\mathbb{E}\left [{\left ({\frac{1}{t}\sum_{k=0}^{t-1} (f(X^\epsilon_k)-[\mu P_\epsilon^k](f))}\right)^2}\right] \\ &\qquad= 2([\pi-\pi_\epsilon](f-\pi_\epsilon f))^2 +2\left ({\pi_\epsilon(f)-\frac{1}{t}\sum_{k=0}^{t-1}[\mu P_\epsilon^k](f)}\right) ^2\\ &\qquad\qquad+\frac{2}{t^2}\sum_{j=0}^{t-1}\sum_{k=0}^{t-1} \textrm{Cov} (f(X^\epsilon_j),f(X^\epsilon_k)).\end{align*}

Applying Corollary 5 to bound the sum of covariances, we find that we are able to exactly cancel the second term in the final expression above. Using the same bound as before for the first expression, we get the final result.