2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Jakub Konieczny Oct 19 '13 at 14:30
  • $\begingroup$ 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)$ ? $\endgroup$ – Jakub Konieczny Oct 19 '13 at 14:32
  • $\begingroup$ @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 $\endgroup$ – dibyendu Oct 19 '13 at 15:29
  • $\begingroup$ So, in a complete graph on $4$ vertices, how many cycles of length $4$ do you count? Is it $1$, or is it $3$? $\endgroup$ – Jakub Konieczny Oct 19 '13 at 15:57
  • $\begingroup$ 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. $\endgroup$ – dibyendu Oct 19 '13 at 16:17
4
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user139226 Mar 31 '14 at 9:50
  • $\begingroup$ @jojopil: Thanks for pointing this out! Corrected. $\endgroup$ – Jakub Konieczny Mar 31 '14 at 15:38
0
$\begingroup$

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}}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.