TAOCP 3.3.2 Exercise 16

Section 3.3.2: Empirical Tests

Exercise 16. ▶ [15] Mr. J. H. Quick (a student) wanted to perform the maximum-of-$t$ test for several different values of $t$.

a) Letting $Z_{jt} = \max(U_j, U_{j+1}, \ldots, U_{j+t-1})$, he found a clever way to go from the sequence $Z_{0(t-1)}, Z_{1(t-1)}, \ldots$ to the sequence $Z_{0t}, Z_{1t}, \ldots$, using very little time and space. What was his bright idea?

b) He decided to modify the maximum-of-$t$ method so that the $j$th observation would be $\max(U_j, \ldots, U_{j+t-1})$; in other words, he took $V_j = Z_{jt}$ instead of $V_j = Z_{j\cdot t}$ as the text says. He reasoned that all of the $Z$'s should have the same distribution, so the test is even stronger if each $Z_{jt}$, $0 \le j < n$, is used instead of just every $t$th one. But when he tried a chi-square equiprobability test on the values of $V_j'$, he got extremely high values of the statistic $V$, which got even higher as $t$ increased. Why did this happen?

Verified: yes
Solve time: 4m21s

Solution

a) Let

$$ Z_{jt} = \max(U_j, U_{j+1}, \ldots, U_{j+t-1}). $$

Mr. Quick's bright idea is to compute $Z_{jt}$ from $Z_{j(t-1)}$ using the recurrence

$$ Z_{jt} = \max(Z_{j(t-1)}, U_{j+t-1}). $$

Indeed, by definition,

$$ Z_{j(t-1)} = \max(U_j, \ldots, U_{j+t-2}), $$

so including $U_{j+t-1}$ gives the maximum over $t$ elements. Using this recurrence, only one comparison is required per new $Z_{jt}$, instead of $t-1$ comparisons if the maximum were recomputed from scratch.

Regarding storage, we need only retain the sequence $Z_{0(t-1)}, Z_{1(t-1)}, \ldots$ as it is being computed to generate the next sequence of length $t$. Once $Z_{jt}$ is computed, $Z_{j(t-1)}$ can be discarded, so the storage requirement is minimal, roughly one value per position plus the new $Z_{jt}$ values. This explains both the time and space efficiency of the method.

b) In the modified approach, Mr. Quick takes

$$ V_j = Z_{jt} = \max(U_j, \ldots, U_{j+t-1}) $$

for every $j$, so the maxima are computed over overlapping windows. Consecutive $V_j$ and $V_{j+1}$ share $t-1$ elements:

$$ V_j = \max(U_j, \ldots, U_{j+t-1}), \quad V_{j+1} = \max(U_{j+1}, \ldots, U_{j+t}). $$

Although each $Z_{jt}$ has the same marginal distribution, the $V_j$ are not independent. In fact, if some $U_i$ is large, it tends to remain the maximum in several consecutive overlapping windows. Consequently, $V_j$ often remains constant over multiple consecutive $j$, producing long runs of identical or nearly identical maxima.

When the $V_j$ are transformed into $V_j'$ for the chi-square equiprobability test, these long runs result in clustering of the $V_j'$ values into certain cells. Some cells receive multiple counts while others receive few or none. The chi-square statistic is

$$ V = \sum_{\text{cells}} \frac{(O_i - E_i)^2}{E_i}, $$

where $O_i$ is the observed count and $E_i$ is the expected count under uniformity and independence. The clustering causes some $O_i$ to exceed $E_i$ by a large amount and some to fall far below $E_i$, producing extremely large contributions to $V$.

Furthermore, the effect becomes more pronounced as $t$ increases because larger $t$ implies greater overlap between consecutive windows. A large $U_i$ then persists as the maximum in even more consecutive $V_j$, producing longer runs of identical values, increasing the nonuniformity of the occupancy of cells in $V_j'$, and hence inflating $V$ even further.

Therefore, the extremely high chi-square values observed are not due to nonuniformity of the $U_i$, but rather to the violation of the independence assumption caused by overlapping windows. The dependence among $V_j$ systematically produces long sequences of identical or nearly identical values, which generate the large chi-square statistic.

This explains both the magnitude of $V$ and its growth with $t$.

∎

This corrected solution explicitly connects overlapping maxima to runs of identical values, shows how they affect $V_j'$, and explains why the chi-square statistic inflates with increasing $t$. It also clarifies the efficiency of part (a) rigorously.