Generate random variable by accept-reject algorithm

Question

Solve the following problem:

Consider using the Accept-Reject algorithm to generate a N (0, 1) random variable from a double-exponential distribution L(α), with density g(x|α)=(α/2) exp(-α|x|) as a candidate.

a. Show that

f(x)/g(x/α) ≤ √(2/π)α^-1e^α2/2

and that the minimum of this bound (in α) is attained for α = 1.

b. Show that the probability of acceptance is then √π/2e = .76  and deduce that, to produce one normal random variable, this Accept-Reject algorithm requires on average 1/.76 ≈ 1.3 uniform variables.

c. Show that L(α) can be generated by the probability inverse transform, and compare this algorithm with the Box-Muller algorithm of Example in terms of execution time.

Example : If U₁ and U₂ are iid U_[0,1], the variables X₁ and X₂ defined by

X₁ = √-2 log (U₁) cos(2πU₂),      X₂ = √-2 log (U₁) cos(2πU₂)