When to favor rejection sampling over importance sampling

I asked a question about importance vs rejection sampling: Importance sampling vs acceptance-rejection and why one would use rejection sampling when importance sampling should produce a lower variance because it doesn't outright drop any samples. A question linked was this one: What is the difference between Metropolis-Hastings, Gibbs, Importance, and Rejection sampling? which asks about a much broader range of simulation techniques and the only distinction between importance and rejection sampling I could discern (and was also pointed out) from the answer was that rejection sampling produces an i.i.d sample while importance sampling does not.

This is good to know, but I still am not able to use this information on my original question which was - what would be an actual scenario where rejection sampling would be better applicable than importance sampling. In almost all instances of simulation, I feel we end up finding some kind of average anyway. In fact, this statement was made by the professor who taught a course on simulation I took (except, he didn't say "almost").

1 Answer

It is incorrect to see simulation as reduced to Monte Carlo integration. There are many other usages of computer simulation. In particular, dynamical systems as in statistical mechanics that are driven by differential equations are rarely allowing for an analytical solution and require simulation to describe their equilibrium distribution.

A very specific instance when importance sampling cannot be used is the case of the pseudo-marginal Metropolis–Hastings algorithm: this is a Metropolis algorithm where the target density $$\pi(\theta)$$ is replaced with an unbiased estimator (of said density), $$\hat\pi(\theta,\xi)$$, with $$\xi\sim \varpi(\xi|\theta)$$. Ẁhile resorting to an accept-reject algorithm to produce a simulation from $$\varpi(\xi|\theta)$$ is acceptable, using instead a self-normalised importance sampling estimate of $$\pi(\theta)$$ is not valid because it breaks the unbiasedness requirement. (A simple experiment shows that the resulting Markov chain does not converge to the intended target $$\pi(\theta)$$.)

Reminder: the (usual) variance improvement brought by unbiased importance sampling over accept-reject simulation only applies when the variance exists.

Note also that, given an accept-reject output, producing an iid sample $$x_1,\ldots,x_n$$ from an overall sample (containing rejected values) $$y_1,\ldots,y_N$$, and auxiliary uniforms, $$u_1,\ldots,u_N$$, a variance improvement over the sample average $$\frac{1}{n}\sum_{i=1}^n h(x_i)=\frac{1}{n}\sum_{j=1}^N h(y_j)\mathbb I_{u_j<\varrho(y_j)}$$ [where $$\varrho(y_j)$$ is the acceptance ratio] can be found by integrating out the $$u_j$$'s, conditional on the $$y_j$$'s and $$n$$ being accepted. The domination follows from a Rao-Blackwell argument.