The acceptance-rejection method is an algorithm for generating random samples from an arbitrary probability distribution, given as ingredients random samples from a related distribution and the uniform distribution.
The acceptance-rejection method’s chief advantage over the inverse CDF method of generating random numbers is that it requires neither the cumulative distribution function nor its inverse to be computed. So in many cases it can run faster.
Let be a random variable with some other probability distribution that we know how to draw samples from — that is, generate on a computer.
Let be a random variable uniformly distributed on the interval .
Further assume that the density is bounded above by a constant . So for all in the range of ; and necessarily .
In most applications, both and will be continuous random variables with densities and respectively. In that case we have , and we require .
(If , then set . Note that we cannot have and simultaneously on a set of positive measure, since has a distribution absolutely continuous with respect to that of .)
The random variables and can be multi-variate.
The procedure to generate a value for is:
Generate a value for .
Generate a value for .
If , then set (“accept”).
Otherwise, go back to step 1 (“reject”), repeating until we obtain a value of in step 3.
When we generate and as prescribed in the algorithm, we are in fact picking the point in the rectangular box below. And the test 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 .
We now prove that the acceptance-rejection method works.
Let , for , be independent random variables representing the samples, all with law . Let , for , be independent random variables, with the uniform distribution over , and independent from .
be the number of draws (for and ) taken by the algorithm before acceptance. Then we must show that has the correct distribution: it should be distributed with density with respect to .
We have, by independence,
We can calculate the last probability explicitly. Letting be the law of , and using the independence of from , we find:
Thus almost surely, and the algorithm terminates, on average, after drawing samples.
Finally, for all measurable sets , we have
as is to be shown.
- 1 James E. Gentle. Random Number Generation and Monte Carlo Methods, second edition. Springer, 2003.
|Date of creation||2013-03-22 17:19:20|
|Last modified on||2013-03-22 17:19:20|
|Last modified by||stevecheng (10074)|