Unbiased Metropolis-Hastings estimator of the form $\frac{\sum_{i=1}^nW_if(Y_i)}{\sum_{i=1}^nW_i}$. How do we need to choose $W_i$?

Question

Let $(X_n)_{n\in\mathbb N_0}$ be the Markov chain generated by the Metorpolis-Hastings algorithm with proposal kernel $Q$ and target distribution $\mu$ and $(Y_n)_{n\in\mathbb N}$ denote the corresponding proposal sequence. Say we want to consider an estimator $A_nf$ for $\mu f$, $f\in L^1(\mu)$, of the form $$A_nf=\frac{\sum_{i=1}^nW_if(Y_i)}{\sum_{i=1}^nW_i}.$$

How do we need to choose the weights $W_i$ if $A_nf$ is supposed to be an unbiased estimator?

Assume $Q$ and $\mu$ admit densities $q$ and $p$ with respect to a common reference measure $\lambda$. In this paper, it is claimed that, assuming $\{p>0\}\subseteq\{q(x,\;\cdot\;)>0\}$ for all $x$, $W_i=\rho(X_{i-1},Y_i)$, where $$\rho(x,y):=\begin{cases}\displaystyle\frac{p(y)}{q(x,y)}&\text{, if }p(y)>0\\0&\text{, otherwise}\end{cases},$$ is a possible choice.

How do we prove that the estimator is unbiased with this choice of $W_i$? And are other choices of $W_i$ possible? I could imagine that $W_i$ might depend on $X_0,\ldots,X_{i-1},Y_1,\ldots,Y_i$.

Answer 1

A partial answer: in the paper you reference, the unbiasedness is essentially a byproduct of the equality

\begin{align} \int \int p ( x ) q ( x, y ) \cdot \rho ( x, y ) g ( y ) \, dx \, dy &= \int \int p ( x ) p ( y ) g ( y ) \, dx \, dy \\ &= \int p ( y ) g ( y ) \, dy. \end{align}

Note that:

• Finite-time unbiasedness will generally not hold, unless the Markov chain is initialised at equilibrium (i.e. with a draw from $p$), which is typically difficult.
• Moreover, the importance sampling estimator you include is a ratio of estimators, which typically makes it difficult to establish unbiasedness for finite $n$. Fortunately, this is usually less of an issue when considering $n$ going to $\infty$.

If I remember correctly, it's also the case that the weights used in the paper are not quite $\rho = p / q$, but a constant multiple of this expression, where the constant is unknown. This doesn't get in the way of showing unbiasedness, but does explain why the ratio-type estimator is used; one is doing something a bit closer to self-normalised importance sampling.

To make other choices of weights, the following advice might be useful:

• To obtain unbiasedness, one should construct weights $\rho$ which admit some sort of simplification, as in the integral expression at the beginning of this answer.
• When performing importance sampling, one is comparing a distribution which you can sample from to one from which you cannot sample. The latter is usually your target distribution, i.e. $p$, and the former is some distribution which you have algorithmic access to. As such, it is simpler to think in terms of 'which importance distributions are available for me to sample from?' rather than 'which importance-weighting scheme should I use?'.
• Basic importance sampling generally performs worse as the dimensionality of the problem increases, and so in some sense, you would like your importance distribution to be as low-dimensional as possible. As such, if one constructed importance weights involving more points (e.g. looking at $\{ X_{t-2}, X_{t-1}, Y_t \}$, then one could reasonably expect the weights to become more singular, and worsen the variance of the estimator.