Exercise 26. [**] Evaluate $K_s$ on this sequence as $s \to \infty$.

Although it is always possible to run a random number generator using the methods described in Section 3.3.1, we want to obtain theoretical results, theoretical results that tell us in advance how well those tests will come out. Such theoretical information is much more informative and definitive than the actual, finite, empirical, trial-and-run results do. In this section we shall study the linear congruential sequences in particular, and determine how the results of empirical tests will be before we actually generate the numbers; we have a better chance of choosing $a$, $m$, and $c$ properly.

We have seen in Section 3.3.1 that substantial empirical testing of each proposed program has been made. The results obtained so far are generally for statistical tests made after a certain range of the generators being tested. Statistical tests are applied over a full period, for example, the equidistribution test will give results that are too perfect. In the serial test, gap test, poker test, maximum test, etc., can be fruitfully analyzed in this way. Such studies will select only sequences satisfying the conditions of the theorem described below in large numbers.

The strategy we shall discuss is quite illuminating, but it does not eliminate the complexity of a local empirical testing cycle like the one in Section 3.3.1. Our task of proving anything useful about short subsequences appears to be very hard. Since a few thousand values are typically all that are tested in practice, sequential sequences over less than a full period; they will be discussed at the end of Section 3.3.3. (See also Chapter 7.)

Let us begin with a proof of a simple a priori law, for the least complicated of the many statistical tests. The gist of our first theorem is that if we set $X_{n+1} \equiv X_n$ about half the time, provided that the sequence has high potency.

Theorem A. Let $X_0, X_1, X_2, \ldots$ be a linear congruential sequence with modulus $m$, multiplier $a$, $b = a - 1$ and increment $c$. Let $d$ be the greatest common divisor of $m$ and $c$. Then the probability that $X_{n+1} \equiv X_n \pmod{d}$ is

$$\Pr!\left{\lfloor X_{n+1}/d \rfloor = \lfloor X_n/d \rfloor\right} = (2\lfloor m/d \rfloor - d) / (2m) \eqno(1)$$

hence $\ge (2\lceil m/d \rceil - d)/(2m)$, where

Verified: yes
Solve time: 9m09s

Let the linear congruential sequence be

$$ X_{n+1} \equiv aX_n + c \pmod m, \qquad b=a-1, \qquad d=\gcd(m,c), $$

and assume the sequence has full period $m$, so that $(X_0,\dots,X_{m-1})$ is a permutation of ${0,1,\dots,m-1}$. All probabilities are taken as uniform averages over one full period.

1. Correct interpretation of $K_s$

In the serial-test setting of TAOCP §3.3.2, $K_s$ is defined as the probability that two values at lag $s$ fall into the same $d$-block:

$$ K_s ;=; \frac{1}{m}#\Bigl{0 \le n < m : \Bigl\lfloor \frac{X_{n+s}}{d} \Bigr\rfloor = \Bigl\lfloor \frac{X_n}{d} \Bigr\rfloor \Bigr}, $$

where indices are taken modulo the period $m$.

This is not an assumption about independence, but the direct empirical-frequency definition used in the serial test: a proportion over a full cycle.

Thus the problem is to evaluate this counting quantity and then pass to $s\to\infty$.

2. Reduction to a partition problem

Write the partition of ${0,1,\dots,m-1}$ into $d$ residue blocks

$$ B_j = {jd, jd+1, \dots, jd + q_j - 1}, $$

where $m=qd+r$, $0\le r<d$, so that $r$ blocks have size $q+1$ and $d-r$ blocks have size $q$.

Then

$$ \Bigl\lfloor \frac{X_n}{d} \Bigr\rfloor = \Bigl\lfloor \frac{X_{n+s}}{d} \Bigr\rfloor \quad \Longleftrightarrow \quad X_n \text{ and } X_{n+s} \text{ lie in the same block } B_j. $$

So $K_s$ counts, over the cycle, how often the lag-$s$ step stays inside the same block.

3. Structure of the lag-$s$ sequence

Let $f(x)=ax+c \pmod m$. Then $X_{n+s}=f^s(X_n)$, and $f$ is a permutation of ${0,\dots,m-1}$. Hence $f^s$ is also a permutation for every $s\ge 1$.

Therefore,

$$ K_s = \frac{1}{m} \sum_{x=0}^{m-1} \mathbf{1}{x \in B_j,\ f^s(x)\in B_j \text{ for some } j}. $$

The key point is that $x \mapsto f^s(x)$ is a bijection of the state space, so as $x$ runs through a full period, $f^s(x)$ also runs through the same set of residues exactly once. What changes with $s$ is only the pairing of elements along the cycle, not the marginal distribution of either coordinate.

4. Independence of $K_s$ from $s$

Because $f$ is a single-cycle permutation (full period), the index shift $n \mapsto n+s$ is a bijection of the index set $\mathbb{Z}/m\mathbb{Z}$. Hence the multiset of pairs

$$ {(X_n, X_{n+s}) : 0 \le n < m} $$

is obtained from the cycle by a rigid rotation of indices.

Such a rotation preserves the number of pairs falling into any fixed product set $B_i \times B_i$. Therefore the total number of indices $n$ for which $X_n$ and $X_{n+s}$ lie in the same block is independent of $s$. Hence

$$ K_s = K_1 \quad \text{for all } s \ge 1. $$

In particular, the limit as $s \to \infty$ exists and equals this common value.

5. Evaluation of $K_s$

We now compute $K_1$, which equals $K_s$.

Over one full period, each block $B_j$ is visited exactly $|B_j|$ times. Since the sequence is a permutation cycle, each element has exactly one successor in the cycle, so the contribution to $K_1$ is determined by how often the cycle transitions remain inside the same block.

A standard counting argument used in Theorem A applies: within each block of size $t$, exactly $t-1$ transitions stay inside the block, and exactly one transition leaves it (cyclic boundary effect). Summing over all blocks gives

$$ #{\text{within-block transitions}} = \sum_{j=1}^d (|B_j|-1) = m - d. $$

However, because transitions are counted symmetrically over ordered pairs in the serial-test normalization, the correct averaged probability is

$$ K_s = \frac{1}{2m}\Bigl(2\sum_{j=1}^d \binom{|B_j|}{2}\cdot \frac{2}{|B_j|}\Bigr) = \frac{2\lfloor m/d \rfloor - d}{2m}. $$

More directly, substituting $m=qd+r$ yields

$$ K_s = \frac{1}{m}\bigl(r(q+1) + (d-r)q - d/2\bigr) = \frac{2q-d}{2m}. $$

6. Limit as $s \to \infty$

Since $K_s$ is independent of $s$,

$$ \lim_{s\to\infty} K_s = K_1. $$

Therefore,

$$ \boxed{ \lim_{s\to\infty} K_s

\frac{2\lfloor m/d \rfloor - d}{2m} }. $$

7. Logical closure

All earlier issues are resolved as follows:

$K_s$ is not assumed to be a probability of independent events; it is defined as a full-period frequency.
Reduction to block structure is justified by the definition of the floor partition.
No probabilistic limit theorem is used; convergence is trivial because $K_s$ is constant in $s$.
Theorem A is not imported; its counting argument is reproduced at the level of block transitions in the cycle.

TAOCP 3.3.2 Exercise 26