GATE CSE 2013 | Question: 24

Question

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

• A. $\dfrac {1}{8}$
• B. $1$
• C. $7$
• D. $8$

Comments

Whats the random variable and the sample space?

Is it no. of graph with 3 length cycle or different ways in which we can select 3 vertex out of 8 vertex in same graph?

Answer 1

Answer is (C)

A cycle of length $3$ requires $3$ vertices.

Number of ways in which we can choose $3$ vertices from $8$ = $^{8}C_{3} =56.$

Probability that $3$ vertices form a cycle $=\text{ Probability of edge between vertices 1 and 2}\times \text{ Probability of edge}$
$ \text{between vertices 2 and 3} \times \text{Probability of edge between vertices 1 and 3}$

$=\dfrac{1}{2}\times \dfrac{1}{2}\times \dfrac{1}{2} =\dfrac{1}{8}$

So, expected number of cycles of length $3 = 56\times \dfrac{1}{8} = 7$

ref@ http://stackoverflow.com/questions/14801072/number-of-cycles-in-a-random-graph

Comments

Why it cant be 8p3/8 for ordered cycles plzz tell me

---

@Arjun sir why are we not considering circular permutations of vertices here?

---

This is the detailed explanation of the expectation in binomial distribution

Answer 2

Maximum number of cycles of length 3 from 8 vertices = C(8,3) = 56.

It is a Binomial experiment as we keep on repeating the same Bernouli experiment again and again. What Bernouli experiment we keep on repeating ? We keep on checking all 56 possibilities whether there is a cycle or not. Checking is clearly a Bernouli experiment because after checking we will either find cycle (success) or no-cycle(failure).

So number of Bernouli experiments, n = 56.

Let X be a random variable which indicates number of 3-length cycles.

Expectation (X) (i.e) Expected number of 3-length cycles = n * p (since it is a Binomial distribution)

                             where n is number of Bernouli trials or experiments and p is probability of success (i.e) probability of getting a 3-length cycle in 1 Bernouli experiment. p = 1/8 as there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle.

    So Expectation (X) = n * p

                                   = 56 *  1/8

                                   = 7.

Comments

Please anyone explain " there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle."   this line.......

---

@Mantu

Let the 3 vertices are $a, b, c$

The probability of having an edge between a pair of vertices is $1/2$ (Given in Ques) and having an edge between a pair of vertices is an independent event.

$P(ab, bc, ca)  = P(ab) * P(bc) * P(ca)$

                    $= 1/2*1/2*1/2$

                    $= 1/8$

Hence, out of 8 possibilities, only one will have an edge among all three vertices.

---

i think its not binomial experiment .to be binomial all indivisual experiment have to be independent of each other like flliping one coin after another.But if two triangle already have occured then the 3^rd triangle sharing two of there edges the probaility ocurance of this event increges and they are not independent of each other.

---

perfect answer

Answer 3

Let us solve the problem using indicator random variable.

Given $8$ vertices, the total number of $3$ cycles we can have is $\binom{8}{3}$

Let $X$ be the random variable indicating the number of number of cycles we can have in a random graph.

So $0\leq X \leq \binom{8}{3}$ [Just an observation]

So at most we can have $\binom{8}{3}$ number of $3$ cycles.

Now let us order these $\binom{8}{3}$ cycles from $1$ to $\binom{8}{3}$

Let $X_i$ be the indicator random variable indicating that our graph has $i$th cycle.

i.e. $$X_i = \begin{cases} 1 \text{ if cycle $i$ is in our graph} \\ 0 \text{ otherwise}\end{cases}$$

So, $$X= \sum_{i=0}^{\binom{8}{3}} X_i$$

Taking expection on both sides,

$$E[X]= E\left[ \sum_{i=0}^{\binom{8}{3}} X_i \right]$$

using linearity of expection we have,

$$E[X]=  \sum_{i=0}^{\binom{8}{3}} E\left[X_i \right]$$

Now from the property of indicator random variable, we know

$E[X_i]=Pr\{X_i=1\}$

Now we need to find the probability that a particular cycle is included in our graph.

Now suppose $v_1,v_2,v_3$ constitutes a $3$ cycle. Then probability it shall be present in our graph is:

Pr= Probability that edge $v_1-v_2$ is present $\times$ Probability that edge $v_2-v_3$ is present $\times$ Probability that edge $v_1-v_3$ is present
=$\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}$

[Note that we consider only the $3$ required edges, and did not consider whether any other edges is present or not, because, our main concern is the cycle $v_1-v_2-v_3-v_1$ and we are concerned about its presence only. We do not care about the presence of other edges. They may be present or might not be present... But we do not care, and hence that probability is $1$...]

So,

$$E[X]=  \sum_{i=0}^{\binom{8}{3}} E\left[X_i \right] = \binom{8}{3}*\frac{1}{8}=7$$

Answer 4

Any three vertices can be chosen in 8C3 ways

and P that there are three edges together is 1/8

Just multiply them using Law of multiplicity