# Is Metropolis-Hastings ever more efficient than rejection sampling in 2 dimensions?

I know that Metropolis-Hastings is an MCMC (Markov Chain Monte Carlo) method that is very useful in higher dimensions. The advantages it has over something like simple rejection sampling are that there are fewer points that are rejected, especially in higher dimension systems, and thus it is more efficient (sometimes even to the scale of actually being able to solve a problem in our lifetime vs. not) than rejection sampling.

In the lower dimensions -- say 1 or 2 dimensions -- is it ever worth using Metropolis-Hastings or any other MCMC method over just rejection sampling?

I guess rejection sampling at these lower dimensions would almost always be more efficient than MCMC methods especially because (1) in order to sample N points Metropolis Hastings also has to go through a burn-in period where many points will be thrown out, and (2) it sucks at multimodal systems. In addition, at these lower dimensions, Metropolis-Hastings would never reach situations where rejection sampling is SO bad that it is less efficient than Metropolis=Hastings.

• In some cases, rejection sampling isn't an option, e.g., for a Gamma distribution with a shape parameter $< 1$, where the maximum value the PDF takes on is $\infty$... so yes, if we include these distributions in the question domain! Jul 3, 2023 at 23:19

First, one need define a precise notion of efficiency. For instance, if the goal is to produce an iid sample from a target distribution with density $$\pi$$, then rejection sampling (assuming it is available at a tolerable cost) is more efficient than MCMC simply because the latter can (almost) never guarantee that one realisation of the Markov chain is exactly distributed from $$\pi$$, nor that a series of realisations of the Markov chain are independent.

Second, if the goal is to produce numerical approximations to integrals depending on $$\pi$$, like$$\int h(x)\pi(x)\text dx$$the comparison of simulation methods usually consider their respective biases and variances. As far as bias is concerned, MCMC is at a disadvantage unless (i) stationarity is guaranteed [e.g., by using a rejection sampler or a perfect sampling scheme to initialise the Markov chain] or (ii) the MCMC approximation is debiased. Concerning variance, MCMC chains most usually induce positive dependence between consecutive simulations and hence generally increase variance when compared with iid sampling. This positive correlation between consecutive simulations explains why MCMC having "less points that are rejected" is not a valuable universal argument in favour of Metropolis-Hastings. Intuitively, a Metropolis-Hastings algorithm that almost never reject takes forever to explore the density range, unless one considers the unrealistic special case when the proposal is $$\pi$$ itself. The comparison of a MCMC method with an iid sampler goes through the measure of effective sample size (ESS), plus a rescaling accounting for the time required to produce one output.

Third, the comparison need account for the design of both algorithms. An off-the-shelf MCMC algorithm like random walk Metropolis-Hastings or HMC (Stan) requires little human intervention. A rejection sampler need picking a dominating density $$\bar\pi$$ and deriving an upper bound$$\overline M\ge\sup_x \pi(x)/\bar\pi(x)$$which can little be automated.

As for the arguments in the question

(1) in order to sample N number of points Metropolis Hastings also has to go through a burn-in period where many points will be thrown out

Burn-in is often a minor issue, especially if the Markov chain can be started from a $$\pi$$ likely value, plus the ergodic theorem does not require burn-in.

(2) it sucks at multimodal systems

Multimodality is also a challenge for rejection sampling since the dominating density has to encompass all the modes.

at these lower dimensions, Metropolis Hastings would never reach situations where rejection sampling is SO bad that it is less efficient than Metropolis Hastings

This statement cannot be quantified, since the choices of the Markov proposal in the Metropolis-Hastings algorithm and of the dominating measure in rejection sampling will determine the relative efficiencies of both and can get unboundedly bad.