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?
