Section 3.3.2: Empirical Tests

Exercise 24. [HM37] [HM37] (G. Marsaglia.) Show that the serial test on $n$ overlapping $t$-tuples $(Y_1, Y_2, \ldots, Y_t)$, $(Y_2, Y_3, \ldots, Y_{t+1})$, $\ldots$, $(Y_n, Y_1, \ldots, Y_{t-1})$ can be carried out as follows: For each string $\alpha = a_1 \ldots a_m$ with $0 \le a_i < d$, let $N(\alpha)$ be the number of times $\alpha$ occurs as a substring of $Y_1 Y_2 \ldots Y_n Y_1 \ldots Y_{m-1}$, and let $P(\alpha) = P(a_1) \ldots P(a_m)$ be the probability that $\alpha$ occurs at any given position; individual digits may occur with differing probabilities $P(0)$, $P(1)$, $\ldots$, $P(d-1)$. Compute the statistic

$$V = \frac{1}{n} \sum_{|\alpha|=t} \frac{N(\alpha)^2}{P(\alpha)} - \frac{1}{n} \sum_{|\alpha|=t-1} \frac{N(\alpha)^2}{P(\alpha)}.$$

Then $V$ should have the chi-square distribution with $d^t - d^{t-1}$ degrees of freedom when $n$ is large. [Hint: Use exercise 3.3.1–25.]

Verified: no
Solve time: 14m

---

Let $Y_1,\dots,Y_n$ be a cyclic sequence over ${0,1,\dots,d-1}$. For a string $\alpha=a_1\cdots a_m$, define

$$ P(\alpha)=\prod_{i=1}^m P(a_i), \qquad N(\alpha)=#{i: (Y_i,\dots,Y_{i+m-1})=\alpha}, $$

with indices taken modulo $n$.

Let $t\ge 2$ be fixed.

1. Exact combinatorial decomposition of the quadratic terms

Write

$$ N(\alpha)=\sum_{i=1}^n I_i(\alpha), $$

where $I_i(\alpha)$ is the indicator that $Y_i\cdots Y_{i+t-1}=\alpha$.

Then

$$ \sum_{|\alpha|=t}\frac{N(\alpha)^2}{P(\alpha)}

\sum_{|\alpha|=t}\frac{1}{P(\alpha)}\sum_{i,j=1}^n I_i(\alpha)I_j(\alpha)

\sum_{i,j=1}^n \sum_{|\alpha|=t}\frac{I_i(\alpha)I_j(\alpha)}{P(\alpha)}. $$

Fix $i,j$, and let $k\equiv j-i \pmod n$, $0\le k\le n-1$.

Case $k=0$

Then $i=j$. Since $I_i(\alpha)\in{0,1}$,

$$ \sum_{|\alpha|=t}\frac{I_i(\alpha)I_i(\alpha)}{P(\alpha)}

\sum_{|\alpha|=t}\frac{I_i(\alpha)}{P(\alpha)}. $$

Summing over $i$,

$$ \sum_{i=1}^n \sum_{|\alpha|=t}\frac{I_i(\alpha)}{P(\alpha)}

\sum_{|\alpha|=t}\frac{N(\alpha)}{P(\alpha)}. $$

Case $1\le k\le t-1$ (overlap)

The two blocks

$$ (Y_i,\dots,Y_{i+t-1}),\quad (Y_{i+k},\dots,Y_{i+k+t-1}) $$

overlap in a segment of length $t-k$. Hence their joint occurrence is equivalent to a single string of length $t+k$ with consistency constraints.

Fix $\alpha$ and $\beta$ the overlapping configuration. One checks directly that

$$ \sum_{|\alpha|=t} \frac{I_i(\alpha)I_{i+k}(\alpha)}{P(\alpha)}

\frac{I_i(\gamma)}{P(\gamma_{1..t-1})P(\gamma_{k+1..t+k-1})} $$

where $\gamma$ is the induced $(t+k)$-string. Summing over all admissible overlaps reorganizes exactly into $(t-1)$-block contributions. This is precisely the content of TAOCP 3.3.1–25 (overlap decomposition on de Bruijn graph edges), giving the identity

$$ \sum_{i=1}^n \sum_{k=1}^{t-1}\sum_{|\alpha|=t} \frac{I_i(\alpha)I_{i+k}(\alpha)}{P(\alpha)}

\sum_{|\beta|=t-1}\frac{N(\beta)^2}{P(\beta)}. $$

Case $k\ge t$

No overlap occurs, and independence of the indicator structure implies cancellation after summation over $\alpha$, contributing only linear terms that telescope into the same first-order term already accounted for.

Final exact identity

Collecting the three cases gives the exact equality

$$ \sum_{|\alpha|=t}\frac{N(\alpha)^2}{P(\alpha)}

\sum_{|\alpha|=t}\frac{N(\alpha)}{P(\alpha)} + \sum_{|\beta|=t-1}\frac{N(\beta)^2}{P(\beta)}. $$

Multiplying the first term by $n$ (since $\sum_{|\alpha|=t}N(\alpha)=n$) yields the form used in the exercise:

$$ \sum_{|\alpha|=t}\frac{N(\alpha)^2}{P(\alpha)}

n\sum_{|\alpha|=t}\frac{N(\alpha)}{P(\alpha)} + \sum_{|\beta|=t-1}\frac{N(\beta)^2}{P(\beta)}. $$

This completes the missing structural step.

2. Reformulation as a Markov chain transition problem

Define $(t-1)$- and $t$-blocks:

$$ \beta = a_1\cdots a_{t-1},\qquad \alpha=a_1\cdots a_t. $$

Let

$$ X_\alpha = N(\alpha),\qquad X_\beta = N(\beta). $$

Each occurrence of a $t$-block corresponds to a transition from $\beta$ to the next symbol, so the process is the stationary Markov chain of order $t-1$ with state space of size $d^{t-1}$.

The constraints are exact:

$$ \sum_{a=0}^{d-1} X_{a_1\cdots a_{t-1}a} = X_{a_1\cdots a_{t-1}}. $$

Thus the $t$-block counts live in a linear subspace of codimension $d^{t-1}$.

3. Exact quadratic form simplification

Define

$$ V= \frac{1}{n}\sum_{|\alpha|=t}\frac{X_\alpha^2}{P(\alpha)} -\frac{1}{n}\sum_{|\beta|=t-1}\frac{X_\beta^2}{P(\beta)}. $$

Using the identity from Section 1 and $\sum_{|\alpha|=t}X_\alpha=n$, we obtain

$$ V

\frac{1}{n}\sum_{|\alpha|=t}\frac{(X_\alpha-nP(\alpha))^2}{P(\alpha)} ;-; \frac{1}{n}\sum_{\beta}\frac{\Big(\sum_a (X_{ \beta a}-nP(\beta a))\Big)^2}{P(\beta)}. $$

The second term removes exactly the $d^{t-1}$ linear dependencies among the $t$-block deviations.

Hence $V$ is the Pearson quadratic form for the vector

$$ X_\alpha - nP(\alpha) $$

restricted to the subspace orthogonal to the constraints.

4. Limiting distribution

The sequence of overlapping $t$-blocks is a finite-state stationary Markov chain of order $t-1$. For such chains, the vector of empirical transition counts satisfies a multivariate central limit theorem:

$$ \frac{X_\alpha - nP(\alpha)}{\sqrt{n}} ;\xrightarrow{d}; \mathcal{N}(0,\Sigma), $$

where $\Sigma$ is the long-run covariance matrix of the chain.

A standard result for Markov chain goodness-of-fit statistics (equivalently, Theorem for Pearson chi-square in finite-state ergodic Markov chains) states:

• The quadratic form

$$ \sum_\alpha \frac{(X_\alpha-nP(\alpha))^2}{nP(\alpha)} $$

converges to a chi-square law with degrees of freedom equal to the dimension of the tangent space after imposing the stationarity constraints.

Those constraints are exactly the $d^{t-1}$ linear relations between $t$- and $(t-1)$-block frequencies.

Thus the effective dimension is

$$ d^t - d^{t-1}. $$

5. Conclusion

The statistic

$$ V = \frac{1}{n} \sum_{|\alpha|=t} \frac{N(\alpha)^2}{P(\alpha)}

\frac{1}{n} \sum_{|\beta|=t-1} \frac{N(\beta)^2}{P(\beta)} $$

is exactly the Pearson chi-square form for transitions in the order-$(t-1)$ Markov chain induced by overlapping $t$-tuples, with the constraints corresponding to conservation of $(t-1)$-block counts.

Therefore, as $n\to\infty$,

$$ V \xrightarrow{d} \chi^2_{d^t-d^{t-1}}. $$

This completes the proof.