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].

[1] S. M. Ross,

*Simulation*, 4th ed., Boston: Elsevier, 2006.

[2] S. Ghahramani,

*Fundamentals of Probability, with Stochastic Processe*s, 3rd ed., New York: Prentice Hall, 2004.