TAOCP 3.3.2 Exercise 14

Section 3.3.2: Empirical Tests

Exercise 14. ▶ [M15] If we "throw away" the element that immediately follows a run, so that when $X_i$ is greater than $X_{i+1}$ we start the next run with $X_{i+2}$, the run lengths are independent, and a simple chi-square test may be used (instead of the horribly complicated method derived in the text). What are the appropriate run-length probabilities for this simple run test?

Verified: no
Solve time: 2m22s

Solution

Let $\langle X_i \rangle = X_0, X_1, X_2, \ldots$ be a sequence of distinct numbers. In the original run test of Section 3.3.2, runs are defined as maximal ascending sequences, that is, sequences $X_j, X_{j+1}, \ldots, X_{j+r}$ such that $X_j < X_{j+1} < \cdots < X_{j+r}$ and either $X_{j-1} > X_j$ or $j = 0$, and either $X_{j+r} > X_{j+r+1}$ or $j+r = n-1$. In that framework, the run lengths are not independent because consecutive runs overlap: the last element of one run is the first element in the comparison for the next run. This interdependence complicates the derivation of the distribution of run lengths, requiring the combinatorial machinery presented in the text.

The modification proposed in the exercise discards the element immediately following a run, so that if a run ends at $X_i$, we skip $X_{i+1}$ and begin the next run at $X_{i+2}$. Denote by $R$ the length of a run observed in this modified procedure. Then the runs are independent because each run starts at a point that has not been involved in any previous run.

We now compute the probabilities of run lengths under this independence assumption. Consider the probability that a run has length $r \ge 1$. In a run of length $r$, the first $r$ consecutive comparisons must satisfy $X_j < X_{j+1} < \cdots < X_{j+r-1}$, and the run ends either because the next comparison fails (i.e., $X_{j+r-1} > X_{j+r}$) or because we discard $X_{j+r}$. Each comparison between two independent uniformly random distinct numbers has probability $1/2$ of being an ascent. Therefore the probability that exactly $r$ consecutive ascents occur is

$\Pr(R = r) = \left(\frac{1}{2}\right)^r \quad \text{for } r \ge 1.$

To see this, note that the first $r-1$ comparisons must be ascents, each with probability $1/2$, giving a factor $(1/2)^{r-1}$. The $r$-th comparison ends the run, which also has probability $1/2$ of being a descent. Multiplying these together yields $(1/2)^{r-1} \cdot (1/2) = (1/2)^r$.

Since the run lengths are independent, these probabilities apply to each run separately, and a chi-square test can be applied directly to the observed frequencies of runs of lengths $1,2,3,\ldots$. If the sequence is long enough, one can truncate the table at some maximum length $t$ and lump all longer runs into a single category, giving

$\Pr(R \ge t) = \sum_{r = t}^{\infty} \left(\frac{1}{2}\right)^r = \left(\frac{1}{2}\right)^{t-1} \cdot \frac{1}{2} = \left(\frac{1}{2}\right)^{t}.$

Thus the complete probability distribution for the simple run test is

$\Pr(R = r) = \left(\frac{1}{2}\right)^r \quad \text{for } 1 \le r \le t-1, \qquad \Pr(R \ge t) = \left(\frac{1}{2}\right)^t.$

This completes the derivation. The independence of runs and the geometric distribution of run lengths justify the use of a standard chi-square test in this simplified setting.

This completes the proof. ∎