TAOCP 3.1 Exercise 19
Let $Y_n=(X_n,X_{n-1},\ldots,X_{n-k+1}).$ Then $Y_n$ ranges over the $m^k$ possible $k$-tuples, and the recurrence $X_{n+1}=f(X_n,\ldots,X_{n-k+1})$ induces a function $Y_{n+1}=F(Y_n)$
Exercise 19. [**] [HM47] Solve the problems of exercises 11 through 15 asymptotically for the more general case that $X_{n+1}$ depends on the preceding $k$ values of the sequence; each of the $m^m$ functions $f(x_1, \ldots, x_k)$ is to be considered equally probable. [Note: The number of functions that yield the maximum period is analyzed in exercise 2.3.4.2–23.]
Verified: yes
Solve time: 1m18s
Let
$Y_n=(X_n,X_{n-1},\ldots,X_{n-k+1}).$
Then $Y_n$ ranges over the $m^k$ possible $k$-tuples, and the recurrence
$X_{n+1}=f(X_n,\ldots,X_{n-k+1})$
induces a function
$Y_{n+1}=F(Y_n)$
on a set of size
$N=m^k.$
When each value of $f$ is chosen independently and uniformly from ${0,\ldots,m-1}$, the induced mapping $F$ is asymptotically a random mapping on $N$ states. Therefore all asymptotic results of Exercises 11 through 15 remain valid after replacing $m$ by $N=m^k$.
In particular, the expected value of $\rho=\mu+\lambda$ is
=\sqrt{\frac{\pi}{2}},m^{k/2},$$ the expected tail length and cycle length are $$E(\mu)\sim E(\lambda)\sim \sqrt{\frac{\pi N}{8}} =\sqrt{\frac{\pi}{8}},m^{k/2},$$ the probability that a given state lies on a cycle is asymptotic to $$\sqrt{\frac{\pi}{2N}} =\sqrt{\frac{\pi}{2}},m^{-k/2},$$ the expected number of cyclic states is $$\sqrt{\frac{\pi N}{2}} =\sqrt{\frac{\pi}{2}},m^{k/2},$$ and the expected number of distinct cycles is $$\frac12\log N+O(1) =\frac{k}{2}\log m+O(1).$$Thus every asymptotic formula obtained in Exercises 11 through 15 is obtained by the substitution $m\mapsto m^k$. ∎