# Sampling from Gamma Distribution using the Rejection Method

I'm having some issues working through this practice problem. I have worked through the first portion of it, and I have the solution, but I don't understand how/why the solution does two things at the end.

# Problem:

Use the rejection method to sample from the gamma density $$\Gamma(\lambda, t)$$ where $$t (\geq 1)$$ may not be assumed integral. [Hint: You might want to start with an exponential random variable with parameter $$\frac{1}{t}$$.]

# What I've done

Let $$Z\sim \Gamma(1, t)$$. This can be done without loss of generality because, for such a Z, $$\frac{Z}{\lambda}\sim \Gamma(\lambda, t)$$.

Let $$V\sim Uniform(0,1)$$. Using the hint, for some $$y\in (0,1)$$,

\begin{align*} F(x) &= 1-e^{\frac{-x}{t}}\\ y &= 1-e^{\frac{-x}{t}}\\ x &= F^{-1}(y) = -t ln(1-y)\\ X &= -t~ln(1-V)\\ X &= -t~ln(V) \end{align*}

(Since if $$1-V\sim Uniform(0,1)$$, then $$V\sim Uniform(0,1)$$.)

Now, we need to find some $$c$$ such that

\begin{align*} f_Z(x) \leq c f_X(x) \end{align*}

where $$f_Z(x) = \frac{1}{\Gamma(t)}x^{t-1}e^{-x}$$ and $$f_X(x)= \frac{1}{t} e^{\frac{-x}{t}}$$.

Thus, we need to find a $$c$$ that satisfies:

\begin{align*} \frac{f_Z(x)}{f_X(x)} &\leq c\\ \frac{\frac{1}{\Gamma(t)}x^{t-1}e^{-x}}{\frac{1}{t} e^{\frac{-x}{t}}} &\leq c\\ \frac{t e^{x(1/(t-1))}x^{t-1}}{\Gamma(t)} &\leq c \end{align*}

By taking the derivative w.r.t. X, I verified that, for $$t\geq 1$$ and $$x>0$$, the LHS is maximized by $$x=t$$ (I'll omit this work, but I found that the derivative had a root at $$x=-t^2+2t-1$$, so over the ranges of $$t$$ and $$x$$, $$t>x$$, thus the LHS is strictly smaller than its value when $$x=t$$).

Thus, the smallest value of $$c$$ such that $$LHS\leq RHS$$ is:

\begin{align*} c &= \frac{1}{\Gamma(t)}t^{t} e^{-(t-1)} \end{align*}

# What I don't understand

The solution uses the following two things to continue the problem that I don't understand.

## (1)

"Conditional on the event $$A$$:

\begin{align*} U &\leq \frac{X^{t-1}e^{-t}}{\Gamma(t)}t~e^{\frac{-X}{t}} \end{align*}

where $$U\sim Uniform(0,1)$$, X has the required gamma distribution."

I don't understand where this definition of $$A$$ comes from.

I can see that $$\frac{X^{t-1}e^{-t}}{\Gamma(t)}$$ is almost $$f_Z(x)$$, except that $$e^{-x}$$ has been replaced by $$e^{-t}$$ and the rest is almost $$f_X(x)$$, except $$\frac{1}{t}$$ has been replaced with $$t$$.

But, even if that were the case, $$A$$ would be showing that $$U\leq$$ the joint density of the two component functions (and, again, I know that this is not the case, but it is the closest explanation I can come up with), not the $$\frac{f_Z(x)}{c~f_X(x)}$$ that I believe I need to continue the problem. I cannot manipulate $$\frac{f_Z(x)}{c~f_X(x)}$$ to create this $$A$$.

I understand that the next step likely involves the fact that $$F_Z(z;1, t)$$ will take the form $$\frac{\gamma(t, z)}{\Gamma(t)}$$, and $$\gamma(t, z) = \int_0^z x^{t-1}e^{-x} dx$$. I just don't know what to do with this information, given that I don't know where this $$A$$ came from or how to use it.

## (2)

"We note that $$A = \{log(U)\leq(n-1)(log(X/n)-(X/n)+1) \}$$."

Where did this come from and why is it worth noting?

• This is a special case of the question answered very nicely at stats.stackexchange.com/a/41284/919.
– whuber
Nov 3, 2019 at 22:36
• That helps my intuition somewhat, but I'm not sure it really answers my question. I feel confident that I have already identified the relevant envelope function, at least insofar as it satisfies $f_Z(x) \leq c f_X(x)$, which is how I currently understand envelope function working in this context. If that understanding is in error, I would appreciate some intuition as to why finding $c$ is necessary but not sufficient to define event $A$ in this context. (cont'd) Nov 4, 2019 at 1:37
• I want to understand why that particular value of $A$ was chosen in the solution I have, given that it does not align with any way that I can manipulate the RHS of $\mathbb{P}(U\leq \frac{f_Z(x)}{c~f_X(x)})$. Upon further thought, I feel confident that my goal is to create an ultimate ratio of integrals such that I have: $\frac{\frac{1}{\Gamma(t)}\frac{1}{c} \int_0^z x^{t-1}e^{-x} dx}{\frac{1}{c}}$ (I have omitted the integral of the denominator because it integrates to 1.) (cont'd) Nov 4, 2019 at 1:37
• This will give me $\frac{\frac{\gamma(t, z)}{\Gamma(t)} \frac{1}{c}}{\frac{1}{c}} = F_Z(z)$ with mean number of attempts $c$ before a sample of $n=1$ is obtained. I just feel like I am missing one crucial step that gets me from my definition of $c$ to the answer's definition of $A$, and if your link provides that answer, I'm missing some other piece of information that connects the two. Nov 4, 2019 at 1:37

The rejection method can be explained either by an envelope argument, namely that pairs $$(X,U)$$ that are generated uniformly on the set $$\mathfrak S_{cf_X}=\{(x,u);\ 0\le u\le c f_X(x)\}$$ [called the subgraph of $$cf_X$$] are such that
1. $$X\sim f_X(x)$$ (we call this result the fundamental lemma of simulation in our book);
2. if $$U then $$X\sim f_Z(x)$$
This can be seen on the picture below where the hollow circles are $$(X,U)$$'s that are generated uniformly over a square that contains the graph of the target $$f_Z$$ (a Gamma truncated to (0,1) in this illustration) and the filled circles are those that fall below $$f_Z$$. They are indeed uniformly distributed over $$\mathfrak S_{f_Z}$$. It can also be explained by a stopping rule reasoning: if one runs a sequence of iid simulations from $$f_X$$, $$X_1,X_2,\ldots$$ and an associated auxiliary sequence of uniforms $$U_1,U_2,\ldots$$ until $$U_i happening for the (random) index value $$N$$, then $$X_N \sim f_Z(x)$$ since the density of $$X_N$$ is proportional to$$f_X(x)\times\mathbb P(U\le f_Z(X)/cf_X(X)\mid X=x) \propto f_Z(x)$$