Rejection sampling

The rejection sampling is a basic technique used to generate observations from a distri- bution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm". It is a basic unit for the modern (and very popular) sampling method Markov Chain Monte Carlo (MCMC).

Given a density function f(x), the rejection sampling generates data points from this distribution using the following procedure.

(i) Choose a proposal density g(x) which we know how to draw sample from (for

example, g(x) can be the density of a standard normal distribution) as well as a

numberMsup f(x). x g(x)

(ii) Generate a random number Y from g and another random number U from U nif [0, 1].

(iii) If U < f(Y) , we set X = Y. Otherwise go back to the previous step to draw Mg(Y )

another new pair of Y and U.

If we want to generate X1, . . . , Xn from f, we can apply the above procedure multiple

times until we accept n points.

(a) Calculate the probability that a generated Y is accepted.

(b) Show that the points generated using the rejection sampling method follow the distribution f(x).