1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This is a special case of the question answered very nicely at stats.stackexchange.com/a/41284/919. $\endgroup$ – whuber Nov 3 '19 at 22:36
  • $\begingroup$ 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) $\endgroup$ – mdawgig Nov 4 '19 at 1:37
  • $\begingroup$ 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) $\endgroup$ – mdawgig Nov 4 '19 at 1:37
  • $\begingroup$ 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. $\endgroup$ – mdawgig Nov 4 '19 at 1:37
3
$\begingroup$

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<f_Z(X)$ 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}$.

enter image description here

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<f_Z(X_i)/cf_X(X_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)$$

Note: I do not understand the part of the question that mentions "The solution" as I cannot tell where this solution is coming from.

$\endgroup$

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.