Good afternoon. In one book on probability theory I came across this problem which I found myself difficult to understand and prove. Would appreciate any help on that:
Let $X_n$ be the number of complete subgraphs on 4 vertices in $G(n,\frac{1}{2})$. Prove that $\frac{X_n-E(X_n)}{E(X_n)} \xrightarrow{P} 0$
Let $Z_n=(X_n-\mathsf{E}X_n)/\mathsf{E}X_n$. Then for each $\epsilon>0$, $$ \mathsf{P}(|Z_n|\ge \epsilon)\le \epsilon^{-2}\operatorname{Var}(Z_n)=\frac{\operatorname{Var}(X_n)}{\epsilon^2(\mathsf{E}X_n)^2}. $$ It suffices to show that the last term converges to $0$ as $n\to\infty$.
First, since the probability that a given set of $r$ nodes is a complete subgraph is $p^{\binom{r}{2}}$ (where $p$ denotes the connectivity parameter; $p=1/2$ in your case), $$ \mathsf{E}X_n=\binom{n}{r}p^{\binom{r}{2}}. $$ Second, since one can choose $\binom{n}{r}\binom{r}{i}\binom{n-r}{r-i}$ ordered pairs of sets of $r$ nodes with $i$ nodes in common, $$ \mathsf{E}X_n^2=\sum_{i=0}^r\binom{n}{r}\binom{r}{i}\binom{n-r}{r-i}p^{2\binom{r}{2}-\binom{i}{2}} $$ because the probability of two complete subgraphs of $r$ nodes with $i$ nodes in common is $p^{2\binom{r}{2}-\binom{i}{2}}$ (we assume that $n\ge 2r$).
Finally, it is easy to show that $$ \frac{\operatorname{Var}(X_n)}{(\mathsf{E}X_n)^2}=\binom{n}{r}^{-1}\sum_{i=2}^r\binom{r}{i}\binom{n-r}{r-i}\left(p^{-\binom{i}{2}}-1\right). $$
Plugging $r=4$ and $p=1/2$, we get $$ \frac{\operatorname{Var}(X_n)}{(\mathsf{E}X_n)^2}=\left(6\binom{n-4}{2}+28n-49\right)\binom{n}{4}^{-1}\to 0 $$ as $n\to\infty$.