I have a question concerning about one step in the Metropolis algorithm. The algorithm proceeds as following,

  1. Generate a proposed new sample value from the jumping distribution $Q(x'|x_t)$
  2. Calculate the acceptance ratio $a = \frac{P(x')}{P(x_t)}$
  3. If $a\geq 1$, accept $x'$ by setting $x_{t+1}= x'$
  4. Else, accept $x'$ with probability $a$. That is, pick a uniformly distributed random number $r$ between 0 and 1, and if $r\leq a$ set $x_{t+1}=x'$, else set $x_{t+1} = x_t$

I feel unclear about step 4, in step 4 if we have $a<1$, which means $P(x_t)>P(x')$, $x'$ is further away from the large mass of the density than $x_t$. However, we are not dumping $x'$ directly, we leave it to a 'gamble' to decide its go or stay. This gamble is the uniform distribution, a random draw from uniform distribution then compare it with $a$. I do not understand what's happening here. Why won't we just dump $x'$, why we have to give it a chance to 'nature'?

  • $\begingroup$ @Procrastinator, I actually have paraphrased this idea in my question description. But what puzzles me is that what is the purpose of using uniform distribution to compare with $a$ here? And why? $\endgroup$ – Flying pig Oct 27 '12 at 16:57
  • $\begingroup$ Though I am still learning MCMC, I like to think if $a<1$, then we resort to the Acceptance-Rejection algorithm. The algorithm is almost identical and explains where the Uniform distribution comes in. $\endgroup$ – Cam.Davidson.Pilon Oct 27 '12 at 18:50

The scheme you propose is strictly ascending the probability gradient. Think what would happen: you would end up at $x$ such that $P(x)$ is maximal and you would stay there for ever. In the end, the sample you generate would consist mostly of $x$, whatever the size of the sample, so the distribution of that sample would not be close to $P$.

Also bear in mind that the probability to simulate could be bimodal. In that case, it is beneficial to accept an $x$ with low probability to be able to go from one mode to the other.

Actually, it is OK to accept an $x$ with low $P(x)$, as long as the overall acceptance ratio is not bigger than $P(x)$. That this is the case with the Metropolis-Hastings is a little hard to prove though.


The physical origin of this algorithm is some way to get intuition -- in that case, we have energies of states instead of probabilities and a system which is in a state $x_t$ and can go or not in a state $x'$.
Now, isolated system will always go into a lower energy and never into higher and thus the overall distribution would be trivial -- system is stuck forever in a lowest energy state.

But when we have canonical ensemble (i.e. system connected to a thermal booth of some defined temperature) our system can get a random kick from thermal fluctuation that will push it up to a higher energy; the resulting distribution would be the Boltzmann's $N_i=Q e^\frac{-E_i}{kT}$ (where $Q$ is a normalisation factor, $k$ a magic constant converting temperature to a sort of an average thermal kick amplitude and $T$ is the system's temperature). So the conditional acceptance part is just an expression of a stochastic nature of the thermal kicks.


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.