Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 33 / 2

For the Metropolis–Hastings algorithm, start at a point $x$ with positive target probability density function. Draw $Y$ from a proposal probability density function $q(y\mid x)$, generate an independent uniform distribution value $U$, and set the next state to $Y$ ifOtherwise retain $x$, including that repeated state in the sample. Where a proposed forward move is possible but its reverse probability density function vanishes, its acceptance probability is zero. Unknown normalizing constants in $\pi$ cancel.

For distinct states, the accepted probability flow iswhich is symmetric in $x,y$. This detailed balance identity, together with the holding probability, proves that $\pi$ is invariant. Under appropriate irreducibility and aperiodicity conditions the chain converges to $\pi$; successive states are generally dependent.

The Gibbs sampler updates coordinates from their full conditional distributions. In a systematic sweep, draw successivelyEach update preserves the target joint law: integrating the old coordinate against its conditional probability density function and replacing it by an independent draw from that same conditional leaves the joint probability density function unchanged. The composition of the coordinate updates therefore also preserves $\pi$. A Gibbs sampler coordinate move can be regarded as a Metropolis–Hastings algorithm move with acceptance probability one. Systematic sweeps preserve stationarity but need not themselves be reversible. Initialization away from stationarity requires convergence before treating the draws as approximately target-distributed, and dependence must be accounted for in Monte Carlo method error estimates.

Assume ${\sigma }_1,{\sigma }_2>0$ and $|\rho |<1$, as required for the displayed nonsingular probability density function. Put $z_j=(x_j-{\mu }_j)/{\sigma }_j$. Its quadratic exponent isHolding $x_2$ fixed and normalizing the term depending on $x_1$ givesThe analogous completion of the square gives

Using independent draws ${\eta }_{1,r},{\eta }_{2,r}$ from the standard normal distribution, a sweep isUse the newly drawn first coordinate in the second update. Recording the pairs after each sweep gives the dependent sample.

The Gaussian Gibbs sweep autocorrelation makes the dependence explicit. In standardized coordinates, substitution yieldsThe new noise has variance $1-{\rho }^4$, so the stationary variance is one and the lag-$h$ sweep autocorrelation is ${\rho }^{2h}$. Thus the sampler converges geometrically for $|\rho |<1$, but becomes slow near perfect correlation. When $\rho =0$, complete sweeps yield independent pairs. The singular cases $|\rho |=1$ do not have the stipulated two-dimensional probability density function.

Here the proposal is $Y=x+\eta$ with $\eta \sim N_2(0,I_2)$. Its probability density function depends only on $\Vert y-x{\Vert }^2$, so $q(y\mid x)=q(x\mid y)$. The determinant and normalizing constant of the target also cancel. With $Q$ as in the preceding entry,Equivalently, writing $u_j=(y_j-{\mu }_j)/{\sigma }_j$ and $z_j=(x_j-{\mu }_j)/{\sigma }_j$,One can also compute the exponent without subtracting two large quadratic forms:Generate two independent standard normal distribution proposal increments, compute this log ratio, and accept when $\log U\le \min (0,\log (\pi (Y)/\pi (x)))$. Retain the previous pair on rejection. Detailed balance gives the correct invariant distribution, and the everywhere-positive Gaussian proposal makes this random-walk Metropolis algorithm chain irreducible; a rejection probability provides a holding step. The resulting target-distributed pairs are dependent, with proposal scale and target anisotropy controlling how quickly they mix.