Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 26J (Principles of Statistics)

In Bayesian inference, a finite parameter space has posterior probabilities $\pi (\theta )=w(\theta )/Z$, with $w(\theta )$ the product of the prior probability and likelihood and $Z={\sum }_{\theta }w(\theta )$ the evidence. Although each weight may be easy to evaluate, summing a large parameter space can be impractical. The Metropolis–Hastings algorithm constructs a Markov chain with posterior stationary distribution, allowing posterior expectations, probabilities and credible regions to be estimated from its trajectory. Its acceptance ratios cancel $Z$, so direct enumeration of the normalizing constant is unnecessary. Posterior sampling alone does not automatically provide the evidence for comparing models.

Restrict to the positive-weight support. From a state $\theta$, propose ${\theta }^{\prime }$ according to $q(\theta ,{\theta }^{\prime })$ and accept with probabilityOtherwise stay at $\theta$. For distinct states, the accepted transition kernel satisfiesThus detailed balance holds, and summing over $\theta$ proves stationarity. Irreducibility of the accepted kernel makes this stationary distribution unique. Proposal irreducibility by itself is insufficient if proposed edges have zero reverse probability and are always rejected.

For convergence of the distribution from an arbitrary start, also require aperiodicity, which can always be supplied by making the chain lazy. In a finite irreducible aperiodic chain, some power $P^m$ has all entries positive. Its rows then share a fixed positive probability component, so repeated application contracts total variation distance geometrically. This proves that the chain's distribution approaches $\pi$.

The stronger fact needed for averages isOne can justify this directly by returns to a chosen state. Successive excursions are independent identically distributed cycles by the Strong Markov property. In a finite irreducible chain, return times have finite mean: from every state there is a path of uniformly bounded length and uniformly positive probability to the chosen state, giving a geometric tail bound. Apply the strong law of large numbers to cycle lengths and accumulated rewards. Their ratio converges; the mean visits per cycle, normalized by the mean cycle length, form a stationary distribution and hence equal $\pi$. The unfinished final cycle is negligible. This proves the displayed average law, even when the chain is periodic. Under these conditions, Metropolis–Hastings delivers the required posterior expectations.

The proposal must connect the whole positive posterior support by moves with nonzero reverse probability. Use the full Metropolis–Hastings acceptance probability for asymmetric proposals; dropping the reverse proposal factor generally targets the wrong distribution. Compute likelihoods and acceptance ratios on a logarithmic scale to avoid overflow and underflow, and handle zero weights explicitly. A lazy step prevents periodicity when distributional convergence is needed.

Finite-chain convergence does not guarantee a useful run length: separated modes and narrow bottlenecks can make mixing extremely slow. Tune proposals to explore efficiently, inspect several starting points and chains, and assess autocorrelation and Monte Carlo uncertainty rather than treating correlated draws as independent observations. Discarding an initial segment can reduce initialization effects, but diagnostics do not prove that every posterior mode has been visited. Thinning is not required for correctness and often throws away useful information. The model and prior must themselves be specified correctly; an exact sampler from an incorrect posterior cannot repair the model.