# The Accept-Reject Method

The **Accept-Reject method** is a classical sampling method which
allows one to sample from a distribution which is difficult or
impossible to simulate by an inverse transformation. Instead, draws
are taken from an *instrumental density* and accepted with a carefully
chosen probability. The resulting draw is a draw from the target
density.

## Accept-Reject Algorithm

The objective is to sample from a target density $\pi (x)=f(x)/K$, where $x\in {\mathbb{R}}^{d}$, $f(x)$ is the unnormalized target density, and $K$ the potentially unknown normalizing constant. Suppose that we can sample from another density $h(x)$ and that there exists a constant $c$ such that $f(x)\le ch(x)$ for all $x$. To obtain a draw from $\pi $:

- Draw a candidate $z$ from $h$ and $u$ from $U(0,1)$, the uniform distribution on the interval $(0,1)$.
- If $u\le \frac{f(z)}{ch(z)}$, return $z$.
- Otherwise, return to 1.

The expected number of iterations required to accept a draw is ${c}^{-1}$. To ensure efficiency, the optimal choice of $c$ is $$c=\underset{x}{\mathrm{sup}}\frac{f(x)}{h(x)}.$$

## References

Chib, S. and E. Greenberg (1995). Understanding the Metropolis Hastings Algorithm.

*American Statistical Journal*49, 327–335.Robert, C.P., and G. Casella (2004).

*Monte Carlo Statistical Methods*, Second Edition. New York: Springer.