Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 40 / 3

Let $h\ge 0$ be proportional to the target probability density function, with $0<Z=\int h(x)dx<\infty$. Define the ratio-of-uniforms method through the regionDraw $(U,V)$ uniformly with respect to area on $A_h$ and return $X=V/U$. To prove its law, change variables from $(u,x)$ to $(u,v)=(u,ux)$. The Jacobian determinant is $u$, and the allowed interval for $u$ is $0<u\le \sqrt{h(x)}$. ConsequentlyThe joint density of $(U,X)$ is therefore $2u/Z$ on that interval. Integrating out $u$ givesFor an already normalized density, $Z=1$ and the region has area $1/2$. The name refers to the two coordinates of a uniformly sampled region; drawing two unrelated uniforms on arbitrary intervals and taking their ratio would not give the target law.

The region $A_h$ usually has a curved boundary, so sampling uniformly inside it directly is inconvenient. Rejection sampling replaces it by an easily sampled envelope, usually a rectangle. Choose finite bounds $a,b_{-},b_{+}$ withThen $A_h\subseteq (0,a)\times (b_{-},b_{+})$ up to null boundaries. A general rectangle algorithm uses only independent uniform deviates: draw $U_1,U_2$ on $(0,1)$, set $u=a{U}_1$, $v=b_{-}+(b_{+}-b_{-})U_2$, and return $v/u$ if $u^2\le h(v/u)$; otherwise repeat. If a numerical generator returns $u=0$, discard that draw before division. No knowledge of $Z$ is required to run the method. Its acceptance rate is the ratio of the two areas:More generally the same area ratio applies to any finite-area envelope $B$ sampled uniformly. A change in the proportionality constant of $h$ scales both ratio coordinates and their areas consistently.

Finite rectangle bounds are a real condition, not a consequence of integrability alone. For instance $h(x)=(1+|x|{)}^{-3/2}$ is integrable, but $|x|\sqrt{h(x)}$ is unbounded. A finite-area envelope for a ratio-of-uniforms region gives a general extension: choose a finite-area open envelope containing $A_h$, decompose it up to null boundaries into countably many disjoint rectangles, and select a rectangle with probability proportional to its area using a uniform draw and cumulative probabilities. Use two more uniforms to sample within it, then apply the same acceptance test. This samples the envelope uniformly and has acceptance $Z/(2\mathrm{area}(B))$. Such envelopes exist for every finite-area measurable $A_h$; obtaining usable bounds or an effective rectangle decomposition is density-specific. The finite-rectangle version above is the usual practical implementation.

For $\sigma >0$, use the unnormalized normal density $h(x)=e^{-x^2/(2{\sigma }^2)}$. Its ratio region isThe bound on $u$ is one because $h$ is maximized at zero. To bound $|v|$, maximize $x\sqrt{h(x)}=x{e}^{-x^2/(4{\sigma }^2)}$ for $x\ge 0$. Its derivative vanishes at $x=\sqrt{2}\sigma$, giving $b=\sigma \sqrt{2/e}$. Thus the normal ratio-of-uniforms envelope is $0<u<1$, $-b<v<b$.

Draw independent $U_1,U_2\sim \mathrm{Unif}(0,1)$, set $u=U_1$ and $v=b(2U_2-1)$, and accept precisely whenreturning $X=v/u$. Equivalently compare logarithms to avoid underflow. Since $Z=\sigma \sqrt{2\pi }$, the region area is $\sigma \sqrt{\pi /2}$ and the rectangle area is $2\sigma \sqrt{2/e}$. ThereforeIt is independent of the normal scale. In the diagram the vertical coordinate is normalized by $\sigma$, so the same shape works for every positive scale.