Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 47 / 5 / a

For the Metropolis–Hastings algorithm, start at a state $\theta$ with positive target density, propose ${\theta }^{\prime }$ from $q({\theta }^{\prime }\mid \theta )$, and generate an independent uniform draw. Accept the proposal with probabilityOn rejection retain $\theta$, including repeated states in the chain; removing repeats would generally change its stationary law. The accepted-flow density satisfieswhich is symmetric in its two states. This proves detailed balance and hence invariance of the target distribution, including the holding probabilities on the diagonal. Unknown common normalization constants cancel in the ratio. Invariance alone does not establish convergence from arbitrary initial states. Choosing proposals that yield a positive Harris recurrent Markov chain with aperiodicity supplies the usual convergence guarantee, and the resulting sample is dependent. Use burn-in and account for autocorrelation when assessing Monte Carlo precision.

A random-walk update proposes ${\theta }^{\prime }=\theta +\eta$, with an increment distribution independent of the current state. If its density is symmetric, $q({\theta }^{\prime }\mid \theta )=q(\theta \mid {\theta }^{\prime })$, reducing the Metropolis–Hastings acceptance probability to $\min \{1,\pi ({\theta }^{\prime })/\pi (\theta )\}$. For nonsymmetric increments the proposal-density ratio must remain.

Such updates need little global knowledge of the target and adapt naturally to its local scale. Their limitation is a tuning tradeoff: very small increments accept often but move slowly, while very large increments are often rejected. They can also have difficulty moving between distant modes. Covariance-scaled increments help with anisotropic targets, but the chain still explores through local steps.

An independence sampler proposes from a fixed density $g({\theta }^{\prime })$, independent of the current state. Its acceptance probability isIf $g$ is close to the target, proposals can make large efficient moves and cross separated modes; $g=\pi$ gives acceptance one and independent samples. On the other hand, a good global approximation is required. A proposal with tails too light can leave the chain trapped at states having very large importance weight $\pi /g$, since most outgoing proposals then have tiny acceptance probabilities.

For perspective, if the normalized target satisfies $\pi \le Mg$, the accepted transition density is at least $\pi ({\theta }^{\prime })/M$, because both entries in $\min \{g({\theta }^{\prime }),\pi ({\theta }^{\prime })/w(\theta )\}$ have that lower bound, where $w=\pi /g\le M$. This yields a uniform refresh component. Thus a well-designed independence proposal can mix rapidly, whereas a poor global proposal can be much worse than a locally tuned random walk. The tradeoff concerns effective samples per computation, not acceptance rate alone.