Question about this ratio in Metropolis-Hastings MCMC algorithm - MathOverflow

Question about this ratio in Metropolis-Hastings MCMC algorithm

2010-06-04T19:48:59Z

I have a stupid question about the Metropolis-Hastings sampling algorithm.

If I got this right, for every variable $X$ in turn, which currently has value $x_{old}$, you generate a new sample $x_{new}$. To do that, you draw $x_{new}$ from the proposal distribution $Q(x_{new}\mid x_{old})$, then you draw a number $\alpha$ uniformly at random from the range between $0$ and $1$. Then, accept $x_{new}$ if $\alpha < \min{1,\frac{P(x_{new})}{P(x_{old})}\frac{Q(x_{old}\mid x_{new})}{Q(x_{new}\mid x_{old})}}$

The second ratio does not really make sense to me: Why are we more likely to accept if $Q(x_{new}\mid x_{old})$ is low?

Answer by Dan Piponi for Question about this ratio in Metropolis-Hastings MCMC algorithm

2010-06-04T20:23:23Z

From what you're saying, I'm not sure if you want a proof or intuition. As the proof is written up in many places, I'll just guess that you want intuition.

Very informally: the algorithm allows you to, in effect, sample from distribution P using samples from distribution Q. So in a sense we want to take the samples from Q and "remove" statistical properties of these samples that reveal that they come from Q, replacing them with the properties of P. The thing that "gives away" that they came from Q is that they're more likely to come from areas where Q is high. So we want our acceptance probability to be reduced when our samples come from such an area. That's exactly what dividing by $Q(x_{new}|x_{old})$ does.

(BTW The $min$ in your expression is redundant.)

Answer by Alekk for Question about this ratio in Metropolis-Hastings MCMC algorithm

2010-06-04T20:29:44Z

if the kernel $Q$ is symmetric (ie: $Q(x,y)=Q(y,x)$), the Metropolis ratio reduces to $$ 1 \wedge \frac{P(x_{new})}{P(x_{old})}. $$ This is a stochastic gradient ascent: there is a drift towards the highly probable configurations.

Now, if the kernel $Q$ is not symmetric, you also have to take this into account: it is possible that the Kernel $Q$ is strongly biased towards certain configurations that are not likely to happen under the target distribution $P(\cdot)$ and you have to correct that - this is what the additional term $\frac{Q(x_{old}|x_{new})}{Q(x_{new}|x_{old}}$.

Take the example of a Markov chain on ${1,2,\ldots,N}$, with uniform target distribution $P(k)=\frac{1}{N}$, and with proposal kernel $Q(k+1|k)=1-Q(k-1|k)=0.99$ (and do something different at the boundary). The Kernel $Q$ pushes you strongly towards high values of the interval ${1,2,\ldots,N}$ - nevertheless the Metropolis ratio is always equal to $1$ so that all the moves are accepted: this is clearly wrong. The Metropolis-Hasting ratio corrects that and takes the asymmetry of $Q$ into account: a move from $k$ to $k+1$ is accepted with probability only equal to $\frac{0.01}{0.99}$.