Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Intuitively, I've been able to understand the Metropolis-Hastings ratio as a trade off between how much time we should be spending at the candidate point (the numerator) versus how easy it is to reach the candidate point (the denominator).

Then, if our candidate, $x_{new}$, is easy to get to (large denominator) but we shouldn't be spending much time there (small numerator) then the ratio is small and we accept the new candidate with a lower probability.

Conversely, if our candidate is hard to get to (small denominator) but we should be spending lots of time there (i.e. $x_{new}$ is very likely given our target distribution) then the ratio is large and we accept the move with high probability.

share|improve this answer
add comment

The way I think about the Metropolis rule is like this. Suppose I want to preserve some distribution $P(x),$ by a transition $Q(x \to y)$. I can impose a strictly stronger condition, namely detailed balance. This says that $Q$ should carry an equal amount of mass between any two points (rather than just balancing overall). That looks like $P(x) Q(x \to y) = P(y) Q(y \to x).$ This doesn't hold, but we can alter it in the following simple way: suppose that the left hand side is larger. Just alter $Q(x \to y)$ by multiplying by $\alpha = \frac{Q(y \to x)}{Q(x \to y)} \frac{P(y)}{P(x)}$, and setting $\tilde{Q}(x \to y) = \alpha Q(x \to y)$, and $\tilde{Q}(y \to x) = Q(y \to x).$ We can simulate this by drawing from $Q$ and accepting steps from $x \to y$ with probability $\alpha.$

Basically, look at the would-be equation of detailed balance, scale down the larger side to make it true by definition. Realize that scaling by randomly thinning steps.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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