# Rejection-Sampling of Exponential Distribution

Consider the following question.

Consider the generation of random numbers following an exponential distribution with some known mean. Give three reasons why the rejection-acceptance method would not be the preferred approach for generating random numbers for this distribution. What is the preferred approach?

Assume a program is available to generate uniformly distributed random numbers between 0 and 1.

I'm not looking for direct answers to the question, but rather advice on how to go about solving it. I could not find a reason as to why the rejection method is not well suited for the exponential distribution. Thanks

• I am not looking for a direct answer to the question itself. I've been stuck on this problem while studying for an exam, and can't seem to figure it out. I want someone to point me in the right direction. Thanks – Just Aug 12 '14 at 17:58
• Can you say what you have done / understand so far? – gung Aug 12 '14 at 18:29
• It is not in the least obvious that rejection sampling couldn't work for an exponential distribution. (Offhand I can think of a simple one with 69% efficiency.) Why don't you try to implement a rejection sampler? If you succeed with an efficient one, you will have learned more than whoever asked the question :-) while if you do not succeed you will acquire a good appreciation for what the difficulties might be. – whuber Aug 12 '14 at 18:48
• @whuber Yes, rejection method can be used here. And I did read about it achieving around 69% accuracy. But I got the impression that the accuracy can't be increased any further, but I'm not sure how to prove it. I need some help in proving it (if it is the case). – Just Aug 12 '14 at 19:14
• Accuracy isn't the issue so much as speed. Either you're generating exponentially-distributed variables or you're not; if you are, speed is what's left to consider. Can you think of a method that a) isn't a rejection method, and b) requires fewer than 1/0.69 uniform random variates to be generated, on average, for each output exponential variate? – jbowman Aug 12 '14 at 19:39

The exponential distribution is one of the easiest to generate, because you can get its inverse CDF in closed form: Solving $u = F(x) = 1 - \exp\{-x/\theta\}$, you obtain $x = -\theta\log(1-u)$, implying that if $U_1,U_2,\ldots$ are independent uniforms, then $-\theta\log U_1, -\theta\log U_2, \ldots$ are independent exponentials with mean $\theta$. You can generate these without rejection. (Note: I replaced $1-U_j$ with $U_j$ because they both have the same distribution.)