Let's say I have some MCMC algorithm implemented as a function, black_box(x), which generates samples from $P(x)$ when run in a chain. I would now like to sample from $P(x)G(x)$. Is it possible to use black_box(x) as proposal distribution and then use Independent Metropolis, i.e.:

1) Let x' = black_box(x).

2) Accept with probability min(1, G(x') / G(x))

3) Loop to 1)

How can I prove that this works?

First attempt

Let B(x -> x') be the probability that black_box(x) returns x'. Assuming that black_box(x) implements a Metropolis-Hastings algorithm, we know that it fulfills detailed balance, i.e.

$\frac{B(x \rightarrow x')}{B(x' \rightarrow x)} = \frac{P(x')}{P(x)}$

If we choose our acceptance probability as

$A(x \rightarrow x') = \min(1, \frac{G(x')}{G(x)})$

the overall transition probability fulfills detailed balance since

$\frac{B(x \rightarrow x')A(x \rightarrow x')}{B(x' \rightarrow x)A(x' \rightarrow x)} = \frac{P(x')\min(1, G(x') / G(x))}{P(x)\min(1, G(x) / G(x'))} = \frac{P(x')G(x')}{P(x)G(x)}$ (since either $\frac{G(x)}{G(x')} \gt 1$ or $\frac{G(x)}{G(x')} \le 1$).


However, the above doesn't work in the general case, since there are MCMC algorithms that does not guarantee detailed balance. For example, each sweep of the deterministic sweep Gibbs sampler does not satisfy detailed balance. Is there a way to fix the above solution to make it work, or is it impossible? What requirements does black_box(x) have to fulfill in order to allow it to be used as a proposal distribution?

  • $\begingroup$ I'd like to know why this question was voted down. It looks interesting and shows thought. $\endgroup$
    – Yair Daon
    Commented Jan 9, 2016 at 21:42

1 Answer 1


It a nearly equivalent way to do this is via importance sampling. In other words,

1) Draw $M$ samples from $P(X)$. Let's call these samples $X'$.

2) Get importance weights by computing $w = G(X')$

3) Calculate whatever statistic you want (i.e. mean, sd, etc) by the weights incorporation $w' = \frac{w}{\sum w}$

4) If you want to get an unweighted sample from P(X)G(X), draw from $X'$ with probability $w'$

  • $\begingroup$ Unfortunately this requires $M \rightarrow \infty$, and this is taking place within a larger MCMC algorithm, so I can't let $M$ be too large. $\endgroup$
    – yong
    Commented Jan 10, 2016 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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