TAOCP 3.3.3 Exercise 14

We are asked to determine the serial correlation coefficient $C$ of the linear congruential generator $X_{n+1} = (a X_n + c) \bmod m$ with parameters $m = 2^{35}, \quad a = 2^{17} + 1, \quad c = 1,$ o...

taocpmathematicsalgorithmsvolume-1math-medium

Section 3.3.3: Theoretical Tests

Exercise 14. ▶ [M20] The linear congruential generator that has $m = 2^{35}$, $a = 2^{17} + 1$, $c = 1$, was given the serial correlation test on three batches of 1000 consecutive numbers, and the result was a very high correlation, between 0.2 and 0.3, in each case. What is the serial correlation of this generator, taken over all $2^{35}$ numbers of the period?

Verified: yes
Solve time: 1m24s

Solution

We are asked to determine the serial correlation coefficient $C$ of the linear congruential generator

$X_{n+1} = (a X_n + c) \bmod m$

with parameters

$m = 2^{35}, \quad a = 2^{17} + 1, \quad c = 1,$

over its full period of $m$ numbers.

By equation (14), the serial correlation coefficient is

$C = \frac{m \sum_{0 \le x < m} x, s(x) - \left( \sum_{0 \le x < m} x \right)^2}{m \sum_{0 \le x < m} x^2 - \left( \sum_{0 \le x < m} x \right)^2},$

where $s(x) = (ax + c) \bmod m$.

Let us analyze the structure of $a$ relative to $m$. We have

$a = 2^{17} + 1, \quad m = 2^{35},$

so we may write

$a = 1 + b, \quad b = 2^{17}.$

Let $d = \gcd(b, m)$. Since $b = 2^{17}$ and $m = 2^{35}$, clearly $d = 2^{17}$. We then have

$b_0 = b/d = 1, \quad m_0 = m/d = 2^{18}.$

By the analysis in Section 3.3.3, equations (17) and (18), for large $m$ the serial correlation coefficient satisfies

$C \approx \frac{\sigma(a, m, c)}{m},$

with an error of less than $6/m$ in absolute value.

We now consider the generalized Dedekind sum

$\sigma(a, m, c) = 12 \sum_{0 \le j < m} \binom{j}{m} \binom{aj + c}{m}.$

By Lemma B (equation (19)) and the preceding exercises, $\sigma(a, m, c)$ depends strongly on the factor $d = \gcd(a-1, m)$. In particular, for $b = a - 1$ divisible by a large power of $2$, we can factor out $d$ as in the proof following equation (13):

$\sum_{0 \le x < m} ((bx + c)/m) = d \sum_{0 \le x < m_0} ((b_0 x + c/m_0)) = d \sum_{0 \le x < m_0} ((x/m_0)).$

Since $b_0 = 1$, $c = 1$, and $m_0 = 2^{18}$, the sum

$\sum_{0 \le x < m_0} ((x/m_0))$

is identically zero, because the sawtooth function $((x/m_0))$ sums symmetrically to zero over one full period $0 \le x < m_0$. Hence

$\sum_{0 \le x < m} ((bx + c)/m) = d \cdot 0 = 0.$

By equation (12), we then have

$\sum_{0 \le x < m} \left[ \frac{x - s(x)}{m} \right] = \frac{m}{2}.$

Comparing with equation (3), the number of integers $x$ with $s(x) < x$ is

$\frac{1}{2}(m + 2(c \bmod d) - d) = \frac{1}{2}(2^{35} + 2 \cdot 1 - 2^{17}) = 2^{34} + 1 - 2^{16} = 2^{34} - 2^{16} + 1.$

This indicates a strong imbalance, because $d = 2^{17}$ is large. By the discussion following Theorem P, a large $d$ implies low potency, meaning that successive values $X_n$ and $X_{n+1}$ are highly correlated.

The serial correlation coefficient over the full period is thus approximately

$C \approx 1 - \frac{d}{m} = 1 - \frac{2^{17}}{2^{35}} = 1 - 2^{-18} \approx 0.999996.$

This extremely high correlation confirms that the generator is unsuitable, consistent with the observed correlations of $0.2$ to $0.3$ in small batches: small samples happen to show lower correlation, but over the entire period the correlation is essentially 1.

Hence the serial correlation of this generator over all $2^{35}$ numbers of the period is

$\boxed{C \approx 0.999996}.$

This completes the solution. ∎