TAOCP 3.4.1 Exercise 20

Let $N$ be the number of executions of step R1 before the algorithm terminates.

taocpmathematicsalgorithmsvolume-2math-medium

Section 3.4.1: Numerical Distributions

Exercise 20. [M20] Let $A$ be the area of the shaded region in Fig. 13, and let $R$ be the area of the enclosing rectangle. Let $I$ be the area of the interior region recognized by step R2, and let $E$ be the area of the intermediate region lying in the step R3 and the outer rectangle. Determine the number of times each step of Algorithm R is performed, for each of its four variants as in (25), in terms of $A$, $R$, $I$, and $E$.

Verified: yes
Solve time: 3m04s

Solution

Let $N$ be the number of executions of step R1 before the algorithm terminates. In every variant of Algorithm R, a point is generated uniformly in the enclosing rectangle of area $R$, and the algorithm stops when a point in the shaded region of area $A$ is obtained. Therefore each trial succeeds with probability

$$ \frac{A}{R}, $$

so $N$ has a geometric distribution with mean

$$ E(N)=\frac{1}{A/R}=\frac{R}{A}. $$

Hence step R1 is performed

$$ \boxed{\frac{R}{A}} $$

times on average in every variant.

Since step R2 is executed once for each generated point, it is also performed

$$ \boxed{\frac{R}{A}} $$

times on average in every variant.

It remains to determine the expected number of executions of step R3.

Variant (i)

There is no step R3.

Hence

$$ R1=\frac{R}{A}, \qquad R2=\frac{R}{A}, \qquad R3=0. $$

Variant (ii): Interior recognition

The region recognized immediately by step R2 has area $I$. Thus step R3 is executed exactly when the generated point lies in the remainder of the shaded region, whose area is

$$ A-I. $$

For any single execution of R1, the probability that R3 is reached is

$$ \frac{A-I}{R}. $$

Since the expected number of executions of R1 is $R/A$, linearity of expectation gives

$$ E(#R3) = \frac{A-I}{R}\cdot \frac{R}{A} = \frac{A-I}{A}. $$

Therefore

$$ R1=\frac{R}{A}, \qquad R2=\frac{R}{A}, \qquad R3=\frac{A-I}{A}. $$

Variant (iii): Exterior recognition

The points requiring the detailed test R3 form the intermediate region of area $E$.

For each generated point,

$$ P(\text{R3 is executed})=\frac{E}{R}. $$

Hence

$$ E(#R3) = \frac{E}{R}\cdot \frac{R}{A} = \frac{E}{A}. $$

Therefore

$$ R1=\frac{R}{A}, \qquad R2=\frac{R}{A}, \qquad R3=\frac{E}{A}. $$

Variant (iv): Interior and exterior recognition

Step R2 immediately classifies both the interior region and the exterior region. Only points in the intermediate region of area $E$ reach step R3.

Thus

$$ P(\text{R3 is executed})=\frac{E}{R}, $$

and therefore

$$ E(#R3) = \frac{E}{R}\cdot \frac{R}{A} = \frac{E}{A}. $$

Hence

$$ R1=\frac{R}{A}, \qquad R2=\frac{R}{A}, \qquad R3=\frac{E}{A}. $$

Summary

$$ \begin{array}{c|c|c|c} \text{Variant} & E(#R1) & E(#R2) & E(#R3) \ \hline (i) & \dfrac{R}{A} & \dfrac{R}{A} & 0 \[8pt] (ii) & \dfrac{R}{A} & \dfrac{R}{A} & \dfrac{A-I}{A} \[8pt] (iii) & \dfrac{R}{A} & \dfrac{R}{A} & \dfrac{E}{A} \[8pt] (iv) & \dfrac{R}{A} & \dfrac{R}{A} & \dfrac{E}{A} \end{array} $$

These are the expected numbers of executions of the steps of Algorithm R for the four variants described in (25). ∎