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 {ℝ}^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$:

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