TAOCP 3.4.1 Exercise 23

We are asked to determine whether the two methods described produce a random quantity $X$ with the same distribution.

taocpmathematicsalgorithmsvolume-2hm-medium

Section 3.4.1: Numerical Distributions

Exercise 23. [HM25] (J. von Neumann.) Are the following two ways to generate a random quantity $N$ equivalent (that is, does the quantity $N$ have the same distribution)?

Method 1: Set $X \leftarrow \sin((\pi/2)U)$, where $U$ is uniform.

Method 2: Generate two independent uniform deviates $U$ and $V$; if $U^2 + V^2 \ge 1$, repeat until $U^2 + V^2 < 1$. Then set $X \leftarrow (U^2 - V^2)/(U^2 + V^2)$.

Verified: yes
Solve time: 1m14s

Solution

We are asked to determine whether the two methods described produce a random quantity $X$ with the same distribution. Denote by $F_1(x)$ the distribution function of $X$ obtained from Method 1, and by $F_2(x)$ the distribution function of $X$ obtained from Method 2.

Method 1: Let $U$ be uniform on $[0,1]$ and define

$X = \sin\left(\frac{\pi}{2} U\right).$

The distribution function of $X$ is

$F_1(x) = \Pr{X \le x} = \Pr{\sin((\pi/2)U) \le x}.$

Since $\sin(\pi U/2)$ is strictly increasing on $[0,1]$, we can invert:

$\sin\left(\frac{\pi}{2} U\right) \le x \quad \Longleftrightarrow \quad U \le \frac{2}{\pi} \arcsin x.$

Hence

$F_1(x) = \frac{2}{\pi} \arcsin x, \qquad 0 \le x \le 1.$

The corresponding probability density function is

$f_1(x) = F_1'(x) = \frac{2}{\pi} \cdot \frac{1}{\sqrt{1 - x^2}}, \qquad 0 \le x \le 1.$

Method 2: Generate independent uniform $U, V \in [0,1]$ and reject until $U^2 + V^2 < 1$. Then set

$X = \frac{U^2 - V^2}{U^2 + V^2}.$

Introduce polar coordinates inside the unit quarter-circle (since $U, V \in [0,1]$):

$U = R \cos \theta, \quad V = R \sin \theta, \quad 0 \le R \le 1, \quad 0 \le \theta \le \pi/2.$

The Jacobian of the transformation is

$\frac{\partial(U,V)}{\partial(R,\theta)} = R.$

The rejection $U^2 + V^2 < 1$ corresponds to $0 \le R < 1$. Then

$X = \frac{U^2 - V^2}{U^2 + V^2} = \frac{R^2 \cos^2 \theta - R^2 \sin^2 \theta}{R^2} = \cos 2\theta.$

The angle $\theta$ is uniformly distributed in $[0,\pi/2]$ because the joint density of $(U,V)$ over the quarter unit disk is constant in area. Hence

$\Pr{X \le x} = \Pr{\cos 2\theta \le x} = \Pr{\theta \ge \frac{1}{2} \arccos x}.$

Since $\theta$ is uniform on $[0, \pi/2]$, we have

$F_2(x) = \Pr{\theta \le \frac{1}{2} \arccos x} = \frac{1}{\pi/2} \cdot \frac{\pi/2 - \frac{1}{2}\arccos x}{1} \quad \text{careful: verify}.$

Check carefully: the cumulative probability is

$\Pr{\theta \le \phi} = \frac{2}{\pi} \phi, \qquad 0 \le \phi \le \pi/2.$

We want $X \le x$, that is, $\cos 2\theta \le x \iff 2\theta \ge \arccos x \iff \theta \ge \frac{1}{2} \arccos x$. Therefore

$F_2(x) = \Pr{\theta \ge \frac{1}{2} \arccos x} = 1 - \frac{2}{\pi} \cdot \frac{1}{2} \arccos x = 1 - \frac{1}{\pi} \arccos x.$

Using the identity $\arcsin x = \pi/2 - \arccos x$, we have

$F_2(x) = 1 - \frac{1}{\pi} (\pi/2 - \arcsin x) = \frac{1}{2} + \frac{1}{\pi} \arcsin x.$

Comparison: Method 1 gives

$F_1(x) = \frac{2}{\pi} \arcsin x, \quad 0 \le x \le 1,$

while Method 2 gives

$F_2(x) = \frac{1}{2} + \frac{1}{\pi} \arcsin x, \quad 0 \le x \le 1.$

These are not equal. In particular, $F_1(1) = 2/\pi \cdot \pi/2 = 1$, while $F_2(1) = 1/2 + 1/\pi \cdot \pi/2 = 1$. However, at $x = 0$, $F_1(0) = 0$, while $F_2(0) = 1/2$. Therefore the two distributions differ.

This completes the proof. ∎