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.
The objective is to sample from a target density , where , is the unnormalized target density, and the potentially unknown normalizing constant. Suppose that we can sample from another density and that there exists a constant such that for all . To obtain a draw from :
- Draw a candidate from and from , the uniform distribution on the interval .
- If , return .
- Otherwise, return to 1.
The expected number of iterations required to accept a draw is . To ensure efficiency, the optimal choice of is
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.