TAOCP 3.4.1 Exercise 6

Exercise 6. [HM21] A quantity $X$ is computed by the following method:

Step 1. Generate two independent uniform deviates $U$ and $V$.

Step 2. If $U^2 + V^2 \ge 1$, return to step 1; otherwise set $X \leftarrow U$.

What is the distribution function of $X$? How many times will step 1 be performed? (Give the mean and standard deviation.)

Verified: yes
Solve time: 1m41s

Solution

The algorithm generates two independent uniform deviates $U$ and $V$, each distributed on $[0,1]$, and rejects pairs for which $U^2 + V^2 \ge 1$. Otherwise, it sets $X \leftarrow U$. We analyze the resulting distribution function and the expected number of iterations.

Distribution Function of $X$

Let $F_X(x) = \Pr{X \le x}$ denote the distribution function of $X$. Consider the unit square $[0,1]^2$ for the pair $(U,V)$. The acceptance region is the set

$$ A = {(u,v) \in [0,1]^2 : u^2 + v^2 < 1}. $$

The algorithm selects $X = U$ if and only if $(U,V) \in A$. Therefore, for $0 \le x \le 1$,

$$ F_X(x) = \Pr{U \le x \mid (U,V) \in A} = \frac{\text{area}{(u,v) \in A : 0 \le u \le x}}{\text{area}(A)}. $$

The set ${(u,v) \in A : 0 \le u \le x}$ is bounded by $v \in [0, \sqrt{1-u^2}]$. Hence, its area is

$$ \int_{0}^{x} \sqrt{1-u^2}, du. $$

Similarly, the total area of $A$ is

$$ \int_{0}^{1} \sqrt{1-u^2}, du. $$

Therefore, for $0 \le x \le 1$,

$$ F_X(x) = \frac{\displaystyle \int_0^x \sqrt{1-u^2}, du}{\displaystyle \int_0^1 \sqrt{1-u^2}, du}. $$

Evaluating the integrals, we have

$$ \int_0^x \sqrt{1-u^2}, du = \frac{1}{2} \left( \arcsin x + x \sqrt{1-x^2} \right), \quad \int_0^1 \sqrt{1-u^2}, du = \frac{\pi}{4}. $$

Thus, the distribution function is

$$ F_X(x) = \frac{2}{\pi} \left( \arcsin x + x \sqrt{1-x^2} \right), \quad 0 \le x \le 1. \eqno(1) $$

For $x < 0$, $F_X(x) = 0$; for $x > 1$, $F_X(x) = 1$. Equation (1) completely describes the distribution function of $X$.

Expected Number of Iterations

Step 1 is repeated until a pair $(U,V)$ falls inside the quarter unit circle $u^2 + v^2 < 1$. Let $T$ denote the number of times step 1 is performed. Each trial is independent and has success probability equal to the area of the quarter circle:

$$ p = \text{area}(A) = \int_0^1 \sqrt{1-u^2}, du = \frac{\pi}{4}. $$

The number of trials until the first success follows a geometric distribution with parameter $p$. Therefore, the mean and standard deviation are

$$ \mathrm{E}[T] = \frac{1}{p} = \frac{4}{\pi}, \qquad \sigma_T = \frac{\sqrt{1-p}}{p} = \frac{\sqrt{1-\pi/4}}{\pi/4} = \frac{4 \sqrt{4-\pi}}{\pi}. $$

These values give the expected number of repetitions and its standard deviation.

This completes the proof.

∎

$$ \boxed{ F_X(x) = \frac{2}{\pi} \left( \arcsin x + x \sqrt{1-x^2} \right), \quad \mathrm{E}[T] = \frac{4}{\pi}, \quad \sigma_T = \frac{4 \sqrt{4-\pi}}{\pi} } $$