# GATE2013-24

6.9k views

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?

1. $\dfrac {1}{8}$
2. $1$
3. $7$
4. $8$

edited

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$

[email protected] http://stackoverflow.com/questions/14801072/number-of-cycles-in-a-random-graph

edited
0
Sir , is there any significance of the term "expected" here , since I am unable to see anywhere the usage of random variable , so the question is actually just asking for the calculation of no of cycles in the graph with 8 vertices .
10
presence of an edge is given by a random variable- so expectation is important.
45
• To count the no of triangles we need to scan the entire graph taking 3 points at a time. So no of experiments = $\binom{8}{3}$
• Each such experiment result can either be a triangle (with prob p = $\frac{1}{8}$) or no triangle (with prob q = $\frac{7}{8}$ )
• So, Binomial distribution with $E$ = $\text{np}$

can we model like this ?

4

@Debashish_Deka  How are you writing in Blue color ?

7

.................. 0
@ arjun sir, i did not understand your solution.
please  correct me if i am wrong.
here the number of cycles of length three is asked on average if we take a random graph of 8  vertices.
shouldnt the random variable taken be number of cycles of length three in a graph?
0
i think number of cycles of length 3 is acting as random variable here
0

@Arjun Sir, What is the significance of word "unordered cycle" here... What would be the answer if it asked for Number of Ordered Cycles?

0

If it were ordered cycles then total possibilities out of 56 will be (123,234,...678,781,812)?

So expected number of cycles of length 3 will be 8 x $\frac{1}{8}$ = 1

0
ur method is correct but is there some term like ordered cycles in a graph ??
0
Why it cant be 8p3/8 for ordered cycles plzz tell me
0

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

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.
0
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.......
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.

## Related questions

1
3.7k views
Suppose $p$ is the number of cars per minute passing through a certain road junction between $5$ PM and $6$ PM, and $p$ has a Poisson distribution with mean $3$. What is the probability of observing fewer than $3$ cars during any given minute in this interval? $\dfrac{8}{(2e^{3})}$ $\dfrac{9}{(2e^{3})}$ $\dfrac{17}{(2e^{3})}$ $\dfrac{26}{(2e^{3})}$
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is $3$ $4$ $5$ $6$
When a coin is tossed, the probability of getting a Head is $p, 0 < p < 1$. Let $N$ be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of $N$ is $\dfrac{1}{p}$ $\dfrac{1}{(1 - p)}$ $\dfrac{1}{p^{2}}$ $\dfrac{1}{(1 - p^{2})}$
If the difference between the expectation of the square of a random variable $\left(E\left[X^2\right]\right)$ and the square of the expectation of the random variable $\left(E\left[X\right]\right)^2$ is denoted by $R$, then $R=0$ $R<0$ $R\geq 0$ $R > 0$