Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" points of G are those contained in a cycle. What do we know about the statistics of G? For instance, what is the mean number of periodic points, and how do the cycle lengths look?


By comparison, a random directed graph with all out-degrees 1 (which is to say, the graph of a random function from vertices to vertices) has on order of sqrt(N) periodic points on average.


(Motivation: the graph of a quadratic rational function f acting on P^1(F\_q) looks like this, and I'm wondering what the "expected" dynamics are.) 



Dynamics of  a random "quadratic" directed graph
Let $G$ be a directed graph on $N$ vertices such that the out-degree of each vertex is 1 and the in-degree is either 0 or $n$. Letting $N=nt$, there are $t$ vertices with in-degree $n$ and $(n-1)t$ vertices with in-degree 0. Assuming the vertices are labeled, the number of such graphs is
$$
\binom{nt}{t}\frac{(nt)!}{(n!)^t}.
$$
For $1\leq m\leq t$, the number of such graphs with a fixed $m$-cycle is
$$
\binom{nt-m}{t-m}\frac{(nt-m)!}{((n-1)!)^m(n!)^{t-m}},
$$
so the number of $m$-periodic points amongst all such graphs is
$$
m\cdot\binom{nt-m}{t-m}\frac{(nt-m)!}{((n-1)!)^m(n!)^{t-m}}\cdot\frac{(nt)!}{m(nt-m)!}=\binom{nt-m}{t-m}\frac{(nt)!}{((n-1)!)^m(n!)^{t-m}}.
$$
Summing over $1\leq m\leq t$, the average we want is
$$
\binom{nt}{t}^{-1}\sum\_{m=1}^{t}{n^m\binom{nt-m}{t-m}}=-1+\binom{nt}{t}^{-1}\sum\_{m=0}^{t}{n^m\binom{nt-m}{t-m}}.
$$
When $n=1$, the average is $t$ (since all points would be periodic). When $n=2$, as in the question, the sum is 
$$
-1+\frac{4^t}{\binom{nt}{t}}\sim-1+\sqrt{\frac{\pi}{2}}\sqrt{N},
$$
so the number of periodic points does indeed look random. When $n>2$, I haven't found the identity I need yet.


