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 π(x)=f(x)/K, where x 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)ch(x) for all x. To obtain a draw from π:

  1. Draw a candidate z from h and u from U(0,1), the uniform distribution on the interval (0,1).
  2. If uf(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=sup xf(x)h(x).