So I know how to correctly calculate the expected number of triangles in the Erdos-Renyi graph using linearity of the expectation value operator (See this for example). However, now consider a "wrong" derivation of the same thing as follows:
Let $t = \ ^{n}C_{3}$ which is simply a number of all possible triples in the graph of size $n$. The probability of a given triple forming a triangle is $p^{3}$. Therefore the probability that there are exactly $k$ triangles in the graph is $^{t}C_{k}p^{3k}(1-p^{3})^{t-k}$. Thus, the expected number of triangles is:
$$ T_{e} = \sum\limits_{k=0}^{t}\ k ^{t}C_{k}p^{3k}(1-p^{3})^{t-k} = ^{t}C_{k}p^{3} $$
This is actually the correct answer even though this derivation doesn't consider the statistical dependence of the triangles in the network! Then how come this wrong argument actually produces the right answer?
Thanks in advance.
Best Answer
The answer is the same because the probability for each triangle to be counted is the same – by linearity of expectation these probabilities are all that matters. You can think of your "wrong" calculation as calculating the expected number of triangles for a fictitious graph consisting of $\binom n3$ unconnected triangles, with each triangle being formed independently with the same probability with which the actual triangles are formed.