Expected triangles among ten random collaborators

Question

Ten researchers form a collaboration network. Each pair of researchers collaborates independently with probability $\tfrac13$ . A "trio" is fully connected if all 3 of its members pairwise collaborate.

On average, how many fully connected trios are there among the 10 researchers?

Accepted Answer

Put one indicator on each group of 3 researchers, then add. There are \binom{10}{3} = 120 trios. Fix one trio. It is fully connected only if all 3 of its internal pairs collaborate. Those 3 links are independent, each present with probability 	frac13, so P(	ext{a given trio is connected}) = \left(	frac13ight)^3 = \frac{1}{27}. By linearity over all 120 trios, E[	ext{connected trios}] = \binom{10}{3}\left(	frac13ight)^3 = 120 	imes \frac{1}{27} = \frac{120}{27} = \frac{40}{9} \approx 4.444. Takeaway. The expected number of triangles in a random graph is \binom{n}{3}p^{3}. Here 120 	…

Expected triangles among ten random collaborators

Your answer

Discussion

Learn the concepts

Related questions