Q. 10.10 - A First Course in Probability

Question

In Example 2c we simulated the absolute value of a unit normal by using the rejection procedure on exponential random variables with rate 1. This raises the question of whether we could obtain a more efficient algorithm by using a different exponential density—that is, we could use the density g(x) = λe−λx. Show that the mean number of iterations needed in the rejection scheme is minimized when λ = 1.

Step-by-Step Solution

Answer

Write$\frac{f\left(x\right)}{g\left(x\right)}$and find$c$ Using the differentiation, and prove $c$ is minimal if any only if $\lambda =1$which is explained below.

Step 1: Given Information

We have given the exponential density

$g\left(x\right)=\lambda e^{-\lambda x}$.

Step 2: Simplify

Using the rejection method

$f\left(x\right)=\frac{2}{\sqrt{2\mathrm{\pi }}}{e}^{-\frac{x^2}{2}}$

and

$g\left(x\right)=\lambda e^{-\lambda x}$

which implies

$$\begin{gathered} \frac{f\left(x\right)}{g\left(x\right)}=\frac{1}{\lambda }\sqrt{\frac{3}{\mathrm{\pi }}}exp\left(-\frac{x^2-2\lambda x}{2}\right) \\ =\frac{1}{\lambda }\sqrt{\frac{2}{\mathrm{\pi }}}exp\left(-\frac{x^2-2\lambda z+{\lambda }^2}{2}+\frac{{\lambda }^2}{2}\right) \\ =\frac{e^{{\displaystyle \frac{{\lambda }^2}{2}}}}{\lambda }\sqrt{\frac{2}{\mathrm{\pi }}}exp\left(-\frac{{(x-\lambda )}^2}{2}\right) \\ \le {\frac{e}{\lambda }}^{\frac{{\lambda }^2}{2}}\sqrt{\frac{2}{\mathrm{\pi }}} \end{gathered}$$

So, we can take

$c=\frac{e^{{\displaystyle \frac{{\lambda }^2}{2}}}}{\lambda }\sqrt{\frac{2}{\mathrm{\pi }}}$

Now, proving$c$ has minimal value when $\lambda =1.$ By, differentiation, we have

$\frac{dc}{d\lambda }=\sqrt{\frac{2}{\mathrm{\pi }}}\left(\frac{e^{{\displaystyle \frac{{\lambda }^2}{2}}}({\lambda }^2-1)}{{\lambda }^2}\right)$

So, we notice that $\frac{dc}{d\lambda }=0$ if and only $\lambda =\pm 1.$ Hence, we have proved that $c$ is minimal for$\lambda =1$, so it takes the minimum time(on average) to obtain the accepting value.