2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – Just
    Commented Aug 12, 2014 at 17:58
  • 1
    $\begingroup$ Can you say what you have done / understand so far? $\endgroup$
    – gung - Reinstate Monica
    Commented Aug 12, 2014 at 18:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber ♦
    Commented Aug 12, 2014 at 18:48
  • $\begingroup$ @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). $\endgroup$
    – Just
    Commented Aug 12, 2014 at 19:14
  • 2
    $\begingroup$ 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? $\endgroup$
    – jbowman
    Commented Aug 12, 2014 at 19:39

1 Answer 1

Reset to default
3
$\begingroup$

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.)

That said, I think there are rejection methods that would have higher than 69% acceptance rate. All you need is a distribution with a fatter tail than the exponential, so that some multiple of its density dominates the exponential density. Generate a random variate from the fat-tailed distribution, and accept it with probability equal to the ratio of the exponential and the scaled fat-tailed density.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For any distribution there will be rejection procedures that come as close to 100% as you like--in theory. The issue is whether they are fast and simple. That comes down to efficiently generating realizations from a distribution having a similarly shaped PDF. (The 69% rate originates from the binary nature of the machines we use.) BTW, please take a look at our policy concerning self-study questions. $\endgroup$
    – whuber ♦
    Commented Aug 12, 2014 at 20:46
  • $\begingroup$ Oops, sorry. I need to remember look at the tags. $\endgroup$
    – Russ Lenth
    Commented Aug 12, 2014 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.