# Monte Carlo sampling: Rejection method vs. Transformation method

I just covered the rejection method with students in an optimization course. Naturally, I mentioned the benefit of the rejection method when you receive e.g. empirical data from a research team with a statement like "nothing is known about probability distributions and their parameters, and all we can provide are the data." In this case, I suggested evaluating the effect of the number of bins, bin width and lower and upper bin walls, incrementing bin counts based on the data, etc. Once you know the integer valued bin counts, get their sum, normalize the bin counts, and then run cubic splines on the bin proportions in order to obtain a smoothed pdf function. Then acquire a quantile or not for each pair of the two random uniform numbers (r1,r2) during the rejection method.

The question is, when we cover the transformation method next, which is merely getting the cdf of bin counts, then turning cdf on its head and inputting the cdf function values in range [0,1] as the x-inputs to cubic splines, and the quantile values (lower bin wall values) as the y-values for cubic splines. Then, to obtain a random quantile, simply input a random uniform as the x-value into the fitted cubic spline function, and directly obtain the respective quantile.

The advantage of the inverse cdf method with cubic splines over the rejection method is clear, since you never have to repeat a random draw of r1 & r2 if r2>pdf(x)/pdf_max. With the inverse cdf approach and cubic splines you get a quantile for each single random draw of r1 after it's entered into the fitted cubic spline. Thus, I would expect students to ask "why did we learn the rejection method, which is less efficient than the transformation method?"

Question is: Are there cases where certain properties of the pdf require rejection over transformation? (I haven't read the Numerical Recipes sections on these, but did look at the figures and equations. I also have Newman & Barkema's MC Methods in Stat Physics (which doesn't cover the transformation method at all?).

The inverse method requires the computation of the inverse cumulative distribution at each step. For certain pdf's this could take longer (or much longer) than the acceptance/rejection method. Consider a small lattice with 100 sites of which 50 are occupied. In this problem the die has $$\frac{100!}{50! 50!} \sim 10^{29}$$ configurations that are equally probable. Clearly the fastest simulation is to pick a configuration at random and always accept. This amounts to the Metropolis implementation of the acceptance/rejection criterion. The inverse method here is clearly dead on its tracks.

For the inverse transformation sampling one needs to obtain the CDF and then invert it, which is a mathematically non-trivial procedure - it is not possible with an arbitrary probability density.

Rejection Sampling is much easier to implement, and it does not require any special treatment of the of the probability density - it does not even have to be an analytical function.

Then, pedagogically, rejection sampling is a convenient precursor for discussing more advance Monte Carlo methods, notably Markov Chain Monte Carlo (where rejection/acceptance of proposals is a centerpiece.)