# 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$?

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

• To clarify - do you want to show unbiasedness for finite $n$, or asymptotic unbiasedness as $n \to \infty$?
– πr8
Dec 16, 2019 at 21:15
• @πr8 Ah, I guess with the choice in the paper the estimator is only "asymptotically unbiased" (just to be sure, this is supposed to mean that a strong law of large numbers hold, right?). In any case, I'm interested in both. Dec 17, 2019 at 5:34
• Yes, correct - in the paper, the estimator is asymptotically unbiased, and so an SLLN holds.
– πr8
Dec 17, 2019 at 10:45

## 1 Answer

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.
• Regarding the weights: Note that they don't assume $p$ to be a probability density and hence need to normalize it. So, the $p$ in my question is the already normalized density. Dec 17, 2019 at 14:07
• @0xbadf00d Okay - note that it will then usually be the case that you cannot evaluate $p$ directly, because of this normalisation, hence the need for the ratio estimator.
– πr8
Dec 17, 2019 at 14:17
• Sure. I only didn't want to make this question more complicated. Dec 17, 2019 at 14:47