edited by
19,663 views
61 votes
61 votes

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 by

6 Answers

Best answer
119 votes
119 votes

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

edited by
32 votes
32 votes
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.
4 votes
4 votes
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$$
edited by
3 votes
3 votes

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:

Related questions

36 votes
36 votes
7 answers
2
go_editor asked Sep 29, 2014
8,811 views
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 $\l...
61 votes
61 votes
3 answers
3
Arjun asked Sep 26, 2014
17,275 views
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .