Number of triangles in Erdös-Renyi graph

Question

For each ${n}$, let ${(V_n,E_n)}$ be an Erdös-Renyi graph on ${n}$ vertices with parameter ${1/2}$ (we do not require the graphs to be independent of each other). If ${|T_n|}$ is the number of triangles in ${(V_n,E_n)}$, (i.e. the set of unordered triples ${\{i,j,k\}}$ in ${V_n}$ such that ${\{i,j\}, \{i,k\}, \{j,k\} \in E_n}$), show in fact that ${|T_n|/\binom{n}{3}}$ converges almost surely to ${1/8}$. (Note: in contrast with the situation with the strong law of large numbers, the fourth moment does not need to be computed here.)

Attempt: Using the second moment method, one can obtain the bound

$$\displaystyle {\bf P}\left(\left|\frac{|T_n|}{\binom{n}{3}} - 1/8\right| \geq \varepsilon\right) \leq O\left(\frac{1}{n^2}\right)/{\varepsilon}^2$$ for any natural number $n$ and any $\varepsilon > 0$,

so $|\frac{|T_n|}{\binom{n}{3}} \to 1/8$ in probability. As the RHS is also summable in $n$, we may apply the Borel-Cantelli lemma to establish the claim. Is there any other way to do this or is this a valid approach?

Answer 1

Let $\{\tau_{i}\}$ for $i=1,2,...\binom{n}{3}$ be the enumeration of triangles.

Then $T_{n}=\sum_{i}\mathbf{1}_{\tau_{i}}$ where $\mathbf{1}_{\tau_{i}}$ is the indicator of the event that the triangle $\tau_{i}$ is in the Erdos Renyi Graph.

Then you have $$E(T_{n}^{2})=\sum_{i}\mathbf{1}_{\tau_{i}}+\sum_{i\neq j}\mathbf{1}_{\tau_{i}}\mathbf{1}_{\tau_{j}}$$

Now, suppose $\tau_{i}$ and $\tau_{j}$ where $i\neq j$ are both the graph. Then, they either they share no vertices in common or they share one vertex in common or they share two vertices in common.

In the first case, you have $\binom{n}{3}\binom{n-3}{3}$ many such possible triangles each of which is present with probability $\dfrac{1}{2^{6}}$.

In case they share one vertex, then the possible number of triangles is $n\cdot\binom{n-1}{2}\binom{n-3}{2}$, i.e. you choose the vertex which is common in $n$ ways and then chose the each of the two vertices in $\binom{n-1}{2}\binom{n-3}{2}$ ways. Each such triangle will be there with probability $\frac{1}{2^{6}}$, each $\frac{1}{2}$ being multiplied for the $6$ edges.

If they have two vertices in common, then the number of such triangles is $\binom{n}{2}(n-1)(n-2)$ ways and each triangle is present with probability $\frac{1}{2^{5}}$, $\frac{1}{2}$ being multiplied for each of the five edges.

Here is another way to calculate as I did above. Also see Theorem 3.5 here in these notes.

Thus, you have

\begin{align}E(T_{n}^{2})&=\frac{1}{2^{3}}\binom{n}{3}+\binom{n}{3}\binom{n-3}{3}\frac{1}{2^{6}}\\\\&+n\cdot\binom{n-1}{2}\binom{n-3}{2}\frac{1}{2^{6}}+\binom{n}{2}(n-1)(n-2)\frac{1}{2^{5}}\end{align}

And the Variance will be $E(T_{n}^{2})-(E(T_{n}))^{2}$ which is just the above expression minus $\bigg(\binom{n}{3}\frac{1}{2^{3}}\bigg)^{2}$

Now it is easy to see that as $n\to\infty$, we have $$\binom{n}{3}\binom{n-3}{3}\frac{1}{2^{6}}-\binom{n}{3}^{2}\frac{1}{2^{6}}\to 0$$

and hence, $Var(T_{n})=O(n^{5})$

So you have

\begin{align}P(\bigg|\frac{T_{n}}{\binom{n}{3}}-\frac{1}{2^{3}}\bigg|>\epsilon)&=P(|T_{n}-E(T_{n})|>\binom{n}{3}\epsilon)\\\\&\leq \frac{Var(T_{n})}{\epsilon^{2}(\binom{n}{3})^{2}}=\frac{O(n^{5})}{\epsilon^{2}n^{6}}\to 0\end{align}

The same proof shows you that $\dfrac{T_{n}}{\binom{n}{3}}\xrightarrow{L^{2}}\dfrac{1}{2^{3}}$ as you have

$$E\bigg(\bigg|\dfrac{T_{n}}{\binom{n}{3}}-\dfrac{1}{2^{3}}\bigg|^{2}\bigg)=\frac{Var(T_{n})}{(\binom{n}{3})^{2}}=O(\frac{1}{n})$$

Thus you have $L^{2}$ convergence and convergence in Probability but I don't see an easy way to prove almost sure convergence but you do have almost sure convergence along a subsequene. The main issue is that $T_{n}$ is not a deterministically, almost surely increasing random variable but rahter is stochastically increasing. One way is to compute the fourth moment as the blog by Terry Tao suggests but it is cumbersome.

Lastly, as I said in the comments the Second Moment Method is used to prove that P(X>0) is positive. Applying Chebycheff gives you the form you are using which is weaker than the Paley-Zygmund inequality which is taken to be the second moment method. In any case, it is not for proving something goes to 0 but rather it is for proving something is non-zero with positive probability.The form that you are using is derived in the following way:-

Let $X$ be a postive random variable. Then $P(X=0)=P(X-E(X)=-E(X))\leq P(|X-E(X)|\leq E(X))\leq \frac{Var(X)}{E(X)^{2}}$. And hence, if the RHS is small, then $P(X=0)$ is small and hence $P(X>0)$ is large.

Answer 2

Define the random variables $X_{ijk} := 1_{\{i, j\}, \{j, k\}, \{i, k\}\in E_n}$ for all unordered triples ${\{i,j,k\}}$ in ${V_n}$, and normalise the mean $\displaystyle {\bf E}X_{ijk} = 0$ for all such triples, by replacing each $X_{ijk}$ with $X_{ijk} - 1/8$, so that $|T_n|$ gets replaced by $|T_n| - \frac{1}{8}\binom{n}{3}$ (and $|T_n|/\binom{n}{3}$ by $|T_n|/\binom{n}{3} - 1/8$). To prove the given claim, it then suffices to do so in this mean-zero setting.

The first moment calculation shows that $|T_n|$ has mean zero. Hence

$\displaystyle {\bf Var}(|T_n|) = {\bf E}|T_n|^2 = {\bf E} |\sum_{\substack{\{i,j,k\} \in V_n \\ \text{unordered}}} X_{ijk}|^2 = \sum_{1 \leq s,t \leq \binom{n}{3}}{\bf E} X_sX_t$,

where we relabel the $X_{ijk} = X_s$ to range over the set $\{1, \dots, \binom{n}{3}\}$. Note that for $X_s$ and $X_t$ to be correlated, their corresponding triples need to share at least one edge, so the RHS of the above identity equals

$\displaystyle \binom{n}{2}\sum_{1 \leq k, l \leq n-2} {\bf E} X_{ijk} X_{ijl} = \binom{n}{2} [\binom{n-2}{2}/2^5 + (n-2)/2^3]$

This bound was established in the mean zero case, but it is clearly that it holds in general, since subtracting a constant from a random variable does not affect its variance.

Insert this bound into Chebyshev's inequality, we obtain the bound

$\displaystyle {\bf P}(|\frac{|T_n|}{\binom{n}{3}} - 1/8| \geq \varepsilon) \leq O(\frac{1}{n^2})/{\varepsilon}^2$

for any natural number $n$ and any $\varepsilon > 0$, whenever the $X_{ijk}$ all have mean $1/8$ and bounded variance. The right-hand side goes to zero as ${n \rightarrow \infty}$ for fixed ${\varepsilon}$, so $|T_n|/\binom{n}{3} \to 1/8$ in probability. As this bound is summable in $n$, we may apply the Borel-Cantelli lemma to get almost sure convergence as well.