GATE CS 2013 Q24 — Probability: Random Variables and Distributions

To find the expected number of unordered cycles of length three (triangles) in a random graph of $8$ vertices, we can use the linearity of expectation.

Let the number of vertices be $n = 8$.

1. Number of possible triplets: The number of ways to choose $3$ vertices out of $8$ to form a potential cycle of length three is given by: $$\binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$
2. Probability of a cycle: For any chosen triplet of vertices to form a cycle of length three, all three edges connecting these vertices must be present. Since the probability of an edge existing between any pair of vertices is $p = \frac{1}{2}$, and the existence of edges is independent, the probability that all three edges exist is: $$P(\text{cycle}) = p^3 = \left(\frac{1}{2}\right)^3 = \frac{1}{8}$$
3. Expected value: Let $X_i$ be an indicator random variable such that $X_i = 1$ if the $i$-th triplet forms a cycle, and $X_i = 0$ otherwise. The total number of cycles is $X = \sum_{i=1}^{56} X_i$.
   By linearity of expectation: $$E[X] = E\left[\sum_{i=1}^{56} X_i\right] = \sum_{i=1}^{56} E[X_i] = 56 \times P(X_i = 1)$$ $$E[X] = 56 \times \frac{1}{8} = 7$$

Thus, the expected number of unordered cycles of length three is 7.