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

Understand the number of potential 3-cycles

To form a cycle of length three, we must choose exactly 3 vertices from the total 8 vertices in the graph.

The number of ways to choose 3 vertices out of 8 is calculated using combinations

$$\binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$

So, there are exactly $56$ possible unordered cycles of length three in an 8-vertex graph.
 

Define the Indicator Random Variables

Let $X$ be the random variable representing the total number of unordered cycles of length three. We can express $X$ as the sum of 56 indicator random variables, one for each potential cycle

$$X = X_1 + X_2 + \dots + X_{56}$$

Where for each $i$ from 1 to 56

• $X_i = 1$, if the $i$-th potential cycle actually exists in the random graph.

• $X_i = 0$, otherwise.

 

Find the Expectation of a single $X_i$

$$E[X_i] = (1 \cdot P(X_i = 1)) + (0 \cdot P(X_i = 0))$$

$$E[X_i] = P(X_i = 1)$$

For a specific set of 3 vertices to form a cycle, all three edges connecting them must exist. Since the probability of any single edge existing is $\frac{1}{2}$ and the edges are independent, the probability that all three specific edges exist is

$$P(X_i = 1) = \left(\frac{1}{2}\right) \times \left(\frac{1}{2}\right) \times \left(\frac{1}{2}\right) = \left(\frac{1}{2}\right)^3 = \frac{1}{8}$$

Therefore, $E[X_i] = \frac{1}{8}$.

 

Apply Linearity of Expectation

By the linearity of expectation, the expected value of the sum is the sum of the expected values

$$E[X] = E[X_1 + X_2 + \dots + X_{56}]$$

$$E[X] = E[X_1] + E[X_2] + \dots + E[X_{56}]$$

Since all 56 potential cycles have the same probability of occurring

$$E[X] = 56 \times E[X_i]$$

$$E[X] = 56 \times \frac{1}{8}$$

$$E[X] = 7$$

Answer is C

---

General formula for k length cycles:

$$
\binom{n}{k}\frac{(k-1)!}{2}\left(\frac{1}{2}\right)^k
$$

---

Great answer

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

Then you have to check  1-2 ,2-3, 3-4, 4-1 if this type of edge exits or not.

1-2 =2-3=3-4=4-1 each with 0.5 probability.

and choose 4 vertices from 8 vertices (8Choose4).

---

but we also have to make sure that there is no edge between 1-3 and 2-4 right?

 

---

I think that's not matter just we have to check that it create a cycle with 4 node or not.

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

perfect answer

---

Great Explanation bro 👏

---

No this is not correct: The random variable $X $ defined as:  $X = \text{Number of unordered cycles of length 3.}$. The distribution of $X$ is not binomial distribution. Because of binomial distribution you need independent bernoulli trails, here each trail is "whether a set of 3 vertices forms a cycle or not".

Define $$I_{ijk} =\begin{cases}1, & \text{If vertices }\set{i, j, n} \text{ form a cycle of length 3 } \\ 0, & \text{o/w}\end{cases}$$

$$E_{i, j} = \begin{cases}1, & \text{If there edge between i and j } \\ 0, & \text{o/w}\end{cases}$$

Then $X = \displaystyle\sum_{i< j <k} I_{ijk}$. Now For each of these indicator random variables, $P(I_{ijk} = 1) = P(E_{ij} = 1)P(E_{jk} = 1)P(E_{ik} = 1) = \dfrac{1}{8}$

But $P(I_{123}  = 1| I_{124} = 1 ,  I_{234} = 1) = 1$, from this we can conclude that trials are not independent, so the distribution of $X$ is not an binomial distribution.

 

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

Answer 5

for creating a triangle  we need 3 vertices we have n vertices choose one in nc1 ways .as the probability of edge on that vertex is 1/2, so 1/2* nc1.

again from remaining n-1 vertices choose one with probability  1/2 i.e 1/2*n-1c1 .again from n-2 choose one i.e 1/2*1/2*1/2*n*(n-1)*(n-2) now divide it with 3! as it is unordered graph.

i.e 1/2*1/2*1/2*n*(n-1)*(n-2)/3!  put n=8 you get your answer.

Answer 6

Random Variable X =  Number of unordered cycles of length three

Asked (E(X))

We can have X=0,1,2,3,4 also, why are we considering only one triangle?