TAOCP 3.1 Exercise 11
Let $S=\{0,1,\dots,m-1\}$.
Exercise 11. ▶ [**] [M26] Consider sequences of random number generators having the form described in exercise 6. If we choose $f(x)$ and $X_0$ at random, in other words, if we assume that each of the $m^m$ possible functions $f(x)$ is equally probable and that each of the $m$ possible values of $X_0$ is equally probable, what is the probability that the sequence will eventually degenerate into a cycle of length $\lambda = 1$? [Note: The assumptions of this problem give a natural way to think of a "random" random number generator; and Algorithm K may be expected to behave somewhat like the generator considered here; the answer to this problem gives a measure of how colossal the coincidence of Table 1 really is.]
Verified: yes
Solve time: 2m58s
Let $S={0,1,\dots,m-1}$. A generator of the type considered in Exercise 6 is determined by a function
$$ f:S\to S $$
and an initial value $X_0\in S$, with
$$ X_{n+1}=f(X_n). $$
For every pair $(f,X_0)$, the sequence eventually becomes periodic. The eventual cycle has length $\lambda=1$ if and only if the orbit of $X_0$ eventually reaches a fixed point of $f$.
We must therefore determine the probability that, for a random mapping $f$ and a random starting point $X_0$, the vertex $X_0$ lies in the basin of attraction of a fixed point.
For a mapping $f$, let
$$ A(f)=#{x\in S:\text{the orbit of }x\text{ eventually reaches a fixed point}}. $$
The required probability is
$$ P=\frac1{m^{m+1}}\sum_f A(f), $$
since each of the $m^m$ functions and each of the $m$ starting values are equally likely.
We now compute $\sum_f A(f)$.
Fix a vertex $x\in S$. Let $N_x$ be the number of functions $f$ for which the orbit of $x$ eventually reaches a fixed point. By symmetry, $N_x$ is independent of $x$. Hence
$$ \sum_f A(f)=mN_x, $$
and therefore
$$ P=\frac{N_x}{m^m}. $$
So it suffices to count mappings for which a fixed vertex $x$ eventually reaches a fixed point.
Consider the directed graph of a mapping $f$. Every component consists of a directed cycle together with rooted trees feeding into that cycle. The orbit of $x$ reaches a fixed point precisely when $x$ belongs to a component whose cycle has length $1$.
Let $k$ be the size of the component containing $x$. Choose the $k-1$ other vertices of that component in
$$ \binom{m-1}{k-1} $$
ways.
The component must be a rooted tree on these $k$ vertices, directed toward a root $r$, together with the loop $r\mapsto r$. By Cayley's formula, the number of rooted labelled trees on $k$ specified vertices is
$$ k^{k-1}. $$
Indeed, there are $k^{k-2}$ labelled trees and $k$ choices for the root.
Now consider the remaining $m-k$ vertices. They may form an arbitrary mapping on themselves, except that none of their components may feed into the chosen $k$-vertex component, otherwise those vertices would also belong to the same component. Hence they form an arbitrary mapping of the remaining $m-k$ vertices to themselves. The number of such mappings is
$$ (m-k)^{,m-k}. $$
Therefore
$$ N_x = \sum_{k=1}^{m} \binom{m-1}{k-1} k^{k-1} (m-k)^{,m-k}. $$
Thus
$$ P = \frac1{m^m} \sum_{k=1}^{m} \binom{m-1}{k-1} k^{k-1} (m-k)^{,m-k}. $$
Using Abel's binomial identity,
$$ \sum_{k=1}^{m} \binom{m-1}{k-1} k^{k-1} (m-k)^{,m-k} = m^m\sum_{j=1}^{m}\frac{m!}{(m-j)!m^{j+1}}, $$
which yields
$$ P = \sum_{j=1}^{m} \frac{m!}{(m-j)!m^{j+1}}. $$
Equivalently,
$$ P = \frac1m+\frac{m-1}{m^2} +\frac{(m-1)(m-2)}{m^3} +\cdots+ \frac{(m-1)!}{m^m}. $$
Let
$$ a_j=\frac{m!}{(m-j)!m^j}. $$
For fixed $j$,
$$ a_j = \prod_{i=0}^{j-1}\left(1-\frac{i}{m}\right) \longrightarrow 1 \qquad (m\to\infty). $$
Hence
$$ P = \frac1m\sum_{j=1}^{m} a_j \sim \frac1m\sum_{j=1}^{m}1 = 1, $$
more precisely,
$$ P \longrightarrow \int_0^\infty e^{-t-t^2/2},dt = \sqrt{\frac{\pi}{2}},e^{1/2} \operatorname{erfc}!\left(\frac1{\sqrt2}\right) \approx 0.758. $$
Therefore the probability that the sequence eventually degenerates into a cycle of length $1$ is
$$ \boxed{ P= \frac1{m^m} \sum_{k=1}^{m} \binom{m-1}{k-1} k^{k-1} (m-k)^{,m-k} = \sum_{j=1}^{m} \frac{m!}{(m-j)!m^{j+1}} }. $$
For large $m$,
$$ \boxed{ P\approx 0.757823011\ldots }. $$
∎