What is the $(\sum_{i} X_i)^2$ equal to?

Question

We have an indicator Random Variable $X_i$, that takes either the value 0 or the value 1. I read that the square of its sum is:

$$\left(\sum_{i} X_i\right)^2 = \sum_{i} X_i^2 + \sum_{i,j: i \neq j} X_iX_j$$

Why is this true and how many terms are in the second summation ($\sum_{i,j: i \neq j} X_iX_j$), if there are n terms in general?

Answer 1

This is just using the distributive property to multiply out $$ (X_1+X_2+\ldots+X_n)(X_1+X_2+\ldots +X_n).$$ There is a direct term $X_i^2$ for every $i$ and then there are cross terms. For instance, we have $X_1 X_2$ from the $X_1$ in the left factor, multiplied by the $X_2$ in the right factor, and then an $X_2X_1$ from the $X_2$ in the left factor multiplied by the $X_1$ in the right. So there is a cross term $X_iX_j$ for every pair $(i,j)$ with $1\le i\le n$ and $1\le j \le n$ and $i\ne j.$

How many terms there are are just how many such pairs. This is the number of ways of choosing $2$ different numbers from $\{1,\ldots, n\},$ where the ordering matters. This should be familiar if you've seen any combinatorics. There are $n$ choices for the first number and $n-1$ choices for the second number. So the total is $n(n-1).$

Notice that these terms come in pairs: you get both a $X_1X_2$ term and a $X_2 X_1$ term, which are the same thing. So you will often also see the crossterms written $$ 2\sum_{i<j} X_i X_j,$$ in which case there are $\frac{n(n-1)}{2}$ terms in the sum (we've just collected pairs of equal terms together, thus the factor of $2$ out front).

Answer 2

There is an alternative expression for this expansion that generalises to higher powers as well. Let us denote the Kronecker product by $\otimes$. Let us also denote $$x^{\otimes n} = \underbrace{x \otimes \ldots \otimes x}_{n\; \text{times}}.$$ Then for $x, y\in {\rm I\!R}^n$ and $k\in{\rm I\!N}$ we have $$(x^\intercal y)^k = (x^{\otimes k})^\intercal y^{\otimes k}.$$

For $y=(1,1,\ldots,1)$ we have $$(1_n^\intercal x)^k = \left(\sum_{i=1}^{n}x_i\right)^k = 1_{n^k}^\intercal x^{\otimes k} = \sum_{j=1}^{n^k} (x^{\otimes k})_j.$$ I've often found that this formula is easier to work with.