How does a random function $f:\{1,\dotsc,N\}\rightarrow\{1,\dotsc,N\}$ look like?

Question

For every $n$, write $[n]=\{1,\dotsc,n\}$. Let $\{f_n\}_{n=1}^\infty$ be a sequence of random functions $f_n:[n]\rightarrow[n]$. By "random functions", I mean that the value of each $f_n(i)$ is chosen uniformly from $\{1,\dotsc,n\}$.

For every function $f$ from a finite set $V$ to itself, I can create a directed graph. The vertices of the graph are the elements of $V$. From each vertex $v\in V$, I have a single directed edge from $v$ to $f(v)$. This graph is made of directed cycles, and of directed trees connecting to the cycles. I can thus refer to "the cycles of $f$", and for each element $v$ of $V$, I can refer to "the cycle associated with $v$.

For each $n$, choose $x_n$ uniformly from $[n]$. Let's define several events:

1. $A_n$: "$x_n$ belongs to a cycle"
2. $B_n$: "the cycle associated with $x_n$ is of length $\Theta(\sqrt{n})$" (where the constants hidden in $\Theta$ are independent of $n$).
3. $C_n$: "the distance from $x_n$ to its associated cycle is $O(\sqrt{n})$".

I think I proved that $P(A_n)\rightarrow 0, P(B_n)\rightarrow 1, P(C_n)\rightarrow 1$.

Can you confirm that these results are indeed true?

I would also like to ask about stronger properties of these graphs:

1. Does the probabily that all cycles of $f_n$ are of length $\Theta(\sqrt{n})$ converge to $1$?
2. Does the probabilty that all vertices $[n]$ of the graph of $f_n$ are of distance $O(\sqrt{n})$ from their associated cycles converge to $1$?

Answer 1

Chapter 9 of "An Introduction to the Analysis of Algorithms, Second Edition by Sedgewick and Flajolet analyzes these properties of mappings, but in terms of averages (i.e., expected values), not probabilities. The book refers to three additional references: (1) P. Flajolet and A.M. Odlyzko, "Random Mapping Statistics," in Advances in Cryptology, J.-J. Quisquater and J. Vandewalle, eds., Lecture Notes in Computer Science No. 434, 325-354. (2) V.F. Kolchin, B.A. Sevastyanov, and V.P. Chistyakov. Random Allocations. (3) D. Foata and J. Riordan. "Mappings of ayclic and parking functions," Aequationes Mathematicae 10, 1974, 10-22.

For a random mapping of N points, the number of nodes on cycles is asymptotic to $\sqrt{\pi N}$, so most points are not members of cycles. A single cycle may be connected to by several trees. The average tree size is asymptotic to $N/3$, while the average cycle length is asymptotic to $\sqrt{\pi N/8}$. The average tail length (the number of steps taken to connect to the cycle) is asymptotic to $\sqrt{\pi N / 8}$.