I'm working on some practice test problems, and one of them says to design a rejection sampling algorithm to produce draws from a unit exponential using draws from a Gamma(2,1).
I don't understand how this is possible, because I am under the impression that the "envelope function" g(x) needs to be scalable in such a manner that for some constant $M$, $Mg(x)\geq f(x)\; \forall x$.
I can't see any way to do this, as the Gamma(2,1) is going to have little mass around 0, while the exponential function has most of its mass around 0. What kind of transformation do I need to do to the Gamma function to allow it to function as an envelope?
Using R, I tried flipping it to make it an inverse gamma, but that won't adequately capture the probability mass close to 0 and a K-S test confirmed that the points I generated did not arise from a unit exponential.
edit: I will include my code in which I tried to use an inverse-gamma(2,1) as an envelope:
x <- c()
for(i in 1:100000)
{
g <- runif(1, 0, 1)
h <- rigamma(1, 2, 1)
M <- densigamma(h, 2, 1)
crit <- dexp(h, 1)/M
if(g < crit)
x[i] = h
}
x = numeric(100000)This will be much faster. – csgillespie May 5 '11 at 21:11