Exercise 311. [21] Compute approximate values of $EX$ for the 100 probability distributions of exercise 306(b) when $n = l = 100$, using the method of exercise 307 with the sequences $\langle S_n \rangle$ of exercise 308 and $\langle S'_n \rangle$ of exercise 310. Also consider the more easily generated "ruler doubling" sequence $\langle R_n \rangle$, where $R_n = n, &, -n = 2^{\nu n}$. Which sequence is best?

Verified: no
Solve time: 7m03s

Solution

The computation in this exercise is an experimental comparison, so the numerical values depend on the $100$ distributions $p^{(m)}$ defined in exercise 306(b) and on the exact cost function $l(N)$ defined there. The information supplied here does not include those distributions or the definition of $l(N)$, so the numerical table cannot be reconstructed from the exercise statement alone.

For each distribution $p^{(m)}$, the computation proceeds from exercise 307. Given a sequence of cutoff values

$$ (N_1,N_2,\ldots), $$

define

$$ T_j=N_1+\cdots+N_j . $$

Exercise 307 gives

$$ EX=\sum_{j\ge1}\Pr(T_{j-1}<X\le T_j),l(N_j), $$

provided the chosen sequence satisfies the required positivity condition. Therefore the value of $EX$ is obtained by evaluating the probability terms for the particular distribution $p^{(m)}$ and substituting the chosen cutoff sequence.

The first experiment uses the reluctant doubling sequence from exercise 308. The cutoff values are

$$ N_j=S_j . $$

For each of the $100$ distributions $p^{(m)}$, one computes

$$ E_m^{(S)}

\sum_{j\ge1} \Pr_m(T_{j-1}<X\le T_j),l(S_j). $$

The second experiment uses the reluctant Fibonacci sequence from exercise 310. Its cutoff values are

$$ N_j=S'_j , $$

and the corresponding values are

$$ E_m^{(S')}

\sum_{j\ge1} \Pr_m(T_{j-1}<X\le T_j),l(S'_j). $$

The third experiment uses the ruler doubling sequence

$$ N_j=R_j=j,&,(-j)=2^{\nu j}, $$

which gives

$$ E_m^{(R)}

\sum_{j\ge1} \Pr_m(T_{j-1}<X\le T_j),l(R_j). $$

The comparison requested in the exercise is then obtained by computing the three arrays

$$ {E_m^{(S)}}{m=1}^{100}, \qquad {E_m^{(S')}}{m=1}^{100}, \qquad {E_m^{(R)}}_{m=1}^{100}, $$

and comparing the values for each distribution. The best sequence is the one whose corresponding values of $EX$ are smallest over the given family of $100$ distributions.

A numerical answer requires the explicit $p^{(m)}$ from exercise 306(b) and the function $l(N)$ from exercise 306. Without those definitions, any claimed numerical values would be unsupported. With them, the calculation is a direct finite computation using the three displayed formulas.

Thus the corrected conclusion is that the method is completely specified by exercises 306, 307, 308, and 310, but the numerical values and the winner among the three sequences cannot be derived from the information provided here.

TAOCP 7.2.2.2 Exercise 311

Solution

$$ E_m^{(S)}

$$ E_m^{(S')}

$$ E_m^{(R)}