Question about this ratio in Metropolis-Hastings MCMC algorithm - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:44:48Z http://mathoverflow.net/feeds/question/27090 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27090/question-about-this-ratio-in-metropolis-hastings-mcmc-algorithm Question about this ratio in Metropolis-Hastings MCMC algorithm Frankie 2010-06-04T19:48:59Z 2010-06-04T20:29:44Z <p>I have a stupid question about the <a href="http://en.wikipedia.org/wiki/Metropolis%25E2%2580%2593Hastings_algorithm" rel="nofollow">Metropolis-Hastings sampling algorithm</a>. </p> <p>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 &lt; \min{1,\frac{P(x_{new})}{P(x_{old})}\frac{Q(x_{old}\mid x_{new})}{Q(x_{new}\mid x_{old})}}$</p> <p>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? </p> http://mathoverflow.net/questions/27090/question-about-this-ratio-in-metropolis-hastings-mcmc-algorithm/27101#27101 Answer by Dan Piponi for Question about this ratio in Metropolis-Hastings MCMC algorithm Dan Piponi 2010-06-04T20:23:23Z 2010-06-04T20:23:23Z <p>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.</p> <p>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.</p> <p>(BTW The $min$ in your expression is redundant.)</p> http://mathoverflow.net/questions/27090/question-about-this-ratio-in-metropolis-hastings-mcmc-algorithm/27102#27102 Answer by Alekk for Question about this ratio in Metropolis-Hastings MCMC algorithm Alekk 2010-06-04T20:29:44Z 2010-06-04T20:29:44Z <p>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.</p> <p>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}}$.</p> <p>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}$.</p>