# Central limit theorem for a Metropolis-Hastings estimator

Let $$\alpha$$ denote the acceptance function of the Markov chain $$(X_n)_{n\in\mathbb N_0}$$ generated by the Metropolis-Hastings algorithm with proposal kernel $$Q$$ and target distribution $$\mu^1$$ and $$(Y_n)_{n\in\mathbb N}$$ denote the corresponding proposal sequence. Now let $$f\in L^1(\mu)$$ and consider the estimator $$A_nf:=\frac1n\sum_{i=1}^n((1-\alpha(X_{i-1},Y_i))f(X_{i-1})+\alpha(X_{i-1},Y_i)f(Y_i))\;\;\;\text{for }n\in\mathbb N$$ of $$\mu f:=\int f\:{\rm d}\mu$$.

Are we able to prove a central limit theorem $$\sqrt n(A_nf-\mu f)\xrightarrow{n\to\infty}\mathcal N_{0,\:\sigma^2(f)}\tag1$$ in distribution? If so, can we give a closed form expression for $$\sigma^2(f)$$? In particular, will $$n\operatorname{Var}[A_nf]\xrightarrow{n\to\infty}\sigma^2(f)\tag2$$ hold?

Note that $$Z_n:=(X_{n-1},Y_n)\;\;\;\text{for }n\in\mathbb N$$ is again a time-homogeeous Markov chain with transition kernel $$\kappa_{\text{aug}}((x,y),A\times B):=1_A(x)(1-\alpha(x,y))Q(x,B)+1_A(y)\alpha(x,y)Q(y,B)$$ for $$x,y\in E$$ and $$A,B\in\mathcal E$$ and stationary distribution $$\nu:=\mu\otimes Q$$. (In general, $$\nu$$ is not reversible with respect to $$\kappa_{\text{aug}}$$. Are we able to show the reversibility under the assumption that $$q$$ is symmetric? If you know the answer, please take a look at my corresponding separate question: Is the stationary distribution of the augmented Metropolis-Hastings kernel even reversible in the symmetric proposal case?.)

Remark: Note that the paper On a Metropolis-Hastings importance sampling estimator contains a related result in Theorem 15 (cf. Theorem 4).

$$^1$$ To be precise, let

• $$(E,\mathcal E,\lambda)$$ be a measure space;
• $$p$$ be a probability density on $$(E,\mathcal E,\lambda)$$ and $$\mu:=p\lambda$$;
• $$q:E^2\to[0,\infty)$$ be $${\mathcal E}^{\otimes2}$$-measurable with $$\int\lambda({\rm d}y)q(x,y)=1\;\;\;\text{for all }x\in E$$ and $$Q(x,\;\cdot\;):=q(x,\;\cdot\;)\lambda\;\;\;\text{for }x\in E;$$
• $$\alpha(x,y):=\left.\begin{cases}\displaystyle1\wedge\frac{p(y)q(y,x)}{p(x)q(x,y)}&\text{, if }p(x)q(x,y)\ne0\\1&\text{, otherwise}\end{cases}\right\}\;\;\;\text{for }x,y\in E$$ and $$\kappa(x,B):=\int_BQ(x,{\rm d}y)\alpha(x,y)+\left(1-\int Q(x,{\rm d}y)\alpha(x,y)\right)1_B(x)\;\;\;\text{for }(x,B)\in E\times\mathcal E.$$

## 1 Answer

Since $$[\{1-\alpha(X_{i-1},Y_i)\}f(X_{i-1})+\alpha(X_{i-1},Y_i)f(Y_i)]= \overbrace{\mathbb E[f(X_i)|X_{i-1},Y_i]}^\text{integrating out U_i}=H(X_{i-1},Y_i)$$ the sum$$A_nf=\frac{1}{n}\sum_{i=1}^n H(X_{i-1},Y_i)$$satisfies the standard ergodic theorem for the Markov chain $$(X_{i-1},Y_i)$$ and under geometric ergodicity satsfies a Central Limit theorem with asymptotic variance $$\text{var}(\mathbb E[f(X_2)|X_{1},Y_2])+2\sum_{t=1}^\infty \text{cov}(\mathbb E[f(X_2)|X_{1},Y_2],\mathbb E[f(X_{t+2})|X_{t+1},Y_{t+2}])$$

• Ah, I see. If we define $$H((x,y),\;\cdot\;):=(1-\alpha(x,y))\delta_{(x,\:y)}+\alpha(x,y)\delta_{(y,\:x)},$$ then $\operatorname E\left[f(X_n)\mid Z_n\right]=(H\tilde f)(Z_n)$, where $\tilde f(x,y):=f(x)$. Note that, while I know what it should be, there is no $U_i$ in the question. So, your answer might be hard to understand for someone else. – 0xbadf00d Oct 21 '19 at 9:17
• Can we simplify your expression for the asymptotic variance? We may note that $\nu$ is reversible with respect to $H$ (the $H$ from my comment above). I know that if $g\in L^2(\nu)$ is a solution of $(1-\kappa_{\text{aug}})g=h$, where $h=H\tilde f$, then the asymptotic variance is given by $2\operatorname{Cov}_\nu[g,h]-\operatorname{Var}_\nu[h]$. This could be use to perform a worst case analysis, but I've got the feeling that things are easier here for our special choice of $h$. – 0xbadf00d Oct 21 '19 at 13:40
• I'll answer some of my questions by myself: (a) I guess it's just a typo in your answer, but it seems like your indices are off by $1$. The asymptotic variance should be $$\sigma^2(f):=\operatorname{Var}\left[\operatorname E\left[f_0(X_1)\mid Z_1\right]\right]+2\sum_{n=1}^\infty\operatorname{Cov}\left[\operatorname E\left[f_0(X_1)\mid Z_1\right],\operatorname E\left[f_0(X_{1+n})\mid Z_{1+n}\right]\right],$$ where (for further reference) $f_0:=f-\mu f.$ – 0xbadf00d Oct 22 '19 at 9:46
• (b) Assuming $(Z_n)_{n\in\mathbb N}$ is stationary, we should have $$\sigma^2(f)=\operatorname{Var}_\nu[g_0]+2\sum_{n=1}^\infty\operatorname{Cov}_\nu\left[\kappa^n_{\text{aug}}g_0,g_0\right],$$ where $g_0:=H\tilde f_0$ and $\tilde f_0(x,y):=f_0(x)$ for $x,y\in E$. – 0xbadf00d Oct 22 '19 at 9:47
• (c) We may note that $\nu g_0=\nu\tilde f_0=\mu f_0=0$. Moreover, for arbitrary $g_0\in L^2(\nu)$ with $\nu g_0=0$ such that $Gg_0:=\sum_{n=0}^\infty\kappa_{\text{aug}}^ng_0$ exists, $n\operatorname{Var}\left[B_ng_0\right]\xrightarrow{n\to\infty}\sigma^2(g_0),$ where $$B_ng_0:=\frac1n\sum_{i=1}^ng_0(Z_i)$$ (the reason is that $(1-\kappa_{\text{aug}})^{-1}g_0=Gg_0$). For our special choice of $g_0$, $Bng_0=A_nf_0=A_nf$. Is there an easy criterion on $f$ ensuring that $Gg_0$ exists or should I search for a more general criterion on the existence of the asymptotic variance? – 0xbadf00d Oct 22 '19 at 9:52