# Accept rate in Metropolis–Hastings algorithm

In the Metropolis–Hastings algorithm for sampling a target distribution. let

• $\pi_{i}$ be the target density at state $i$,
• $\pi_j$ be the target density at the proposed state $j$,
• $h_{ij}$ be the proposal density for transition to state $j$ given current state $i$,
• $a_{ij}$ be the accept probability of proposed state $j$ given current state $i$.

Then by the detailed balance equation, after choosing the proposal density $h$, the accept probabilities $a$ is computed as $$a_{ij} = \min(1, \frac{\pi_{j} h_{ji}}{\pi_{i} h_{ij}}).$$

If $h$ is symmetric, i.e. $h_{ij}=h_{ji}$, then $$a_{ij} = \min(1, \frac{\pi_{j}}{\pi_{i}}).$$

When $h_i$ is a Guassian distribution centered at state $i$ and has the same variance $\sigma^2$ for all $i$, $h$ is symmetric. From Wikipedia:

If $\sigma^2 \,$ is too large, almost all steps under the MH algorithm will be rejected. On the other hand, if $\sigma^2 \,$ is too small, almost all steps will be accepted.

I wonder why the accept probability changes in the reverse direction of the change of variance of the proposal density, as mentioned in the above quote?

Thanks!

-
There is a problem with your formulation: you use a finite state space to define target, proposal, and acceptance probability, but a Gaussian distribution operating on a continuous space as your example. –  Xi'an May 7 '12 at 9:19
@Xi'an: Thanks! I was aware of the difference between discrete and continuous sample space, when I posted the question. So in my formulation, there are density functions for the target and proposal distributions, while it is probability for the acceptance distribution. I fail to see what are not correct. I wonder if you could point them out? –  Tim May 7 '12 at 12:55
In your formulation, target and proposal sound like probability mass functions, not density functions. Or else it is very confusing to use symbols usually reserved for integers... I mean, $h_{ij}$ looks like a matrix element. This is why I feel the Gaussian proposal does not fit. –  Xi'an May 7 '12 at 19:51

There are two basic assumptions that lead to this relationship:

1. The stationary distribution $\pi(\cdot)$ doesn't change too quickly (i.e. it has a bounded first derivative).
2. Most of the probability mass of $\pi(\cdot)$ is concentrated in a relatively small subset of the domain (the distribution is "peaky").

Let's consider the "small $\sigma^2$" case first. Let $x_i$ be the current state of the Markov chain and $x_j \sim \mathcal{N}(x_i, \sigma^2)$ be the proposed state. Since $\sigma^2$ is very small, we can be confident that $x_j \approx x_i$. Combining this with our first assumption, we see that $\pi(x_j) \approx \pi(x_i)$ and thus $\frac{\pi(x_j)}{\pi(x_i)} \approx 1$.

The low acceptance rate with large $\sigma^2$ follows from the second assumption. Recall that approximately $95\%$ of the probability mass of a normal distribution lies within $2\sigma$ of its mean, so in our case most proposals will be generated within the window $[x_i - 2\sigma, x_i + 2\sigma]$. As $\sigma^2$ gets larger, this window expands to cover more and more of the variable's domain. The second assumption implies that the density function must be quite small over most of the domain, so when our sampling window is large $\pi(x_j)$ will frequently be very small.

Now for a bit of circular reasoning: since we know the M-H sampler generates samples distributed according to the stationary distribution $\pi$, it must be the case it generates many samples in the high density regions of the domain and few samples in the low density regions. Since most samples are generated in high density regions, $\pi(x_i)$ is usually large. Thus, $\pi(x_i)$ is large and $\pi(x_j)$ is small, resulting in an acceptance rate $\frac{\pi(x_j)}{\pi(x_i)} << 1$.

These two assumptions are true of most distributions we're likely to be interested in, so this relationship between proposal width and acceptance rate is a useful tool for understanding the behavior of M-H samplers.

-
+1. Thanks! When $\sigma^2$ is large, I am still not sure why $\pi(x_i)$ is usually big while $\pi(x_j)$ usually small? Can your reason that $\pi(x_j)$ is small apply to $\pi(x_i)$ and your reason that $\pi(x_i)$ big apply to $\pi(x_j)$? –  Tim May 7 '12 at 2:46
Another way to think about it is as follows: when $\sigma^2$ is large, most of your proposals ($x_j$) will have low density under the target distribution (for the reasons described above -- is that part okay?). Very rarely you will propose a value with high density under the proposal, and when this happens you will almost certainly accept it. Once there, you continue proposing unlikely values; since you rarely accept one of them, you just "stay" at your current, high-density sample for many iterations. –  Drew May 7 '12 at 3:17
To by-pass this problem, however, what one can do is to propose different variances in a burn-in period for each parameter and aim at a certain acceptance rates which can satisfy your needs (say $0.44$, see Gelman, Roberts & Gilks, 1995 and Gelman, Gilks & Roberts, 1997 to learn more on the issue of selecting a "good" acceptance rate which, of course, will depende on the form of you posterior distribution). Of course, in this case the chain is non-markovian, so you DON'T have to use them for inference: you just use them to adjust the variance.