5
$\begingroup$

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

Problem

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?

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

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

$\endgroup$
  • $\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 Jan 10 '16 at 4:37

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.