Here is a method called accept-reject sampling for drawing observa- tions from a distribution.

(a) Suppose that f is some probability density function. Let g be any other density and suppose that f (x) ≤Mg(x) for all x, where M is a known constant. Consider the following algorithm: (step 1): Draw X ∼ g and U ∼ Unif(0, 1); (step 2): If U ≤ f (X)/(Mg(X)) set Y = X, otherwise go back to step

1. (Keep repeating until you ?nally get an observation.) Show that the distribution of Y is f.

(b) Let f be a standard Normal density and let g(x) = 1/(1 + x2) be the Cauchy density. Apply the method in (a) to draw 1,000 observations from the Normal distribution. Draw a histogram of the sample to verify that the sample appears to be Normal.