Rao-Blackwellisation of Sampling Schemes

Summary

Casella and Robert (1996) propose a post-simulation improvement to the Accept-Reject and Metropolis algorithms by applying the Rao-Blackwell theorem to integrate out the ancillary uniform random variables that govern acceptance decisions. Rather than discarding rejected candidates, the method computes weights for all simulated draws via an O(n²) recurrence relation, producing an estimator with the same expectation but strictly lower variance. The paper demonstrates 15–60% mean-squared-error (MSE) reductions for Accept-Reject and 40–50% for independent Metropolis, and identifies Rao-Blackwell (RB) importance sampling as an even more powerful alternative that casts doubt on the value of the Metropolis mean as an estimation device.

Key Claims

• Both Accept-Reject and Metropolis estimators depend on ancillary uniform variables $U \sim \text{Unif}[0,1]$. By the law of total variance, conditioning on the full candidate sequence $Y_1,\ldots,Y_n$ and integrating out the $U$'s yields a Rao-Blackwellised estimator with lower variance and identical expectation.
• Accept-Reject RB: weights $p_i = P(Y_i \text{ accepted} | N, Y_1,\ldots,Y_N)$ computed via an $O(n^2)$ recurrence on the order statistics of $w_i = f(Y_i)/Mg(Y_i)$. MSE reduction is 15–20% at acceptance rate 0.9 and up to 60% at rate 0.3. The gap is permanent — it does not close as sample size grows.
• Independent Metropolis RB: weights $\vartheta_i$ = expected number of times $Y_i$ appears in the accepted chain, computed via $\delta_{ij} = \sum_k \delta_{k,j-1} p_{ki}$. Result: ~40–50% MSE reduction vs. the ergodic mean.
• General (random-walk) Metropolis RB: extends to dependent candidates $g(y|Z_{n-1})$ via more complex trajectory-probability recursions; still $O(n^2)$. At acceptance rate 0.33: 7–25% improvement; at 0.75: only 0.4–7%.
• RB importance sampling (Section 5): an importance-sampling (IS) estimator built on the Metropolis chain, with weights Rao-Blackwellised using the same trajectory probabilities, achieves 70–95% MSE reduction over the standard Metropolis estimator — dramatically better than RB Metropolis itself. The authors conclude: "the use of importance sampling in practical MCMC environments should bring an even greater improvement."
• Rao-Blackwellisation is a statistical improvement, not a computational one. A biased estimator stays biased. The uniform variables are ancillary, so conditioning on them is always valid; the only barrier is computational cost (1.15–7× increase depending on algorithm).

Concepts Introduced or Extended

• Metropolis-Hastings Algorithm
• Markov Chain Monte Carlo
• Gibbs Sampler

Entities Mentioned

• George Casella
• Christian P. Robert

Quotes

"No matter how large a sample is simulated, and no matter how good the simple estimators are, dependence on the uniform random variables is a statistical deficiency."

"These results cast some doubt on the value of the Metropolis estimator, since it can be so dramatically improved upon."

My Take

The core contribution is elegant: the uniform random variables in Accept-Reject and Metropolis are genuinely ancillary, so conditioning them out is always strictly better from a decision-theoretic standpoint. The practical limitation is the O(n²) computation, which is cheap for the sample sizes typical in the paper (n ≤ 100) but potentially costly for long Markov chain Monte Carlo (MCMC) chains. The most thought-provoking result is the IS comparison: if IS achieves comparable or better variance reduction than RB Metropolis, and IS requires only a single pass over the weights (O(n)), then the Metropolis estimator looks even less attractive as a pure estimation tool. The paper's conclusion — that IS should be used alongside Metropolis as a "control estimate" — is practically sound but rarely implemented.