= Solution
The proposal's <normalization of a probability distribution> is
$$
\boxed{Z_q=\int_{\mathbb R}e^{-|x|}\,dx=2,\qquad q(x)=\tfrac12e^{-|x|}.}
$$
This is the <Laplace distribution> with location zero and scale one. For example, generate its magnitude from the <exponential distribution> with rate one and give it an <independent> fair sign. The target is the <standard normal distribution>, with $Z_p=\sqrt{2\pi}$.
To obtain the tight envelope, let $t=|x|$. By <completing the square>,
$$
\frac{\widetilde p(x)}{\widetilde q(x)}
=e^{-t^2/2+t}=e^{1/2}e^{-(t-1)^2/2}\leq e^{1/2}.
$$
Equality occurs at $x=\pm1$, so $\boxed{M_*=\sqrt e}$ is the smallest valid envelope constant. It maximizes the acceptance <probability> for this fixed proposal. The supplied lower bound must be clipped at zero to satisfy the algorithm's nonnegativity requirement:
$$
\boxed{h(x)=\max\{0,1-x^2/2\}.}
$$
This is valid because $e^{-s}\geq1-s$ for $s\geq0$, while $\widetilde p$ is everywhere positive. Its <support> is $[-\sqrt2,\sqrt2]$.
Here is the fully specified <squeeze rejection sampling> procedure. Draw $Y$ with <probability density function> $q(y)=e^{-|y|}/2$, independently draw $U\sim\operatorname{Unif}(0,1)$, and compute $H=\max(0,1-Y^2/2)$ and $B=\sqrt e\,e^{-|Y|}$. If $U\leq H/B$, return $Y$ immediately. Otherwise evaluate $P=e^{-Y^2/2}$, independently draw $V\sim\operatorname{Unif}(0,1)$, and return $Y$ if $V\leq(P-H)/(B-H)$. On rejection restart with fresh draws. In this example $B>H$ everywhere, so the residual denominator is positive.
Avoiding a target evaluation means accepting at the first test. Its unconditional <probability> for one proposal is
$$
\begin{aligned}
\mathbb P(\text{no target evaluation})
&=\int_{\mathbb R}q(y)\frac{h(y)}{M\widetilde q(y)}\,dy\\
&=\frac1{2\sqrt e}\int_{-\sqrt2}^{\sqrt2}(1-y^2/2)\,dy\\
&=\boxed{\frac{2\sqrt2}{3\sqrt e}\approx0.571843.}
\end{aligned}
$$
For comparison, the overall acceptance <probability> is $\sqrt{2\pi}/(2\sqrt e)=\sqrt{\pi/(2e)}\approx0.760173$. The first-stage saving $0.571843$ is the fraction of proposals requiring no target evaluation, including both eventual accepted and rejected proposals in the denominator; it is not conditional on acceptance.
Back to article page
