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.$$

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}])$$

  • 1
    $\begingroup$ 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. $\endgroup$ – 0xbadf00d Oct 21 '19 at 9:17
  • $\begingroup$ 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$. $\endgroup$ – 0xbadf00d Oct 21 '19 at 13:40
  • 1
    $\begingroup$ 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.$ $\endgroup$ – 0xbadf00d Oct 22 '19 at 9:46
  • 1
    $\begingroup$ (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$. $\endgroup$ – 0xbadf00d Oct 22 '19 at 9:47
  • 1
    $\begingroup$ (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? $\endgroup$ – 0xbadf00d Oct 22 '19 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.