What is the difference between Metropolis-Hastings, Gibbs, Importance, and Rejection sampling?

Question

I have been trying to learn MCMC methods and have come across Metropolis-Hastings, Gibbs, Importance, and Rejection sampling. While some of these differences are obvious, i.e., how Gibbs is a special case of Metropolis-Hastings when we have the full conditionals, the others are less obvious, like when we want to use MH within a Gibbs sampler, etc. Does anyone have a simple way to see the bulk of the differences between each of these?

Answer 1

As detailed in our book with George Casella, Monte Carlo statistical methods, these methods are used to produce samples from a given distribution, with density $f$ say, either to get an idea about this distribution, or to solve an integration or optimisation problem related with $f$. For instance, to find the value of $$\int_{\mathcal{X}} h(x) f(x)\text{d}x\qquad h(\mathcal{X})\subset \mathbb{R}$$ or the mode of the distribution of $h(X)$ when $X\sim f(x)$ or a quantile of this distribution.

To compare the Monte Carlo and Markov chain Monte Carlo methods you mention on relevant criteria requires one to set the background of the problem and the goals of the simulation experiment, since the pros and cons of each will vary from case to case.

Here are a few generic remarks that most certainly do not cover the complexity of the issue:

1. Accept-reject methods are intended to provide an i.i.d. sample from $f$. To achieve this, one designs an algorithm that takes as input a random number of uniform variates $u_1,u_2,\ldots$, and returns a value $x$ that is a realisation from $f$. The pros are that there is no approximation in the method: the outcome is truly an i.i.d. sample from $f$. The cons are many: (i) designing the algorithm by finding an envelope of $f$ that can be generated may be very costly in human time; (ii) the algorithm may be inefficient in computing time, i.e., requires many uniforms to produce a single $x$; (iii) those performances are decreasing with the dimension of $X$. In short, such methods cannot be used for simulating one or a few simulations from $f$ unless they are already available in a computer language like R.
2. Markov chain Monte Carlo (MCMC) methods are extensions of i.i.d. simulations methods when i.i.d. simulation is too costly. They produce a sequence of simulations $(x_t)_t$ which limiting distribution is the distribution $f$. The pros are that (i) less information about $f$ is needed to implement the method; (ii) $f$ may be only known up to a normalising constant or even as an integral$$f(x)\propto\int_{\mathcal{Z}} \tilde{f}(x,z)\text{d}z$$ and still be associated with an MCMC method; (iii) there exist generic MCMC algorithms to produce simulations $(x_t)_t$ that require very little calibration; (iv) dimension is less of an issue as large dimension targets can be broken into conditionals of smaller dimension (as in Gibbs sampling). The cons are that (i) the simulations $(x_t)_t$ are correlated, hence less informative than i.i.d. simulations; (ii) the validation of the method is only asymptotic, hence there is an approximation in considering $x_t$ for a fixed $t$ as a realisation of $f$; (iii) convergence to $f$ (in $t$) may be so slow that for all practical purposes the algorithm does not converge; (iv) the universal validation of the method means there is an infinite number of potential implementations, with an equally infinite range of efficiencies.
3. Importance sampling methods are originally designed for integral approximations, namely generating from the wrong target $g(x)$ and compensating by an importance weight $$f(x)/g(x)\,.$$ The resulting sample is thus weighted, which makes the comparison with the above awkward. However, importance sampling can be turned into importance sampling resampling by using an additional resampling step based on the weights. The pros of importance sampling resampling are that (i) generation from an importance target $g$ can be cheap and recycled for different targets $f$; (ii) the "right" choice of $g$ can lead to huge improvements compared with regular or MCMC sampling; (iii) importance sampling is more amenable to numerical integration improvement, like for instance quasi-Monte Carlo integration; (iv) it can be turn into adaptive versions like population Monte Carlo and sequential Monte Carlo. The cons are that (i) resampling induces inefficiency (which can be partly corrected by reducing the noise as in systematic resampling or qMC); (ii) the "wrong" choice of $g$ can lead to huge losses in efficiency and even to infinite variance; (iii) importance has trouble facing large dimensions and its efficiency diminishes quickly with the dimension; (iv) the method may be as myopic as local MCMC methods in missing important regions of the support of $f$; (v) resampling induces a bias due to the division by the sum of the weights.

In conclusion, a warning that there is no such thing as an optimal simulation method. Even in a specific setting like approximating an integral $$\mathcal{I}=\int_{\mathcal{X}} h(x) f(x)\text{d}x\,,$$ costs of designing and running different methods intrude as to make a global comparison very delicate, if at all possible, while, from a formal point of view, they can never beat the zero variance answer of returning the constant "estimate" $$\hat{\mathcal{I}}=\int_{\mathcal{X}} h(x) f(x)\text{d}x$$ For instance, simulating from $f$ is very rarely if ever the best option. This does not mean that methods cannot be compared, but that there always is a possibility for an improvement, which comes with additional costs.