2
$\begingroup$

This is a well-known problem in random graph theory, where we show that if $X$ is the number of triangles in $G(V,E,p)$ with $p=o(\frac{1}{n})$, we can show that $$ P(X \geq 1) \geq 1-o(\frac{1}{n}) \to_n 1 $$ using Chebyshev inequality and asymptotic expansion of binomial coefficients, $\binom{n}{k} \sim \frac{n^k}{k!}$.

What I don't understand is the part where the second moment is used for indicator variables: $$ \mathbf{E}X^2 = \mathbf{E} (\sum_{k=1}^{\binom{n}{3}} X_k)^2 = \sum_{k=1}^{\binom{n}{3}} \mathbf{E}X^2_k +\sum_{k \neq j}\mathbf{E}X_k X_j $$ Specifically, I don't understand the absence of 2 in front of the second sum. The explanation is that triangles are ordered. This means that selecting triangle $X_j$ and then $X_k$ is different to $X_k$ and then $X_j$. Could someone explain why?

$\endgroup$
3
$\begingroup$

The issue seems to be just about understanding the notation in the summation index, that is, nothing to do with the specifics of the graph problem.

$\sum_{k\neq j}$ refers to summing over all $(k,j)$ with $k,j \in \{1,\ldots,n\}$ such that $k\neq j$. So, both $(i,l)$ and $(l,i)$ for any $i\neq l$. Since $\mathbb{E}X_k\,X_j = \mathbb{E}X_j\,X_k$, we have

\begin{equation} \sum_{k\neq j} \mathbb{E}(X_k\,X_j) = 2\,\sum_{k<j} \mathbb{E}(X_k\,X_j), \end{equation} where $\sum_{k<j}$ refers to all pairs of indices where $1\leq k < j \leq n$. You are probably thinking about this latter summation.

For example, when $n=2$, $\mathbb{E}((X_1+X_2)^2)$ can be expressed either as \begin{equation} \mathbb{E}(X_1^2+X_1\,X_2+X_2\,X_1+X_2^2) = \mathbb{E}(X_1^2)+\mathbb{E}(X_2^2)+\mathbb{E}(X_1\,X_2)+\mathbb{E}(X_2\,X_1) \end{equation} which is the notation appearing in the question unfolded. Or, since $X_1\,X_2=X_2\,X_1$, this is equal to \begin{equation} =\mathbb{E}(X_1^2) + \mathbb{E}(X_2^2) + 2\,\mathbb{E}(X_1\,X_2) \end{equation} which is the $\sum_{k<j}$ notation unfolded.

$\endgroup$
8
  • $\begingroup$ I'm sorry i don't quite see how this answers my question. The source here:ndsu.edu/pubweb/~novozhil/Teaching/767%20Data/chapter_3.pdf: 'Here Here we assume that all possible triples are ordered and labeled.we assume that all possible triples are ordered and labeled.'. I understand the labelled part (hence $\binom{n}{3}$ number of choices, but why is it ordered? Like triangle 1 and 2 vs 2 and 1 are different. Why? $\endgroup$
    – Alex
    Apr 3 '16 at 12:08
  • $\begingroup$ Can you give a page number? See page 5, "Here the sum in the second term is taken through all the ordered pairs of $i\neq j$, hence there is no “2” in the expression." $\endgroup$ Apr 3 '16 at 12:25
  • $\begingroup$ I maybe misunderstood your question, since I thought you are asking about why $E(\sum(X_i)^2) = \sum_i(E(X_i)^2) + \sum_{i\neq j}(X_i\,X_j)$ rather than $E(\sum(X_i)^2) = \sum_i(E(X_i)^2) + 2\, \sum_{i\neq j}(X_i\,X_j)$ $\endgroup$ Apr 3 '16 at 12:27
  • $\begingroup$ You looked at Thm 3.4 and 3.5, this is exactly my problem. I don't understand why there's not 2 in front of this sum over $\mathbf{E} X_i X_j$ or, rewording it, why the triangles are ordered $\endgroup$
    – Alex
    Apr 3 '16 at 12:36
  • $\begingroup$ Please add a reference/link to the source into the question and clarify that you are asking about the proof of Thm 3.4 on page 5 (if you are asking about something else, clarify that...) $\endgroup$ Apr 3 '16 at 18:49

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.