- #1
jgens
Gold Member
- 1,593
- 50
Homework Statement
Let [itex]G[/itex] be a random graph on [itex]n[/itex] vertices:
1) What is the expected number of triangles in [itex]G[/itex]?
2) What is the variance in the number of triangles?
Homework Equations
N/A
The Attempt at a Solution
I think I can do (1) by using indicator variables. In particular, let [itex]X[/itex] denote the number of triangles in [itex]G[/itex], suppose [itex]\theta_{ijk}[/itex] is the indicator variable that the triple of vertices [itex]i,j,k[/itex] make a triangle, and let [itex]A_{ijk}[/itex] denote the event that the triple of vertices make a triangle. Then, we know
[tex]E(X) = \sum_{i,j,k}P(A_{ijk})[/tex]
where the sum extends over all triples [itex]i,j,k[/itex]. Since there are [itex]\binom{n}{3}[/itex] such triples and since [itex]P(A_{ijk}) = \frac{1}{8}[/itex], this means
[tex]E(X) = \binom{n}{3}\frac{1}{8}[/tex]
which gives us the expected number of triangles.
Now, I just need help getting started with the variance problem. I think I'm just supposed to utilize the fact that [itex]Var(X) = E(X^2) - E(X)^2[/itex], but I'm not sure. Any help is appreciated.