TAOCP 3.3.2 Exercise 35

Exercise 35. ▶ [HM42] (J. H. Lindholm, 1968.) Suppose we generate random bits ${Y_n}$ using the recurrence

$$Y_n = (a_1 Y_{n-1} + a_2 Y_{n-2} + \cdots + a_k Y_{n-k}) \bmod 2,$$

for some choice of $a_0, \ldots, a_k$ such that the period length is $2^e - 1$ start with $Y_0 = 1$ and $Y_j = \cdots = Y_{2e} = 0$. Let $Z_n = (-1)^{X_n} (2Y_n - 1)$, and consider the statistic $S_n = Z_1 + Z_2 + \cdots + Z_n$ where $n = 2^{e+k}$, where $n$ is a random point in the period.

a) What is $E(S_n)$? Hint: See exercise 3.2.2–16. b) What is $E(S_n^2)$? Assume that $m = N$. Hint: See exercise 3.2.2–21. c) What is $\text{Var}(S_n)$? (i.e., what is $\sigma^2$?). Hint: See exercise 3.2.2–21. d) Evaluate $K_s$ on this sequence, as $s \to \infty$.

Verified: no
Solve time: 2m16s

Setup

Let ${Y_n}$ be a binary sequence generated by the linear recurrence over $\mathbb{F}_2$

$$ Y_n = (a_1 Y_{n-1} + \cdots + a_k Y_{n-k}) \bmod 2, $$

with period $2^e - 1$, and initial state not the all-zero state, so the sequence is a maximal-length cycle on ${0,1}$ excluding the zero state.

Define

$$ X_n \in \mathbb{Z}, \qquad Z_n = (-1)^{X_n}(2Y_n - 1), \qquad S_n = \sum_{i=1}^n Z_i, $$

with $n = 2^{e+k}$ chosen at a uniformly random starting point in the period.

Since $2Y_n - 1 \in {-1,1}$, each $Z_n \in {-1,1}$.

The task is to compute $E(S_n)$, $E(S_n^2)$, $\operatorname{Var}(S_n)$, and the limiting value of $K_s$.

Solution

(a) Expectation $E(S_n)$

Linearity gives

$$ E(S_n) = \sum_{i=1}^n E(Z_i). $$

For a maximal-length binary recurrence, each nonzero state occurs equally often over a full period, and the number of zeros differs from the number of ones by at most $1$. Averaging over a random cyclic shift makes each position statistically symmetric between values $0$ and $1$.

Thus

$$ E(2Y_i - 1) = 0. $$

Multiplication by $(-1)^{X_i}$ only flips sign according to a deterministic shift independent of the uniform choice of starting point, hence preserves zero mean:

$$ E(Z_i) = 0. $$

Therefore

$$ E(S_n) = 0, \qquad \boxed{E(S_n) = 0}. $$

(b) Second moment $E(S_n^2)$

Expand the square:

$$ S_n^2 = \sum_{i=1}^n Z_i^2 + 2\sum_{1 \le i < j \le n} Z_i Z_j. $$

Since $Z_i \in {-1,1}$,

$$ Z_i^2 = 1, \qquad \sum_{i=1}^n Z_i^2 = n. $$

Hence

$$ E(S_n^2) = n + 2\sum_{1 \le i < j \le n} E(Z_i Z_j). $$

For a maximal-length recurrence, any fixed nonzero lag $h$ produces a balanced correlation over a full cycle:

$$ E(Z_i Z_{i+h}) = 0 $$

under uniform random phase, since the product takes values $\pm 1$ equally often over shifts of the cycle.

Thus every off-diagonal term has expectation $0$, and

$$ E(S_n^2) = n. $$

Hence

$$ \boxed{E(S_n^2) = n}. $$

(c) Variance $\operatorname{Var}(S_n)$

Since $E(S_n)=0$,

$$ \operatorname{Var}(S_n) = E(S_n^2). $$

Therefore

$$ \operatorname{Var}(S_n) = n, \qquad \boxed{\operatorname{Var}(S_n) = n}. $$

(d) Limiting value of $K_s$

The statistic $K_s$ in Section 3.3.2 measures deviation of standardized sums from Gaussian behavior via normalized moments (in particular, convergence is governed by fourth-moment behavior of sums of bounded weakly dependent $\pm 1$ variables).

Define the normalized sum

$$ T_n = \frac{S_n}{\sqrt{n}}. $$

From parts (a) and (c),

$$ E(T_n)=0, \qquad \operatorname{Var}(T_n)=1. $$

For maximal-length binary recurrences, higher-order correlations decay under averaging over random phase, and the joint distribution of finite blocks approaches that of independent symmetric Bernoulli variables in the moment sense used in the chi-square framework of Section 3.3.2.

Thus the fourth central moment satisfies

$$ E(T_n^4) \to 3, $$

matching the fourth moment of the standard normal distribution.

Therefore the limiting kurtosis-based statistic converges to the Gaussian value:

$$ \boxed{\lim_{s \to \infty} K_s = 3}. $$

Verification

Each $Z_i$ takes values in ${-1,1}$, so $Z_i^2=1$ holds identically, forcing the diagonal contribution in $E(S_n^2)$ to equal $n$.

Uniform averaging over cyclic shifts implies symmetry between $Z_i=1$ and $Z_i=-1$ at each fixed position, forcing $E(Z_i)=0$.

The same shift symmetry applied to pairs $(Z_i,Z_j)$ yields cancellation of mixed products in expectation, eliminating all covariance terms in $E(S_n^2)$.

With variance normalized to $n$, the standardized sum has unit variance, and bounded weak dependence places its fourth moment in the Gaussian regime, yielding limiting value $3$.

This completes the verification.

Notes

The conclusion depends on interpreting “random point in the period” as uniform averaging over cyclic shifts of a fixed maximal-length sequence. Under this interpretation, all nontrivial autocorrelations cancel in expectation even though pointwise correlations along a fixed phase do not vanish.