2
$\begingroup$

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of unordered cycles of length $3$?

The solution is given but I find it difficult to understand. It is as follows -

There can be total $^8C_3$ ways to pick $3$ vertices from $8$. The probability that there is an edge between two vertices is $\frac{1}{2}$. So expected number of unordered cycles of length 3$ =\, ^8C_3\times(\frac{1}{2})^3 = 7$.

Why did they cube $\frac{1}{2}$?

The way I approached is that with $8$ vertices, the maximum n umber of edges possible is $^8C_2=28$, since the probability of edges occurring between a pair of vertices is $0.5$, therefore the number of edges present = $28\times0.5=14$. This was all I could do and got stuck here. How did they solve it? Probability always confuses me so a detailed explanation would be really appreciated.

$\endgroup$
  • 1
    $\begingroup$ Focus on 3 vertices $a,b,c$. They form a triangle only when their 3 possible edges $ab, ac, bc$ are present. Because all edges are picked independtly, that's $P(ab$ is an edge AND $ac$ is an edge AND $bc$ is an edge$) = P(ab$ is an edge$) \cdot P(ac$ is an edge$) \cdot P(bc$ is an edge$) = 1/2 \cdot 1/2 \cdot 1/2$. And that's actually the expected number of triangles per 3-vertices, and the proof follows from linearity of expectation. $\endgroup$ – Manuel Lafond Feb 2 '15 at 16:34
  • $\begingroup$ Please make this an answer so that people with similar doubts will know! $\endgroup$ – Siddharth Thevaril Feb 2 '15 at 16:44
  • $\begingroup$ As you wish good sir :) $\endgroup$ – Manuel Lafond Feb 2 '15 at 16:56
1
$\begingroup$

Focus on 3 vertices $a,b,c$. They form a triangle only when their 3 possible edges $ab,ac,bc$ are present. Because all edges are picked independently, that's $P(ab$ is an edge AND $ac$ is an edge AND $bc$ is an edge$)=P(ab$ is an edge$)⋅P(ac$ is an edge$)⋅P(bc$ is an edge$)=1/2⋅1/2⋅1/2$. And that's actually the expected number of triangles per 3-vertices, and the proof follows from linearity of expectation.

Let's go with the gory details :)

Denote by $T$ the number of triangles of the graph $G$, and by $V_3 = {V(G) \choose 3}$ the set of possible triplets of vertices. Finally for $\{a,b,c\} \in V_3$,let $I_{a,b,c} = 1$ if $a,b,c$ form a triangle, and zero otherwise.

Then,

$$ \mathbb{E}(T) = \mathbb{E}(\sum_{\{a,b,c\} \in V_3}I_{a,b,c}) = \sum_{\{a,b,c\} \in V_3} \mathbb{E}(I_{a,b,c}) = \sum_{\{a,b,c\} \in V_3} \frac{1}{2^3} = {|V(G)| \choose 3} \cdot \frac{1}{2^3} $$

$\endgroup$
  • $\begingroup$ Pardon me... but I have a basic question.. .What are un-ordered cycles / ordered-cycles in a graph ? $\endgroup$ – SimpleGuy Dec 1 '17 at 3:34
1
$\begingroup$

By the linearity of expectation, the expected number of triangles is ${8\choose 3}$ times the expected number of triangles on a subgraph on (any) three vertices. The expected number of triangles on that subgraph is $(1/2)^3=1/8$; either there is or there isn't -- in order to have a triangle, all three edges must be present.

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