# Expected number of simple, unordered cycles in a random graph

Consider an undirected random graph of $n$ vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of simple (no vertex more than once), unordered cycles of length $k$ with $k\leq n$ ?

The approach that I took was as follows.

Let $X$ be the random variable denoting the number of undirected cycles of length $k$. Clearly $X$ can takes values from $\left\{0,1,2,\ldots,{\dbinom{n}{k}}\right\}$. We need to find $\mathbf E(X)$.

Since $X$ is a discrete random variable, by definition we have:$$\mathbf E(X)=\sum_{x\in X}x\cdot \Pr(X=x)=\sum_{i=0}^{\binom{n} k}i\cdot \Pr(X=i)$$ where, $\Pr(X=i)$ is the probability of number of simple, undirected cycles of length $k$ being $i$.

And here is where I'm stuck. Can anyone help me finding a convenient way of computing $\Pr(X=i)$.

• I would be sufficient to solve the problem when $n=k$, and for the general case sum over all possible choices of $k$ vertices (using additivity of $E(\cdot)$. – Jakub Konieczny Oct 19 '13 at 14:30
• Do I correctly understand that you count cycles only depending on the set of vertices? For instance, are these cycles the same: $(1,2,3,4)$ and $(1,3,2,4)$ ? – Jakub Konieczny Oct 19 '13 at 14:32
• @Feanor, $(1,2,3,4)$ and $(1,3,2,4)$ are not same, as $(1,2,3,4)$ doesn't require an edge between $1,3$ whereas $(1,3,2,4)$ does – dibyendu Oct 19 '13 at 15:29
• So, in a complete graph on $4$ vertices, how many cycles of length $4$ do you count? Is it $1$, or is it $3$? – Jakub Konieczny Oct 19 '13 at 15:57
• If we consider the complete graph with $4$ vertices as a rectangle $ABCD$ with both the diagonal existing, then it'll have $2$ cycles of length $4$. Which are $(A,B,C,D)$ and $(A,C,B,D)$. No other unique cycle could be drawn since these $2$ would exhaust all the edges. – dibyendu Oct 19 '13 at 16:17

Let $\{C_t\}_{t=1}^T$ enumerate all cycles of length $k$ in the $n$ vertices, let $G$ be the random graph under consideration, and let $Y_t = 1$ if $C_t \subset G$ and $Y_t = 0$ if $C_t \not \subset G$ (where by $C_t \subset G$ I mean that $G$ has all the edges that appear in $C_t$). If $X$ is the total number of cycles in $G$, then: $$X = \sum_{t=1}^T Y_t.$$ Now, you can act on this with the expected value, and use additivity (note: $\mathbb{E}(Y+Z) = \mathbb{E}(Y) + \mathbb{E}(Z)$ for any random variables $Y,Z$, not necessarily independent in any way): $$\mathbb{E}(X) = \mathbb{E}\left( \sum_{t=1}^T Y_t\right) = \sum_{t=1}^T \mathbb{E}\left(Y_t\right) = \sum_{t=1}^T \mathbb{P}(C_t \subset G) .$$ For any $t$, the cycle $C_t$ has $k$ edges, and the probability that all these $k$ edges are chosen is just $\frac{1}{2^k}$. Hence, we get: $$\mathbb{E}(X) = \frac{T}{2^k} .$$ It remains to compute $T$, i.e. the number of different cycles. Let us fix a vertex $v_0$ (this can be chosen in $n$ ways), and see how many different cycles we can find starting with $v_0$. The second vertex on the cycle $v_1$ can be chosen in $n-1$ ways, $v_2$ can be chosen in $n-2$ ways, and so on, until the vertex $v_{k-1}$ which can be chosen in $n-k+1$ ways. This results in the total of $n(n-1)(n-2)(n-3)\dots (n-k+1) = n^{\underline{k}}$ ways.

However, we count some of the cycles several times. Firstly, we distinguished the starting point $v_0$, which for a given cycle can be chosen in $k$ ways. Secondly, we distinguished an orientation, which for a given cycle can be chosen in two ways. Hence, each cycle is counted $2k$ times, and $T = n^{\underline{k}}/2k$.

Finally, we find: $$\mathbb{E}(X) = \frac{n^{\underline{k}}}{2^{k+1}k}.$$

• There are slight errors in the above. You fix v0 but you have n choices. Also you could have start from v1 or v2 or ... vk. Thus T = n(n-1)...(n-k+1)/2/k. Another way to prove it is: - you have binomial(n,k) ways to choose the k vertices - and (k-1)!/2 ways to label the k-cycle - each edge of the cycle exists with probability 1/2 In total you find the same result – user139226 Mar 31 '14 at 9:50
• @jojopil: Thanks for pointing this out! Corrected. – Jakub Konieczny Mar 31 '14 at 15:38

A probably simpler way to obtain the above result (as explained in comment by user139226).

Let $X$ be the random variable denoting the number of undirected cycles of length $k$. Let $X_{\left\{ V_i \right\}_{i = 1}^{k}}$ be the indicator random variable that the subset of verticies $\left\{ V_i \right\}_{i = 1}^{k}$ is a cycle of length $k$.

If $p \in [0, 1]$ is the probability that there is an edge between a pair of vertices (in this case $p = \frac{1}{2}$), then $P(\left\{ V_i \right\}_{i = 1}^{k} = 1) = p^k$. Now:

$$E[X] = \frac{1}{2k} \sum_{\left\{ V_i \right\}_{i = 1}^{k} \in V} E[X_{\left\{ V_i \right\}_{i = 1}^{k}}]$$

where the term $\frac{1}{2k}$ comes from the fact that each undirected cycle is counted 2 times because of orientation and $k$ times because of the choice of starting vertex.

Because $X_{\left\{ V_i \right\}_{i = 1}^{k}}$ is an indicator variable $E[X_{\left\{ V_i \right\}_{i = 1}^{k}}] = P(\left\{ V_i \right\}_{i = 1}^{k} = 1) = p^k$, so:.

$$E[X] = \frac{1}{2k} \sum_{\left\{ V_i \right\}_{i = 1}^{k} \in V} p^k = \frac{p^k}{2k} \sum_{\left\{ V_i \right\}_{i = 1}^{k} \in V} 1$$

We compute the different ways of choosing $k$ vertices of $n$ available (${n \choose k}$) and the different ways of ordering them ($k!$):

$$E[X] = \frac{p^k}{2k} {n \choose k} k!$$

simplify this expression given that $k! = k\times k-1 \times ... 1$ to:

$$E[X] = {n \choose k} \frac{(k - 1)!}{2}p^k.$$

Finally we substitute $p = \frac{1}{2}$ as specified for this problem and obtain:

$$E[X] = {n \choose k} \frac{(k - 1)!}{2^{k + 1}}.$$