TAOCP 3.3.2 Exercise 2

Exercise 2. [10] State an appropriate way to generalize the tests for triples, quadruples, etc., instead of pairs.

Verified: yes
Solve time: 1m26s

For triples, the serial test should count the occurrences of each ordered triple

$(Y_{3j},Y_{3j+1},Y_{3j+2}), \qquad 0\le j<n,$

for all $d^3$ possible values $(q,r,s)$ with $0\le q,r,s<d$. The observed frequencies are then subjected to a chi-square test with $k=d^3$ categories, each having probability $1/d^3$.

More generally, for $m$-tuples one should examine

$(Y_{mj},Y_{mj+1},\ldots,Y_{mj+m-1}), \qquad 0\le j<n,$

counting the occurrences of each of the $d^m$ possible ordered $m$-tuples. The chi-square test is then applied with $k=d^m$ categories, each of probability $1/d^m$. The tuples should be nonoverlapping, exactly as in the pair test, so that the observations used in the chi-square test are independent. The value of $d$ must be chosen small enough that $n$ is large compared with $d^m$. Thus the appropriate generalization is to test the uniform distribution of nonoverlapping ordered triples, quadruples, and, in general, ordered $m$-tuples. ∎