Random-walk and independent proposals

Section of Markov chains, Gibbs sampling, and Metropolis–Hastings, part of Bayesian statistics

Random-walk and independent proposals

Type Section
Taught in Markov chains, Gibbs sampling, and Metropolis–Hastings
Part Bayesian statistics
Questions using it 17

For a random-walk proposal Y=x+Z with a distribution symmetric about zero,

q(y\mid x)=q(x\mid y),

so Equation (5) in Markov chains, Gibbs sampling, and Metropolis–Hastings reduces to

a(x,y)=\min\!\left\{1,\frac{\pi(y)}{\pi(x)}\right\}.

Every proposed move to higher target density is accepted; a move to a point with two-thirds as much density is accepted with probability 2/3.

For an independent proposal q(y\mid x)=g(y),

a(x,y)=\min\!\left\{ 1,\frac{\pi(y)g(x)}{\pi(x)g(y)} \right\}.

Equivalently, with w(z)=\pi(z)/g(z),

a(x,y)=\min\!\left\{1,\frac{w(y)}{w(x)}\right\}.

The Hastings factor g(x)/g(y) corrects for the fact that g may propose some regions too often and others too rarely. It must not be discarded merely because the proposal is independent of the current state. An independent proposal can jump between separated modes, but it performs poorly if g under-covers a region where \pi is large. A local random walk can represent local shape well but may become trapped in one mode. Proposal scale is therefore a genuine tuning decision, not a cosmetic one.

Gibbs sampling as an always-accepted MH update

Main article: Gibbs sampling as an always-accepted MH update

The connection with Gibbs sampling can be made exact. Suppose the current state is {\boldsymbol{x}}=(x_1,x_2)^{\mathsf T} and we update only the first coordinate by proposing

{\boldsymbol{y}}=(y_1,x_2)^{\mathsf T}, \qquad y_1\sim\pi(\,\cdot\mid x_2).

Then

q({\boldsymbol{y}}\mid{\boldsymbol{x}})=\pi(y_1\mid x_2), \qquad q({\boldsymbol{x}}\mid{\boldsymbol{y}})=\pi(x_1\mid x_2).

Using joint equals conditional times marginal, the Hastings ratio is \begin{align*} r({\boldsymbol{x}},{\boldsymbol{y}}) &=\frac{\pi(y_1,x_2)\pi(x_1\mid x_2)} {\pi(x_1,x_2)\pi(y_1\mid x_2)}\\ &=\frac{\pi(y_1\mid x_2)\pi(x_2) \pi(x_1\mid x_2)} {\pi(x_1\mid x_2)\pi(x_2) \pi(y_1\mid x_2)}\\ &=1. \end{align*} Every Gibbs coordinate proposal is therefore accepted. This does not imply that every Gibbs sampler moves efficiently. In the bivariate-normal example, as |\rho|\to1 the conditional standard deviation \sqrt{1-\rho^2} tends to zero: acceptance remains one while successive states move only a very short distance.

Proposal design is an art because local and global exploration pull in different directions. Tiny random-walk steps are accepted but travel slowly; huge steps travel far but are mostly rejected. An independent proposal can jump between modes, yet it wastes effort if it puts mass where the target has almost none. The Hastings correction guarantees the right equilibrium under the required conditions; it does not guarantee an efficient journey there.

Figure 1: Three random-walk Metropolis chains with the same \operatorname{N}(0,1) target and different proposal standard deviations s_q. The tiny proposal is accepted almost every time but advances slowly; the huge proposal repeats its current value through long runs of rejections. A moderate acceptance rate is useful only because it accompanies larger moves and much weaker autocorrelation. The displayed acceptance rate is a.

Pilot adaptation and a fixed proposal

Main article: Pilot adaptation and a fixed proposal

Adaptive proposals are a practical response to this tuning problem. A conservative version has two stages:

  1. run a pilot calculation to learn a plausible centre, scale, or covariance for the proposal;

  2. discard the pilot output, fix the learned proposal, restart the chain, and use only the second-stage draws for inference.

Conditional on the now-fixed proposal, the ordinary Metropolis–Hastings invariance argument applies to the retained chain.

Some adaptive schemes retain the history and continue changing the proposal during the run. Then the transition rule depends on time and on more than the current state, so the fixed-kernel proof given above no longer establishes the result. Such methods can be valid, but they require additional conditions and theory. Validity does not follow merely from the fact that the proposal seems to improve.

Used in

See also

Hastings correction · Metropolis algorithm · Metropolis–Hastings update · Markov chain · Stationarity and detailed balance · Detailed balance implies stationarity · Systematic-scan Gibbs sampler · Warm-up is not a convergence proof

Glossary and index