Expectation number of cycles in a Erdős–Rényi random directed graph $G(n,p)$ Let $G \sim G(n,p)$ be a directed Erdős–Rényi random graph 
with $n$ vertices and the probability $p$ that 
there is a directed edge between any two ordered pairs of vertices. 
What is the expected number of cycles in $G$?
Is there an exact formula or an upper bound and lower bound
on the expected number of simple cycles in $G$?
 A: Let $X$ be the total number of cycles, 
$X_k$ the number of cycles of length $k$ in $G$, and
$Y_k$ the number of cycles of length $k$ in a random graph of size $k$.
Note that: 


*

*${\sf E}[X] = \sum_{k=2}^n {\sf E}[X_k]$.

*${\sf E}[X_k] = {n \choose k} {\sf E}[Y_k]$.

*${\sf E}[Y_k] = (k!/k)p^k = (k-1)!p^k$.


The last one is because a cycle of length $k$ 
is a permutation of numbers from $1$ to $k$ 
but the first vertex does not matter (a cycle does not have a first vertex).
The probability of each edge being present is $p$,
so the probability of $k$ edges being present is $p^k$.
We have:
\begin{align*}
{\sf E}[X] &= \sum_{k=2}^n E[X_k] \\ 
&= \sum_{k=2}^n {n \choose k} E[Y_k] \\
&= \sum_{k=2}^n {n \choose k} (k-1)! p^k \\
&= \sum_{k=2}^n \frac{n!}{k!(n-k)!} (k-1)! p^k \\
&= \sum_{k=2}^n \frac{n!}{(n-k)!k} p^k \\
&= \sum_{k=2}^n \frac{n\ldots (n-k+1)}{k} p^k \\
\end{align*}
For a simple lower bound 
we can drop the first half of the sum:
\begin{align*}
&\geq \sum_{k=n/2}^{n} \frac{n\ldots (n-k+1)}{k} p^k \\
&\geq \sum_{k=n/2}^{n} \frac{(n/2)^{k}}{n} p^k \\
&\geq \frac{1}{n}\sum_{k=n/2}^{n} (np/2)^{k} \\
&= \frac{(\frac{np}{2})^{n+1}-(\frac{np}{2})^{\frac{n}{2}}}{\frac{np}{2}-1}
\end{align*}
