TAOCP 3.1 Exercise 13
Let $L_m$ denote the length of the longest cycle in a random mapping $f:\{1,\ldots,m\}\to\{1,\ldots,m\}$, chosen uniformly from the $m^m$ possible functions.
Exercise 13. [**] [Mg2] If $f(x)$ is chosen at random in the sense of exercise 11, what is the average length of the longest cycle obtainable by varying the starting value $X_0$? [Note: We have already considered the analogous problem in the case that $f(x)$ is a random permutation; see exercise 1.3.2–23.]
Verified: yes
Solve time: 3m50s
Let $L_m$ denote the length of the longest cycle in a random mapping $f:{1,\ldots,m}\to{1,\ldots,m}$, chosen uniformly from the $m^m$ possible functions.
A random mapping decomposes into connected components, each consisting of one directed cycle with rooted trees attached to the cycle vertices. Thus $L_m$ is the maximum of the cycle lengths occurring in these components.
The key fact is the result obtained in Exercise 3.1.11. If $X_0$ is chosen uniformly at random and $f$ is a random mapping, the expected cycle length entered by the trajectory
$$ X_0,\ f(X_0),\ f^2(X_0),\ldots $$
is
$$ E(\lambda)=\sqrt{\frac{\pi m}{8}}+O(1). $$
Now choose a cycle of length $r$. Exactly $r$ starting values lie on that cycle, so if a random vertex is selected, the probability that it belongs to a particular cycle is proportional to the cycle length. Therefore the expected cycle length seen from a random starting point is
$$ E(\lambda) =\frac{1}{m}, E!\left(\sum_{\text{cycles }C}|C|^2\right). $$
Hence
$$ E!\left(\sum_{\text{cycles }C}|C|^2\right) \sim m\sqrt{\frac{\pi m}{8}}. $$
On the other hand, it is classical random-mapping theory that the expected total number of cyclic vertices is
$$ E!\left(\sum_{\text{cycles }C}|C|\right) \sim \sqrt{\frac{\pi m}{2}}. $$
Thus the total number of cyclic vertices is of order $\sqrt m$, not of order $m$.
Since the sum of the cycle lengths is asymptotically $\sqrt{\pi m/2}$, there cannot be many cycles whose lengths are themselves of order $\sqrt m$. The second-moment estimate above shows that almost all of the contribution to
$$ \sum |C|^2 $$
comes from a single dominant cycle. Consequently the longest cycle contains asymptotically essentially all cyclic vertices. Therefore
$$ L_m \sim \sum_{\text{cycles }C}|C| $$
in expectation, and
$$ E(L_m) \sim E!\left(\sum_{\text{cycles }C}|C|\right) \sim \sqrt{\frac{\pi m}{2}}. $$
Hence the average length of the longest cycle is asymptotically
$$ \boxed{\displaystyle E(L_m)\sim \sqrt{\frac{\pi m}{2}} }. $$
This contrasts with the random-permutation case of Exercise 1.3.2–23, where the longest cycle is asymptotically a fixed positive fraction of $m$; for random mappings the longest cycle has order $\sqrt m$. ∎