Expected number of triangles in a random graph of size $n$

14.6k Views Asked by At

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)$.

1

There are 1 best solutions below

4
On

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).