acceptancerejection method
The acceptancerejection 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 acceptancerejection 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.
Setup

•
Let $X$ be a random variable^{} 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 continuous^{} to the probability distribution for $X$, with density $\rho $.

•
Further assume that the density $\rho $ is bounded above by a constant $c$. So $\rho (x)\le c$ for all $x$ in the range of $X$; and necessarily $c\ge 1$.
In most applications, both $X$ and $Y$ will be continuous random variables with densities $g$ and $f$ respectively. In that case we have $\rho (x)=f(x)/g(x)$, and we require $f(x)\le cg(x)$.
(If $g(x)=0$, then set $\rho (x)=0$. Note that we cannot have $f(x)>0$ and $g(x)=0$ simultaneously on a set of positive measure^{}, since $Y$ has a distribution absolutely continuous with respect to that of $X$.)
The random variables $X$ and $Y$ can be multivariate.
Algorithm
The procedure to generate a value for $Y$ is:

1.
Generate a value for $X$.

2.
Generate a value for $U$.

3.
If $U\le \rho (X)/c$, then set $Y=X$ (“accept”).

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\le \rho (X)/c$ determines that point lies below the graph of $\rho $. It seems plausible that if we keep only the points that fall under the graph of the density $\rho $, and ignore the points above, then the distribution of the abscissa should have density $\rho $.
The acceptancerejection method works more efficiently as the distribution of $X$ and $Y$ become similar enough — that is, $\rho (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 acceptancerejection method works.
Let ${X}_{n}$, for $n\in \mathbb{N}$, be independent^{} random variables representing the samples, all with law $G$. Let ${U}_{n}$, for $n\in \mathbb{N}$, be independent random variables, with the uniform distribution over $[0,1]$, and independent from ${X}_{n}$.
Let
$$N=inf\{n\in \mathbb{N}:{U}_{n}\le \frac{\rho ({X}_{n})}{c}\}$$ 
be the number of draws (for ${X}_{n}$ and ${U}_{n}$) taken by the algorithm before acceptance. Then we must show that $Y={X}_{N}$ has the correct distribution: it should be distributed with density $\rho (x)$ with respect to $dG(x)$.
We have, by independence,
$$\mathbb{P}(N\ge n)=\mathbb{P}\left(\bigcap _{k=1}^{n1}\{{U}_{k}>\frac{\rho ({X}_{k})}{c}\}\right)=\mathbb{P}{({U}_{1}>\frac{\rho ({X}_{1})}{c})}^{n1}.$$ 
We can calculate the last probability explicitly. Letting $H$ be the law of ${Z}_{1}=\rho ({X}_{1})/c$, and using the independence of ${U}_{1}$ from ${Z}_{1}$, we find:
$\mathbb{P}({U}_{1}>{Z}_{1})$  $={\displaystyle {\int}_{0}^{1}}{\displaystyle {\int}_{z}^{1}}\mathit{d}u\mathit{d}H(z)={\displaystyle {\int}_{0}^{1}}(1z)\mathit{d}H(z)$  
$=1\mathbb{E}{Z}_{1}$  
$=1{\displaystyle \int \frac{\rho (x)}{c}\mathit{d}G(x)}=1{\displaystyle \frac{1}{c}}.$ 
From the equation $N={\sum}_{n=1}^{\mathrm{\infty}}\mathrm{\U0001d7cf}\{N\ge n\}$, we take expectations of both sides, evaluating the resulting geometric series:
$$\mathbb{E}N=\sum _{n=1}^{\mathrm{\infty}}\mathbb{P}(N\ge n)=\sum _{n=1}^{\mathrm{\infty}}{(1\frac{1}{c})}^{n1}=c.$$ 
Thus $$ almost surely, and the algorithm terminates, on average, after drawing $c$ samples.
Finally, for all measurable sets^{} $B$, we have
$\mathbb{P}(Y\in B)$  $={\displaystyle \sum _{n=1}^{\mathrm{\infty}}}\mathbb{P}(\{Y\in B\}\cap \{N=n\})$  
$={\displaystyle \sum _{n=1}^{\mathrm{\infty}}}\mathbb{P}({X}_{n}\in B,{U}_{n}\le {\displaystyle \frac{\rho ({X}_{n})}{c}},N\ge n)$  
$={\displaystyle \sum _{n=1}^{\mathrm{\infty}}}\mathbb{P}(N\ge n)\mathbb{P}({X}_{n}\in B,{U}_{n}\le {\displaystyle \frac{\rho ({X}_{n})}{c}})$  
$={\displaystyle \sum _{n=1}^{\mathrm{\infty}}}\mathbb{P}(N\ge n){\displaystyle {\int}_{B}}{\displaystyle {\int}_{0}^{\rho (x)/c}}dudG(x)$  
$=\left({\displaystyle {\int}_{B}}{\displaystyle \frac{\rho (x)}{c}}dG(x)\right){\displaystyle \sum _{n=1}^{\mathrm{\infty}}}\mathbb{P}(N\ge n)$  
$={\displaystyle {\int}_{B}}\rho (x)\mathit{d}G(x),$ 
as is to be shown.
References
 1 James E. Gentle. Random Number Generation and Monte Carlo Methods, second edition. Springer, 2003.
Title  acceptancerejection method 

Canonical name  AcceptancerejectionMethod 
Date of creation  20130322 17:19:20 
Last modified on  20130322 17:19:20 
Owner  stevecheng (10074) 
Last modified by  stevecheng (10074) 
Numerical id  13 
Author  stevecheng (10074) 
Entry type  Algorithm 
Classification  msc 65C10 
Synonym  acceptancerejection 
Synonym  acceptreject algorithm 
Related topic  MonteCarloSimulation 