1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you read about the Janson inequalities, in the Alon Spencer? $\endgroup$ – Graffitics Feb 16 '16 at 21:04
  • $\begingroup$ No. Can you kindly give me the proper description of this reference? Thanks $\endgroup$ – Peaceful Feb 17 '16 at 16:45
  • $\begingroup$ Alon & Spencer, The probabilistic method, Chapter 8. This gives a good justification in the sparse case. $\endgroup$ – Graffitics Feb 17 '16 at 17:08
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.