# acceptance-rejection method

## Set-up

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)\leq 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 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\leq\rho(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\leq\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 acceptance-rejection 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 acceptance-rejection 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\left\{n\in\mathbb{N}\colon U_{n}\leq\frac{\rho(X_{n})}{c}\right\}$

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}\bigl{(}N\geq n\bigr{)}=\mathbb{P}\left(\bigcap_{k=1}^{n-1}\Bigl{\{}% U_{k}>\frac{\rho(X_{k})}{c}\Bigr{\}}\right)=\mathbb{P}\left(U_{1}>\frac{\rho(X% _{1})}{c}\right)^{n-1}\,.$

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:

 $\displaystyle\mathbb{P}\left(U_{1}>Z_{1}\right)$ $\displaystyle=\int_{0}^{1}\int_{z}^{1}\,du\,dH(z)=\int_{0}^{1}(1-z)\,dH(z)$ $\displaystyle=1-\mathbb{E}Z_{1}$ $\displaystyle=1-\int\frac{\rho(x)}{c}dG(x)=1-\frac{1}{c}\,.$

From the equation $N=\sum_{n=1}^{\infty}\mathbf{1}\{N\geq n\}$, we take expectations of both sides, evaluating the resulting geometric series:

 $\mathbb{E}N=\sum_{n=1}^{\infty}\mathbb{P}(N\geq n)=\sum_{n=1}^{\infty}\left(1-% \frac{1}{c}\right)^{n-1}=c\,.$

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

Finally, for all measurable sets  $B$, we have

 $\displaystyle\mathbb{P}\bigl{(}Y\in B\bigr{)}$ $\displaystyle=\sum_{n=1}^{\infty}\mathbb{P}\bigl{(}\{Y\in B\}\cap\{N=n\}\bigr{)}$ $\displaystyle=\sum_{n=1}^{\infty}\mathbb{P}\left(X_{n}\in B,\,U_{n}\leq\frac{% \rho(X_{n})}{c},\,N\geq n\right)$ $\displaystyle=\sum_{n=1}^{\infty}\mathbb{P}(N\geq n)\,\mathbb{P}\left(X_{n}\in B% ,\,U_{n}\leq\frac{\rho(X_{n})}{c}\right)$ $\displaystyle=\sum_{n=1}^{\infty}\mathbb{P}(N\geq n)\,\int_{B}\int_{0}^{\rho(x% )/c}\,du\,dG(x)$ $\displaystyle=\left(\int_{B}\frac{\rho(x)}{c}\,dG(x)\right)\,\sum_{n=1}^{% \infty}\mathbb{P}(N\geq n)$ $\displaystyle=\int_{B}\rho(x)\,dG(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 AcceptancerejectionMethod 2013-03-22 17:19:20 2013-03-22 17:19:20 stevecheng (10074) stevecheng (10074) 13 stevecheng (10074) Algorithm msc 65C10 acceptance-rejection accept-reject algorithm MonteCarloSimulation