Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 40 / 5

For a target probability density function $\pi$ and a proposal distribution with density $q(x^{\prime }\mid x)$, the Metropolis–Hastings algorithm starts in the target support and repeats: propose $x^{\prime }\sim q(\cdot \mid x)$, draw an independent uniform $U$, and move to $x^{\prime }$ ifOtherwise retain $x$. A zero reverse-proposal density makes the acceptance zero. Unknown multiplicative constants of $\pi$ cancel. For distinct states,which is symmetric in the states. Together with the probability of holding at the current state, this proves detailed balance and invariance of $\pi$. Successive values form a dependent Markov chain; convergence from arbitrary initial states additionally needs the appropriate irreducibility and aperiodicity, not just this invariant-density identity.

The Gibbs sampler updates a coordinate using its full conditional distribution while keeping the others fixed. For coordinate $i$, write $r=x_{-i}$ and $\pi (x)={\pi }_{-i}(r){\pi }_i(x_i\mid r)$. Its proposal replaces $x_i$ by $x_i^{\prime }\sim {\pi }_i(\cdot \mid r)$. The MH ratio, interpreted on this one-coordinate proposal space, isThus every Gibbs coordinate update is an MH update with acceptance one. A random choice of coordinate gives a mixture of these invariant kernels; a deterministic sweep gives their composition. Both preserve $\pi$. The latter composition need not be reversible, so the special-case statement is about the coordinate kernels, not a claim that every entire systematic sweep is one reversible MH kernel.

At $\sigma =1$, complete the square:For fixed $y$, all factors not involving $x$ enter its conditional normalizing constant. Interchanging the roles of the coordinates givesThese are the full conditional distributions of the standard bivariate normal distribution with correlation $\rho$.

A systematic Gibbs sampler starts at a chosen $(x_0,y_0)$ and, at each sweep, draws independent standard normals $Z_{1,n},Z_{2,n}$ and setsThe second update uses the newly drawn $x_{n+1}$. Both coordinate updates preserve the target by part (a), hence so does the sweep. The Gaussian two-coordinate Gibbs recursion is explicitlyan AR(1) recursion with innovation variance $1-{\rho }^4$. Its stationary variance is one, and its correlation at sweep lag $k$ is ${\rho }^{2k}$, displaying the dependence of the sample.

The printed general-$\sigma$ expression has a separate normalization defect: for $\sigma >0$ its integral is $\sigma$, not one, since the exponent has covariance ${\sigma }^2\left(\begin{array}{cc}1& \rho \\ \rho & 1\end{array}\right)$, whose normalizing denominator is $2\pi {\sigma }^2\sqrt{1-{\rho }^2}$. Retaining that exponent requires ${\sigma }^2$ in the prefactor. The requested $\sigma =1$ target is already normalized, so this defect does not alter the conditional distributions above.

Use the random-walk proposal specified by its centre and covariance: for the current state $z=(x,y)$ draw $Z_1,Z_2$ independently standard normal and setIts properly normalized density of the proposal distribution isIt is symmetric: $q(z^{\prime }\mid z)=q(z\mid z^{\prime })$. This is a centred-at-the-current-state proposal, rather than an unshifted draw from the density notation in the source. The random-walk Metropolis algorithm consequently needs only the target ratio. Put $H(x,y)=x^2+y^2-2\rho xy$. ThenAn independent uniform decides the move; on rejection both coordinates remain at their previous values. A proposal with lower $H$ is always accepted. This construction uses the joint density directly, without needing either conditional distribution. Its continuous positive proposal density supplies communication over the target support, and the holding probability avoids a deterministic periodic transition pattern.

Tune the proposal scale using pilot runs on a grid of candidate ${\sigma }_q$ values. After allowing for initial transients, compare the effective sample size of a Markov chain per unit computation time for representative functions, such as both coordinates and a quadratic function. Equivalently inspect their integrated autocorrelation time, using $\mathrm{ESS}\approx n/(1+2{\sum }_{k\ge 1}\mathrm{Corr}(h(Z_0),h(Z_k)))$. Choose a useful scale and keep it fixed for the production run. Another pilot criterion is the average squared accepted displacement, possibly in coordinates standardized by the target covariance, which balances move size and rejection.

Acceptance alone is not an efficiency criterion. As ${\sigma }_q\downarrow 0$, proposals are almost the current state, so acceptance tends to one while exploration becomes arbitrarily slow. Very large scales propose mostly low-density states and produce long sequences of identical values. The proposal scale and random-walk Metropolis efficiency trade-off requires both movement and acceptance; neither maximizing nor merely reporting the acceptance probability guarantees a useful sample. With strong correlation, an isotropic proposal also struggles with the target's narrow direction; covariance-scaled proposals can improve this geometry beyond tuning one scalar variance.