# 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 \left(x\right)=f\left(x\right)/K$, where $x\in {ℝ}^{d}$, $f\left(x\right)$ is the unnormalized target density, and $K$ the potentially unknown normalizing constant. Suppose that we can sample from another density $h\left(x\right)$ and that there exists a constant $c$ such that $f\left(x\right)\le ch\left(x\right)$ for all $x$. To obtain a draw from $\pi$:

1. Draw a candidate $z$ from $h$ and $u$ from $U\left(0,1\right)$, the uniform distribution on the interval $\left(0,1\right)$.
2. If $u\le \frac{f\left(z\right)}{ch\left(z\right)}$, return $z$.
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\left(x\right)}{h\left(x\right)}.$