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

$\endgroup$
  • $\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 Aug 12 '14 at 17:58
  • 1
    $\begingroup$ Can you say what you have done / understand so far? $\endgroup$ – gung Aug 12 '14 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 Aug 12 '14 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 Aug 12 '14 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 Aug 12 '14 at 19:39
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.

$\endgroup$
  • $\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 Aug 12 '14 at 20:46
  • $\begingroup$ Oops, sorry. I need to remember look at the tags. $\endgroup$ – rvl Aug 12 '14 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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