Expected triangles among eight coin-flip links

Question

Eight nodes sit in a network. For each pair of nodes you flip a fair coin: heads draws a link between them, tails leaves them unlinked. A triangle is a set of 3 nodes that are all pairwise linked.

On average, how many triangles appear among the 8 nodes?

Accepted Answer

Put one indicator on each group of 3 nodes and add. There are \binom{8}{3} = 56 trios. Fix one trio. It is a triangle only if all 3 of its internal links came up heads. The 3 coin flips are independent, each heads with probability 	frac12, so P(	ext{a given trio is a triangle}) = \left(	frac12ight)^3 = \frac18. By linearity over all 56 trios, E[	ext{triangles}] = \binom{8}{3}\left(	frac12ight)^3 = 56 	imes \frac18 = 7. Takeaway. Expected triangles equal \binom{n}{3}p^{3}. At p=	frac12 this is \binom{n}{3}/8, which for n=8 gives exactly 7. One indicator per trio plus linearity does …

Expected triangles among eight coin-flip links

Your answer

Discussion

Learn the concepts

Related questions