acceptance-rejection method


The acceptance-rejection method is an algorithm for generating random samples from an arbitrary probability distribution, given as ingredients random samples from a related distributionPlanetmathPlanetmathPlanetmath and the uniform distributionMathworldPlanetmath.

The acceptance-rejection method’s chief advantage over the inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath CDF method of generating random numbersMathworldPlanetmath is that it requires neither the cumulative distribution functionMathworldPlanetmath nor its inverse to be computed. So in many cases it can run faster.

Set-up

  • Let X be a random variableMathworldPlanetmath with some other probability distribution that we know how to draw samples from — that is, generate on a computer.

  • Let U be a random variable uniformly distributed on the interval [0,1].

  • Let Y be the random variable that we want to be able to generate. Assume Y has a probability distribution that is absolutely continuousMathworldPlanetmath to the probability distribution for X, with density ρ.

  • Further assume that the density ρ is bounded above by a constant c. So ρ(x)c for all x in the range of X; and necessarily c1.

In most applications, both X and Y will be continuous random variables with densities g and f respectively. In that case we have ρ(x)=f(x)/g(x), and we require f(x)cg(x).

(If g(x)=0, then set ρ(x)=0. Note that we cannot have f(x)>0 and g(x)=0 simultaneously on a set of positive measureMathworldPlanetmath, since Y has a distribution absolutely continuous with respect to that of X.)

The random variables X and Y can be multi-variate.

Algorithm

The procedure to generate a value for Y is:

  1. 1.

    Generate a value for X.

  2. 2.

    Generate a value for U.

  3. 3.

    If Uρ(X)/c, then set Y=X (“accept”).

  4. 4.

    Otherwise, go back to step 1 (“reject”), repeating until we obtain a value of Y in step 3.

Intuitive explanation

When we generate X and U as prescribed in the algorithm, we are in fact picking the point (X,cU) in the rectangular box below. And the test Uρ(X)/c determines that point lies below the graph of ρ. It seems plausible that if we keep only the points that fall under the graph of the density ρ, and ignore the points above, then the distribution of the abscissa should have density ρ.

Figure 1: Acceptance and rejection regions for a density

The acceptance-rejection method works more efficiently as the distribution of X and Y become similar enough — that is, ρ(x) and its upper bound c are close to one. This makes the rejection region smaller, and so the algorithm is likely to go through fewer repetitions discarding the rejects.

Justification

We now prove that the acceptance-rejection method works.

Let Xn, for n, be independentPlanetmathPlanetmath random variables representing the samples, all with law G. Let Un, for n, be independent random variables, with the uniform distribution over [0,1], and independent from Xn.

Let

N=inf{n:Unρ(Xn)c}

be the number of draws (for Xn and Un) taken by the algorithm before acceptance. Then we must show that Y=XN has the correct distribution: it should be distributed with density ρ(x) with respect to dG(x).

We have, by independence,

(Nn)=(k=1n-1{Uk>ρ(Xk)c})=(U1>ρ(X1)c)n-1.

We can calculate the last probability explicitly. Letting H be the law of Z1=ρ(X1)/c, and using the independence of U1 from Z1, we find:

(U1>Z1) =01z1𝑑u𝑑H(z)=01(1-z)𝑑H(z)
=1-𝔼Z1
=1-ρ(x)c𝑑G(x)=1-1c.

From the equation N=n=1𝟏{Nn}, we take expectations of both sides, evaluating the resulting geometric series:

𝔼N=n=1(Nn)=n=1(1-1c)n-1=c.

Thus N< almost surely, and the algorithm terminates, on average, after drawing c samples.

Finally, for all measurable setsMathworldPlanetmath B, we have

(YB) =n=1({YB}{N=n})
=n=1(XnB,Unρ(Xn)c,Nn)
=n=1(Nn)(XnB,Unρ(Xn)c)
=n=1(Nn)B0ρ(x)/cdudG(x)
=(Bρ(x)cdG(x))n=1(Nn)
=Bρ(x)𝑑G(x),

as is to be shown.

References

  • 1 James E. Gentle. Random Number Generation and Monte Carlo Methods, second edition. Springer, 2003.
Title acceptance-rejection method
Canonical name AcceptancerejectionMethod
Date of creation 2013-03-22 17:19:20
Last modified on 2013-03-22 17:19:20
Owner stevecheng (10074)
Last modified by stevecheng (10074)
Numerical id 13
Author stevecheng (10074)
Entry type Algorithm
Classification msc 65C10
Synonym acceptance-rejection
Synonym accept-reject algorithm
Related topic MonteCarloSimulation