Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 208 / 6

Let $\tilde{\pi }$ be a nonnegative target kernel and $q(y\mid x)$ a proposal distribution. At state $x$, propose $Y\sim q(\cdot \mid x)$, draw an independent uniform $U$, and move to $Y$ ifOtherwise keep $x$. This is the Metropolis–Hastings algorithm. Start on the positive target support, with the usual zero-ratio conventions. The unknown normalizing constant cancels.

An unnormalized kernel is sufficient, provided $0<\int \tilde{\pi }<\infty$. A genuinely improper target with infinite integral is not a probability density and cannot supply a stationary target probability distribution. The acceptance formula can still be written formally, but cannot be said to generate samples from that nonexistent probability law.

Because rejected proposals leave the state unchanged, the Markov kernel includes an atom:Detailed balance with a probability measure $\pi$ means the measure identityWhere both sides have ordinary densities, this reads $\pi (x)K(x,y)=\pi (y)K(y,x)$. The measure formulation also includes the rejection atom. Integrating it shows that $\pi$ is invariant.

For the off-diagonal moves, the Metropolis–Hastings acceptance probability givesThis expression is unchanged by interchanging $x$ and $y$. The rejected-move measure $\pi (dx)r(x){\delta }_x(dy)$ is supported on the diagonal and is also symmetric. Therefore the whole transition measure satisfieswhich proves detailed balance, including the atom that an off-diagonal density alone would omit. Consequently the Metropolis–Hastings algorithm kernel preserves the normalized target measure.

For coordinate $i$, keep the other coordinates fixed and propose $y_i$ from the full conditional $\pi (\cdot \mid x_{-i})$. This is a Metropolis–Hastings algorithm proposal on that coordinate fibre, with deterministic equality $y_{-i}=x_{-i}$. Its acceptance ratio isThus the coordinate update has acceptance probability one and is exactly a single-coordinate Gibbs sampler update.

A systematic sweep through coordinates $1,\dots ,p$ is the composition of these kernels. Its joint transition density isThe already updated coordinates are new values, and the not-yet-updated coordinates are old values. Each coordinate kernel preserves $\pi$, so their composition also preserves it. Systematic Gibbs sampling need not be reversible: each individual coordinate kernel is reversible, but their ordered composition need not be reversible; invariance is the property needed here. A random-scan mixture of the coordinate kernels is reversible.

Use the ergodic theorem for a positive Harris recurrent Markov chain: for an invariant distribution $\pi$ and an integrable function $h$, the time average converges almost surely to $\int hd\pi$ under the usual ergodicity conditions. This is the relevant theorem for correlated Metropolis–Hastings algorithm output, rather than the strong law of large numbers. Here $h(x)=x_1$ is integrable. Indeed, puttingwe have $V(x)\ge (x_1-4{)}^2+(x_2-4{)}^2-32$, which bounds the unnormalized density by a constant times an integrable Gaussian density and also gives finite first moments.

For a proposal scale $s>0$, initialize $X_0$ anywhere in ${\mathbb{R}}^2$. At each step draw independent random variables $Z_1,Z_2$ with the standard normal distribution and an independent uniform $U$, propose $Y=X_t+s(Z_1,Z_2)$, and accept whenOtherwise set $X_{t+1}=X_t$. The normal proposal is symmetric, so its density cancels; the target normalizing constant $c$ also cancels. Include every state in the average, including repeated states after rejection. The ergodic theorem for a positive Harris recurrent Markov chain then givesA fixed discarded initial segment does not change this limit.

Small proposal variance gives high acceptance but tiny moves and strong serial dependence. Large variance gives more ambitious moves, but many proposals enter very low-density regions and are rejected, creating long runs at one state. An intermediate scale should be assessed by exploration and effective sample size of a Markov chain, not acceptance rate alone.

This density has two modes, at $(2+\sqrt{3},2-\sqrt{3})$ and their interchange. To see this, stationary points satisfy $x_1(1+x_2^2)=x_2(1+x_1^2)=4$, implying either $x_1=x_2$ or $x_1{x}_2=1$. The unequal solutions have $x_1+x_2=4$ and are local minima of $V$; the equal solution is a saddle. Mode switching is therefore a material part of proposal-scale selection: a chain confined to one mode can have high acceptance and a misleading finite-run estimate.