Acceptance/Rejection Sampling

Suppose that you want to generate pseudorandom numbers from a random variable with probability distribution , but that other methods (like the method of inverse transforms) do not work well (perhaps because the cumulative distribution function associated with does not have an explicit inverse). Instead, choose a companion random variable with probability density function , making sure that and have the same support (i.e. both vanish and fail to vanish over the same sets of real numbers).

Ideally, the random variable has been chosen in such a way that the cumulative distribution function associated with has an explicit inverse and is easy to simulate using a technique like the method of inverse transforms.

The acceptance-rejection algorithm is then as follows: (1) independently simulate a random number with a uniform distribution over the unit interval and a realization * of the random variable ; and then (2) using a fixed, strictly positive number , accept * as a realization of if , where and are the probability densities of the random variables and , respectively. If is not accepted, it is rejected. This process is continued repeatedly until a target number of realizations of is generated.

Heuristically, the acceptance-rejection method works particularly efficiently when certain conditions are satisfied. First, the target random variable and the companion random variable should have density functions that "look" as similar as possible. In this Demonstration, we use the exponential random variable as a companion random variable for the probability distributions with support on the positive part of the real line (the gamma distribution, chi-square distribution, half-normal distribution, and log-normal distribution). We use the Cauchy distribution as the companion distribution for the probability distributions with support over the whole real line (the normal distribution, the Student t distribution, the Gumbel distribution, and the Laplace distribution).

Second, the strictly positive constant influences the tendency of the algorithm to "accept" instead of "reject". If is particularly large, will be less than with small probability, and the algorithm will throw away many fine proxies for . On the other hand, if is particularly close to zero and is not substantially smaller than , then will probably be accepted. It can be shown that the acceptance-rejection algorithm produces an empirical distribution of pseudorandom numbers that converges the most rapidly to the target distribution if is chosen to be the maximum possible value of over the (common) support of and .

The acceptance-rejection method can be generalized to the Metropolis–Hastings algorithm and is a type of Markov chain Monte Carlo simulation. For further information about the acceptance-rejection algorithm, see [1] or [2].

References

[1] S. M. Ross, Simulation, 4th ed., Boston: Elsevier, 2006.

[2] S. Ghahramani, Fundamentals of Probability, with Stochastic Processes, 3rd ed., New York: Prentice Hall, 2004.