# 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$?

• Hi @Anders. Welcome! You might like to use MathJax in future :) – Shaun Mar 25 '14 at 20:11

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*}

• What is n? DId you mean to say a random graph of n nodes? – Joel Aug 1 '16 at 20:25
• $n$ is the number of vertices. The OP defines the model. – D Poole Aug 2 '16 at 12:44
• I should have said a bit more: What does "in a random graph of size k" mean - did you mean "of n nodes"? – Joel Aug 3 '16 at 8:09
• By symmetry, I reduce the question of the expected number of cycles in $D(n,p)$ to the expected number of cycles in $D(k,p)$ (we are looking at directed graphs here, so I use $D(n,p)$ instead of $G(n,p)$), In particular, $$E[\# \text{ of cycles in }D(n,p) \text{ of length }k] = {n \choose k}E[\# \text{ of cycles in }D(k,p)\text{ of length }k]$$ – D Poole Aug 3 '16 at 12:08