8
$\begingroup$

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 probability $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 Gaussian 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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Xi'an May 7 '12 at 9:19
  • $\begingroup$ @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? $\endgroup$ – Tim May 7 '12 at 12:55
  • $\begingroup$ 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. $\endgroup$ – Xi'an May 7 '12 at 19:51
10
$\begingroup$

In order to get this, and to simplify the matters, I always think first in just one parameter with uniform (long-range) a-priori distribution, so that in this case, the MAP estimate of the parameter is the same as the MLE. However, assume that your likelihood function is complicated enough to have several local maxima.

What MCMC does in this example in 1-D is to explore the posterior curve until it finds values of maximum probability. If the variance is too short, you'll most surely get stuck on local maxima, because you'll be always sampling values near it: the MCMC algorithm will "think" it is stuck on the target distribution. However, if the variance is too large, once you get stuck on one local maximum, you'll more-or-less reject values until you find other regions of maximum probability. If you happen to propose the value at the MAP (or a similar region of local maximum probability which is larger than the others), with a large variance you'll end up rejecting almost every other value: the difference between this region and the others will be too large.

Of course, all of the above will affect the convergence rate and not the convergence "per-se" of your chains. Recall that whatever the variance, as long as the probability of selecting the value of this global maximum region is positive, your chain will converge.

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.

$\endgroup$
  • $\begingroup$ +1 Thanks! (1) Why "if the variance is too large, once you get stuck on one local maximum, you'll more-or-less reject values until you find other regions of maximum probability"? (2) "If you happen to propose the value at the MAP (or a similar region of local maximum probability which is larger than the others), with a large variance you'll end up rejecting almost every other value", do you mean the proposed point happening to be at MAP is very likely to be rejected at large variance case? Since it is global maximium, isn't its acceptance probability always 1 regardless of current state? $\endgroup$ – Tim May 7 '12 at 3:08
  • $\begingroup$ @Tim: (1) I was thinking in the case when the initial state is random. If this is the case, then you'll be jumping from maxima to maxima, until you find a region of local maximum probability which is larger than the average. (2) If you happen to propose a value close to the MAP, you'll most likely jump to that state. Once you are there, with a large variance, you'll almost surely reject every other value, because you'll propose values far outside this maximum probability region. $\endgroup$ – Néstor May 7 '12 at 3:32
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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)$? $\endgroup$ – Tim May 7 '12 at 2:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Drew May 7 '12 at 3:17

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.