Asymptotic distribution of wedges in a random graph using second moment's method

Question

I am currently reading R. Van der Hofstad's book Random Graphs and Complex networks and I need help to solve an exercice:

Let $G$ be the Erdos-Renyi random graph with edge probability $\frac{\lambda}{n}$ and $n$ vertices and $\lambda =np$. Let $W_{G}= \sum_{i,j,k\in V(G)} \mathbb{1}_{ij,jk \ occupied} $ be the random variable that counts two times the number of wedges (or connected triples) in G. Show that $\frac{W_G}{n}$ converges in probability to $\lambda²$ by using the second moment method.

I found that $\frac{\mathbb{E}(W_G)}{n}=\frac{\binom{n}3p²}{n}= \frac{1}{6}(n² + o(n))p²$ but I am not sure.

Moreover, in order to use Chebychev's Inequality, I want to estimate variance of $W_G$ and thus $\mathbb{E}(\frac{W_G²}{n²})$. I tried to to this in the following way but it doesn't look quite good:

$\mathbb{E}(\frac{W_G²}{n²})=\frac{1}{n²}\mathbb{E}((\sum_{i,j,k\in V(G)} \mathbb{1}_{ij,jk \ occupied})²)$

Using Cauchy-Schwarz I get : $\frac{1}{n²}\mathbb{E}((\sum_{i,j,k\in V(G)} \mathbb{1}_{ij,jk \ occupied})²)\leq \frac{1}{n²}\mathbb{E}((\sum_{i,j\in V(G)} \mathbb{1}²_{ij \ occupied})(\sum_{j,k\in V(G)} \mathbb{1}²_{jk \ occupied}))$

Then, assuming that $(\sum_{i,j\in V(G)} \mathbb{1}²_{ij \ occupied})$ is independent of $(\sum_{j,k\in V(G)} \mathbb{1}²_{jk \ occupied})$ (My argument for this is that each edge is occupied independently). I get :

$\frac{1}{n²}\mathbb{E}((\sum_{i,j\in V(G)} \mathbb{1}²_{ij \ occupied})(\sum_{j,k\in V(G)} \mathbb{1}²_{jk \ occupied}))=\frac{1}{n²}\mathbb{E}((\sum_{i,j\in V(G)} \mathbb{1}_{ij \ occupied}))\mathbb{E}((\sum_{j,k\in V(G)} \mathbb{1}_{jk \ occupied}))=\frac{1}{n²}(\binom{n}2p)²=(n² + o(n))p²$

What do you think of this? Is the beggining correct?

Thanks a lot.

Answer 1

Well, first of all, $\sum_{i,j\in V(G)} \boldsymbol{1}^2_{ij \text{ occupied}}$ is definitely not independent of $\sum_{j,k\in V(G)} \boldsymbol{1}^2_{jk \text{ occupied}}$: they are the same random variable! Both count the total number of edges in the random graph.

Second, and a minor thing, if we want $\mathbb E[W_G] \sim \lambda^2 n$ with the right constant, then we have to define it properly: as the number of ordered triples $(x,y,z) \in V(G)^3$ such that $x,y,z$ are distinct and $xy, yz \in E(G)$. Your calculation of $W_G$ is off by a factor of $3!$ because the definition you use does not match this one; with this definition, $$ \mathbb E[W_G] = n(n-1)(n-2)p^2 \sim n^3 p^2 = \lambda^2 n. $$

On to the second moment method. It is best to compute quantities like $W_G^2$ by thinking of them as ordered pairs of the things that $W_G$ counts. In this case, $W_G^2$ counts the number of pairs of triples $((x_1,y_1,z_1), (x_2,y_2,z_2))$ where each triple $(x_i,y_i,z_i)$ is as above.

Among these, the pairs of triples where all four edges $\{x_1y_1, y_1z_1, x_2y_2, y_2z_2\}$ are distinct contribute $(1+o(1)) \mathbb E[W_G]^2$ to $\mathbb E[W_G^2]$, because here we have independence (and because almost all pairs are of this type). This usually happens in such second moment calculations, and the contribution from these pairs will get canceled out when we subtract $\mathbb E[W_G]^2$ to compute the variance.

The non-independent cases are:

• Cases where between the two triples, we have $4$ distinct vertices and $3$ distinct edges. The contribution from these is $O(n^4 p^3) = O(n) = o(n^2)$, which in particular is $o(\mathbb E[W_G]^2)$.
• Cases where between the two triples, we have $3$ distinct vertices and $2$ distinct edges. That is, $(x_1,y_1,z_1) = (x_2,y_2,z_2)$ or $(x_1,y_1,z_1) = (z_2,y_2,x_2)$. The contribution from these is $O(\mathbb E[W_G])$ which is also $o(\mathbb E[W_G]^2)$.

It follows that $\operatorname{Var}[W_G] = \mathbb E[W_G^2] - \mathbb E[W_G]^2 = o(\mathbb E[W_G]^2)$, and so by a standard application of Chebyshev's inequality, $W_G \sim \mathbb E[W_G]$ with high probability, which was what we wanted.

---

What's at play here is a useful version of Chebyshev's inequality which is Corollary 4.3.4 in Alon and Spencer's Probabilistic Method.

Suppose that our random variable $X$ counts the number of events $A_1, A_2, \dots, A_n$ which occur, and write $i \sim j$ for the case where $i \ne j$ and events $A_i$ and $A_j$ are not independent. Define $$\Delta = \sum_{i \sim j} \Pr[A_i \land A_j].$$ Suppose that $\mathbb E[X] \to \infty$ and $\Delta = o(\mathbb E[X]^2)$ as $n \to \infty$. Then $X \sim \mathbb E[X]$ almost always.