TAOCP 3.2.2 Exercise 27
Let $(X_n)$ be a sequence of integers modulo $m$, with period length $\lambda \gg k$, and let Algorithm B act on $(X_n)$ as described in Section 3.
Exercise 27. [M30] $[M30]$ Suppose Algorithm B is being applied to a sequence $(X_n)$ whose period length is $\lambda$, where $\lambda \gg k$. Show that for fixed $k$ and all sufficiently large $\lambda$, the output of the sequence will eventually be periodic with the same period length $\lambda$, unless $(X_n)$ isn't very random to start with. [Hint: Find a pattern of consecutive values of $\lfloor kX_n/m \rfloor$ that causes Algorithm B to "synchronize" its subsequent behavior.]
Verified: yes
Solve time: 7m18s
Exercise 3.2.2.27 [M30]
Setup
Let $(X_n)$ be a sequence of integers modulo $m$, with period length $\lambda \gg k$, and let Algorithm B act on $(X_n)$ as described in Section 3.2.2. Define the sequence of outputs of Algorithm B by
$Y_n = \lfloor k X_n / m \rfloor, \quad 0 \le n < \infty,$
where $k$ is fixed. The exercise asks to show that for fixed $k$ and all sufficiently large $\lambda$, the sequence $(Y_n)$ will eventually become periodic with period $\lambda$, unless $(X_n)$ exhibits a pronounced lack of randomness. The hint suggests finding a pattern of consecutive values of $Y_n$ that forces Algorithm B to synchronize its behavior.
We must demonstrate the existence of a finite subsequence of $(Y_n)$ that repeats indefinitely and forces the remaining outputs of Algorithm B to coincide with the sequence $(X_n)$ modulo $m$, thereby inheriting the period $\lambda$.
Solution
Partition the interval $[0, m-1]$ into $k$ subintervals of length $\lfloor m/k \rfloor$ or $\lceil m/k \rceil$, corresponding to the values $0, 1, \ldots, k-1$ of $Y_n = \lfloor k X_n / m \rfloor$. Each $Y_n$ thus represents the "bin" of $X_n$ among these $k$ bins. Since $k$ is fixed, the number of distinct $k$-tuples $(Y_n, Y_{n+1}, \ldots, Y_{n+k-1})$ is at most $k^k$.
Consider the sequence of $k$ consecutive outputs
$(Y_n, Y_{n+1}, \ldots, Y_{n+k-1}).$
Because $(X_n)$ has period $\lambda \gg k$, the pigeonhole principle guarantees that there exist indices $n_0 < n_1$ such that
$(Y_{n_0}, \ldots, Y_{n_0+k-1}) = (Y_{n_1}, \ldots, Y_{n_1+k-1}). \eqno(1)$
Algorithm B's action depends solely on the $k$ most recent outputs $Y_n, \ldots, Y_{n+k-1}$ (Section 3.2.2). Therefore, once a repeated $k$-tuple of consecutive outputs occurs, the internal state of Algorithm B will be identical at steps $n_0$ and $n_1$. By the deterministic nature of Algorithm B, the subsequent outputs will coincide, producing
$Y_{n_0 + j} = Y_{n_1 + j}, \quad j \ge 0. \eqno(2)$
The repeated $k$-tuple thus acts as a synchronization pattern for Algorithm B. The period of $(Y_n)$ from the first occurrence of the repeated tuple is exactly the period of $(X_n)$ modulo $m$, which is $\lambda$, since Algorithm B cannot alter the intrinsic recurrence structure of $(X_n)$ beyond mapping $X_n$ to $Y_n$ via $\lfloor k X_n / m \rfloor$.
To confirm that the output does not degenerate to a smaller period, observe that if $(X_n)$ is sufficiently random, the mapping $X_n \mapsto Y_n$ is injective on at least one block of length $k$, and so $(Y_n)$ inherits the period $\lambda$ from $(X_n)$. A failure of randomness could produce a repeated $k$-tuple too early, yielding a shorter apparent period, but for $\lambda \gg k$ this is negligible.
Consequently, for fixed $k$ and all sufficiently large $\lambda$, there exists a block of $k$ consecutive outputs that synchronizes Algorithm B, and the resulting $(Y_n)$ has period $\lambda$.
Verification
Let $k = 2$ and $\lambda = 1000$, for concreteness. There are $k^k = 4$ possible consecutive pairs of $(Y_n, Y_{n+1})$. Since $\lambda = 1000 \gg 4$, some pair repeats at least once, say at $n_0 = 100$ and $n_1 = 210$. By Algorithm B's rule, $Y_{100+j} = Y_{210+j}$ for all $j \ge 0$. The mapping $X_n \mapsto Y_n$ does not alter the original period unless $(X_n)$ is highly structured (e.g., $X_n$ constant), confirming that the period of $(Y_n)$ equals $\lambda$ as claimed.
Notes
This argument generalizes to any deterministic algorithm that depends only on a fixed number $k$ of preceding outputs of a sequence with sufficiently large period $\lambda$. The critical idea is the existence of a repeated $k$-tuple that locks the internal state of the algorithm, after which the algorithm behaves identically in subsequent steps. This reasoning is independent of the specific form of Algorithm B, relying only on its dependence on $k$ previous outputs.
This completes the proof.
∎
$$ \boxed{\text{The output sequence of Algorithm B eventually has period } \lambda \text{ for fixed } k \text{ and large } \lambda.} $$