Q5. Random-walk Metropolis-Hastings

Topic: Markov chains, Gibbs sampling, and Metropolis–Hastings · more questions on this topic
‹ Q4 Q9 ›

Let the target density be \pi(x)\propto x^2e^{-x}, \qquad x>0. We wish to sample from \pi using a random-walk Metropolis-Hastings algorithm with proposal Y\mid X^{(t-1)}=x\sim\mathcal{N}(x,\sigma^2), where \sigma>0 is fixed.

(a) [3 marks] Show that the Metropolis-Hastings acceptance probability is \alpha(x,y) = \begin{cases} \displaystyle \min\left\{ \left(\frac{y}{x}\right)^2 e^{-(y-x)},1 \right\}, & y>0,\\[1.2em] 0, & y\leq0. \end{cases} Explain why the proposal-density terms cancel.

(b) [2 marks] Calculate the acceptance probability for each proposed move. You may leave your answers in exact exponential form.

1. Current state x=2, proposed state y=3.

2. Current state x=3, proposed state y=2.

(c) [3 marks] Write pseudocode for a random-walk Metropolis-Hastings sampler generating T observations from the target distribution. Begin from a valid initial value x^{(0)}>0.

(d) [1 mark] Explain why the unknown normalising constant of \pi(x) is not required.

(e) [2 marks] Are the sampled values X^{(1)},X^{(2)},\ldots,X^{(T)} independent? Briefly explain.

(f) [2 marks] Explain what is likely to happen if:

1. \sigma is extremely small;

2. \sigma is extremely large.

Worked answer (click to show)

Definitions. Write q(y\mid x) for the density of a proposal y from current state x, and \alpha(x,y) for its acceptance probability. The target kernel is x^2e^{-x} on x>0 and zero elsewhere. N(x,\sigma^2) uses variance \sigma^2, held fixed and positive throughout the run; start with x^{(0)}>0.

As a recognition check, \pi(x)\propto x^{3-1}e^{-1\cdot x}, \qquad x>0, is the kernel of a \operatorname{Gamma}(3,1) distribution under the shape-rate convention. The exercise nevertheless asks us to construct a Metropolis-Hastings sampler for this target.

(a) Acceptance probability

For a proposal density q(y\mid x), the Metropolis-Hastings acceptance probability is \alpha(x,y) =\min\left\{ \frac{\pi(y)q(x\mid y)}{\pi(x)q(y\mid x)},1 \right\}. The normal random-walk proposal is symmetric because q(y\mid x) =\frac{1}{\sqrt{2\pi\sigma^2}} \exp\left[-\frac{(y-x)^2}{2\sigma^2}\right] =q(x\mid y). The proposal-density terms therefore cancel. If y>0, the target-density ratio is \frac{\pi(y)}{\pi(x)} =\frac{y^2e^{-y}}{x^2e^{-x}} =\left(\frac{y}{x}\right)^2e^{-(y-x)}. If y\leq0, then y is outside the support of the target and the proposal must be rejected. Hence \boxed{ \alpha(x,y) = \begin{cases} \displaystyle \min\left\{ \left(\frac{y}{x}\right)^2e^{-(y-x)},1 \right\}, & y>0,\\[1.2em] 0, & y\leq0. \end{cases} }

(b) Acceptance probabilities for the two moves

1. For x=2 and y=3, \alpha(2,3) =\min\left\{\left(\frac32\right)^2e^{-1},1\right\} =\boxed{\frac{9}{4e}\approx0.828}, since 9/(4e)<1. Thus the move is accepted with probability about 82.8\%.

2. For x=3 and y=2, \alpha(3,2) =\min\left\{\left(\frac23\right)^2e,1\right\} =\min\left\{\frac{4e}{9},1\right\} =\boxed{1}, since 4e/9>1. This move goes to a point of higher target density and is always accepted.

This illustrates the basic Metropolis rule: moves to higher target density are accepted automatically, while moves to lower target density may still be accepted with positive probability.

(c) Random-walk Metropolis-Hastings pseudocode

Choose an initial state x^{(0)}>0. For t=1,2,\ldots,T:

1. Generate a proposal Y\sim\mathcal{N}\bigl(x^{(t-1)},\sigma^2\bigr).

2. Calculate a= \begin{cases} \displaystyle \min\left\{ \left(\frac{Y}{x^{(t-1)}}\right)^2 e^{-(Y-x^{(t-1)})},1 \right\}, & Y>0,\\[1.2em] 0, & Y\leq0. \end{cases}

3. Independently generate U\sim\operatorname{Unif}(0,1).

4. Set X^{(t)}= \begin{cases} Y, & U\leq a,\\ X^{(t-1)}, & U>a. \end{cases}

5. Store X^{(t)}.

A rejection does not mean that nothing is recorded: the chain stores the current value again, so X^{(t)}=X^{(t-1)}. After a suitable burn-in, the stored values are approximately distributed according to \pi.

(d) Unknown normalising constant

If \pi(x)=\widetilde{\pi}(x)/C, then \frac{\pi(y)}{\pi(x)} =\frac{\widetilde{\pi}(y)/C}{\widetilde{\pi}(x)/C} =\frac{\widetilde{\pi}(y)}{\widetilde{\pi}(x)}. Thus the same unknown constant appears in the numerator and denominator and cancels from the acceptance ratio. Metropolis-Hastings therefore requires the target only up to proportionality, which is especially useful for posterior distributions with an intractable marginal likelihood.

(e) Independence of the sampled values

No. Each proposal is generated from the previous state, and a rejected move gives X^{(t)}=X^{(t-1)}. The samples therefore form a Markov chain and are generally serially dependent, even after the chain has reached equilibrium. At equilibrium, each X^{(t)} has marginal distribution \pi, but having the correct marginal distribution does not imply independence.

(f) Effect of the proposal scale

1. If \sigma is extremely small, proposals stay close to the current state and are usually accepted. However, the chain moves slowly through the target distribution, producing high autocorrelation and poor mixing.

2. If \sigma is extremely large, many proposals fall outside the support or in regions of very low target density. The acceptance rate becomes small, so the chain often repeats its current value and again mixes poorly.