= Solution
Use the <ratio-of-uniforms method> on
$$
\mathcal R=\{(u,v):0<u\leq1,\ u^2\leq h(v/u)\}.
$$
Writing $x=v/u$ gives $u\leq e^{-x^2/(4\sigma^2)}$ and $v=ux$. Consequently
$$
|v|\leq\max_{x\geq0}x e^{-x^2/(4\sigma^2)}
=\sigma\sqrt{2/e},
$$
because the derivative vanishes at $x=\sigma\sqrt2$. Thus the <normal ratio-of-uniforms envelope> is the rectangle $0<u<1$, $|v|<\sigma\sqrt{2/e}$.
Generate <independent> $U_1,U_2$ with <uniform distribution> on $(0,1)$, set $u=U_1$ and $v=(2U_2-1)\sigma\sqrt{2/e}$, and accept precisely when
$$
u^2\leq\exp\!\left[-\frac{(v/u)^2}{2\sigma^2}\right].
$$
Reject and repeat otherwise. \b[On acceptance return $X=v/u$.] One can compare logarithms instead of exponentials to avoid underflow.
For a proof, the change of variables $(u,x)\mapsto(u,v=ux)$ has <Jacobian determinant> $u$. A uniform point in $\mathcal R$ therefore gives an $x$-density proportional to
$$
\int_0^{\sqrt{h(x)}}u\,du=\frac{h(x)}2.
$$
Normalizing yields the required <normal distribution> with <mean> zero and <variance> $\sigma^2$. The region area is $\frac12\int h(x)\,dx=\sigma\sqrt{\pi/2}$; dividing it by the rectangle area $2\sigma\sqrt{2/e}$ gives acceptance <probability> $\sqrt{\pi e}/4$.
Back to article page
