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

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.