Expected triangles in a random friendship network

Question

Six people attend a mixer. Each of the possible pairs becomes friends independently with probability $\tfrac12$ . A "triangle" is a set of 3 people who are all mutually friends.

On average, how many mutual-friend triangles form among the 6 people?

Accepted Answer

Do not try to count triangles by cases. Put one indicator on each possible triangle (each group of 3 people) and add. There are \binom{6}{3} = 20 groups of 3 people. Fix one such group. It is a triangle only if all 3 of its internal pairs are friends. Those 3 pairs are independent, each present with probability 	frac12, so P(	ext{a given trio is a triangle}) = \left(	frac12ight)^3 = \frac18. Let XT = 1 if trio T is a triangle; E[XT] = 	frac18. Summing over all 20 trios, E[	ext{triangles}] = \binom{6}{3}\left(	frac12ight)^3 = 20 	imes \frac18 = \frac{20}{8} = \frac52 = 2.5. Takeaway…

Expected triangles in a random friendship network

Your answer

Discussion

Learn the concepts

Related questions