Expected mutual-follow triangles among seven users

Question

Seven users join a small social app. Each pair of users becomes mutually connected independently with probability $0.2$ . A triangle is a set of 3 users who are all mutually connected.

On average, how many triangles form among the 7 users?

Accepted Answer

Give each group of 3 users an indicator and add them up. There are \binom{7}{3} = 35 trios. Fix one trio. It is a triangle only if all 3 internal connections exist. These are independent, each with probability 0.2 = 	frac15, so P(	ext{a given trio is a triangle}) = (0.2)^3 = \frac{1}{125}. By linearity over all 35 trios, E[	ext{triangles}] = \binom{7}{3}(0.2)^3 = 35 	imes \frac{1}{125} = \frac{35}{125} = \frac{7}{25} = 0.28. Takeaway. Even with a sparse graph, the expected triangle count is just \binom{n}{3}p^{3}. Here 35 	imes (1/5)^3 = 	frac{7}{25}, so on average well under one triang…

Expected mutual-follow triangles among seven users

Your answer

Discussion

Learn the concepts

Related questions