# What is the expected number of triangles contained in this graph?

I can't seem to understand this question and I really don't know where to start. Could someone please give an explanation as to how to go about answering this?

• A simple graph is formed randomly on the vertices $v_1,v_2,\dots,v_{20}$ in the following way: For each unordered pair of these vertices $\{v_i,v_j\}$, the edge $v_iv_j$ is in the graph with probability $1/3$ and is not in the graph with probability $2/3$.

What is the expected number of triangles contained in this graph?

• There are $\binom{20}3$ potential triangles in $20$ vertices, and each triangle has probability $(\frac13)^3$ of being realized. – bof Jun 20 '16 at 11:07
• @bof but the propability functions for the triangles are not all mutually independent (if $(1,2,3)$ is a triangle and the edges $(2,4)$ and $(3,4)$ are part of the graph, then $(2,3,4)$ has probability one) – Max Jun 20 '16 at 11:14
• @Max dependency is not bothering here. For each potential triangle create a random variable $X$ taking value $1$ if it occurs and $0$ otherwise. The sum of these rv's is the number of triangles. With linearity of expectation (also works under dependency) and symmetry we find $\binom{20}3\times\left(\frac13\right)^3$ for the expectation. – drhab Jun 20 '16 at 11:19
• @Raux maybe try induction for the number of nodes to derive a formula? (just an unelaborated idea) – Max Jun 20 '16 at 11:19
• true. (need moar characters) – Max Jun 20 '16 at 11:23

There are $\binom{20}3=1140$ potential triangles, corresponding to the $\binom{20}3$ three-element subsets of the vertex set $\{v_1,\dots,v_{20}\}.$ Define indicator variables $X_1,\dots,X_{1140},$ where $X_i=1$ if the $i^{\text{th}}$ potential triangle occurs in the random graph, and $X_i=0$ otherwise; thus $E(X_i)=(\frac13)^3=\frac1{27}.$ Then the number of triangles is $X=X_1+\cdots+X_{1140},$ and $$E(X)=E(X_1+\cdots+X_{1140})=E(X_1)+\cdots+E(X_{1140})=1140\cdot\frac1{27}=\frac{380}9.$$