# Optimal distribution for Acceptance Rejection Sampling

For some project I have been sampling from the Gamma distribution. I have been using the exponential distribution intensively. One method I have employed is the Acceptance rejection sampling, particularly for the pdf given $$f(x) = 8{e^{ - 4x}}x \cdot {1_{\left\{ {x \ge 0} \right\}}}$$ Initially I just used $${g_2}(x) = 2{e^{ - 2x}} \cdot {1_{\left\{ {x \ge 0} \right\}}}$$ as the distribution I sampled from for it seemed a good fit. Having looked at just $${g_1}(x) = {e^{ - x}} \cdot {1_{\left\{ {x \ge 0} \right\}}}$$ I think it more closely envelopes the target distribution. I am now thinking what would be the optimal exponential distribution, $${g_\lambda }(x) = \lambda {e^{ - \lambda x}} \cdot {1_{\left\{ {x \ge 0} \right\}}}$$ to be used and if one even exists. Is there a criterion to work that out, short of using calculus of variation approaches?

The question is dependent on the definition of optimality. Mathematically, the optimal choice is the target $$f$$ itself as maths do not account for the cost of producing a simulation. If the cost of computing is taken into account, only functions requesting the same number of basic operations can be compared. For instance, all exponential families can be compared. In which case, the optimal choice is the one leading to the highest acceptance probability. This means, if $$\frac{f(x)}{g_\lambda(x)}\le M_\lambda$$finding $$\lambda$$ that minimises $$M_\lambda$$. And the resolution of $$x^\star(\lambda)=\arg\max_x \frac{f(x)}{g_\lambda(x)} = \arg\max_x \lambda^{-1} x e^{(\lambda-4)x}$$that leads to $$x^\star(\lambda)=(4-\lambda)^{-1}$$ makes the constant $$\lambda^{-1}(4-\lambda)^{-1}e^{-1}$$rather straightforward to minimise! The optimum is thus for $$\lambda^\star=2$$, with an acceptance probability of $$\frac{1}{M^\star}=8\frac{1}{2}\frac{1}{2}e^{-1}=2e^{-1}\approx0.73$$