TAOCP 3.1 Exercise 18
Suppose a sequence is generated by a function $f$ of the preceding $k$ values, as in exercise 17.
Exercise 18. [**] [M20] Invent a method analogous to that of exercise 7 for finding cycles in the general form of random number generator discussed in exercise 17.
Verified: yes
Solve time: 2m03s
Suppose a sequence is generated by a function $f$ of the preceding $k$ values, as in exercise 17. Define a $k$-tuple state $S_n = (X_{n-k+1}, \dots, X_n)$ for $n \ge k-1$. Then the sequence of states $(S_0, S_1, \dots)$ is entirely determined by $f$ and the initial $k$ values. A cycle in the original sequence corresponds precisely to a cycle in the sequence of states.
We can detect cycles using a method analogous to exercise 7 by maintaining two pointers through the sequence of $k$-tuples: one advances one step at a time, the other advances two steps at a time. Formally, let $S_{\text{slow}} \leftarrow S_0$ and $S_{\text{fast}} \leftarrow S_0$. Then repeat the following replacements until $S_{\text{slow}} = S_{\text{fast}}$:
$$ \begin{aligned} S_{\text{slow}} &\leftarrow f(S_{\text{slow}}) \ S_{\text{fast}} &\leftarrow f(f(S_{\text{fast}})) \end{aligned} $$
where $f$ acts on a $k$-tuple by computing the next value and forming the updated $k$-tuple. Each iteration involves three replacements. When a collision occurs, the distance from the initial state to the start of the cycle and the cycle length can be determined as in exercise 7 by resetting one pointer to $S_0$ and advancing both pointers one step at a time until they meet. The total number of replacements required to locate the cycle and measure its length is at most $2m^k$, where $m$ is the range of each $X_n$.
This method generalizes Floyd’s cycle-finding algorithm to sequences defined by functions of $k$ previous values, requiring only $O(1)$ additional storage for the two $k$-tuples. This completes the proof.
∎