# Questions about acceptance rule of Metropolis algorithm

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

• @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? – Flying pig Oct 27 '12 at 16:57
• 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. – 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.