3
$\begingroup$

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random process: Each unordered pair $\{i,j\}$ of vertices, where $i \neq j$, occurs as an edge in $E$ with probability $p$, independently of the other unordered pairs.

A triangle in $G$ is an unordered triple $\{i,j,k\}$ of distinct vertices, such that $\{i,j\}$, $\{j,k\}$, and $\{k,i\}$ are edges in $G$.

Define the random variable $X$ to be the total number of triangles in the graph $G$. Determine the expected value $E(X)$.

$\endgroup$
  • $\begingroup$ Next time please choose a more descriptive title for your question. $\endgroup$ – MJD Mar 28 '14 at 14:27
9
$\begingroup$

Set $t\stackrel{\rm def}{=}\binom{n}{3}$, fix any ordering of the $t$ possible sets of 3 nodes, and consider accordingly $X_1,\dots,X_t$ the indicator random variables where $X_j$ is equal to $1$ iff the $j$-th set defines a triangle. You are interested in $\mathbb{E}\sum_{j=1}^t X_j$, where the expectation is taken over the $\binom{n}{2}$ i.i.d. draws defining the edges.

By linearity of expectation, $$ \mathbb{E}\sum_{j=1}^t X_j = \sum_{j=1}^t \mathbb{E} X_j = t \mathbb{E} X_1 = tp^3 $$ as all $X_j$'s are identically distributed (for the second equality).

$\endgroup$
  • 4
    $\begingroup$ this approach is nice, but I may have missed something. Are the $X_i$'s really independent? For instance, if I know that $\{1,2,3\}$ define a triangle, shouldn't that increase my estimate of the probability that $\{2,3,4\}$ defines a triangle because I know that at least one of the required edges is there? I'm sure the problem is just that I'm missing something though ... $\endgroup$ – Rookatu Mar 28 '14 at 18:39
  • 4
    $\begingroup$ Sorry -- the $X_j$ are not independent, though they are identically distributed (which is what I needed for the second equality). Independence is not needed at all, the only real property used is the linearity of expectation. $\endgroup$ – Clement C. Mar 28 '14 at 18:44
  • $\begingroup$ Okay, thanks. And again, nice solution :) $\endgroup$ – Rookatu Mar 28 '14 at 18:45
  • $\begingroup$ This is really nice! I couldn't believe it could be so simple until I calculated it the long way for $n=4$ and got the same answer. $\endgroup$ – MJD Mar 28 '14 at 21:46

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.