# $\operatorname{Var}(\sum_{i=1}^nX_i)\leq n\sum_{i=1}^n \operatorname{Var}(X_i)$, where "$X_i$"s are not necessarily independent

$$\newcommand{\Var}{\operatorname{Var}}\newcommand{\Cov}{\operatorname{Cov}}$$I am trying to prove the inequality on the title.

My work:

We want: $$\Var\left(\sum_{i=1}^n X_i\right)\leq n \sum_{i=1}^n \Var(X_i)$$

$$\Var\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n \Var(X_i)+\sum_{i\ne j} 2\Cov(X_i,X_j)$$

I know, from the first part of the question, that;

$$|\Cov(X,Y)|^2\leq \Var(X) \Var(Y) \implies|\Cov(X,Y)|\leq\sqrt{\Var(X)}\sqrt{\Var(Y)}\leq\frac{\Var(X) + \Var(Y)}{2}$$ by AM GM Inequality.

\begin{align} & \Var\left(\sum_{i=1}^n X_i\right)=\sum_{i=1}^n \Var(X_i)+\sum_{i\ne j} 2\Cov(X_i,X_j) \\[8pt] \leq {} & \sum_{i=1}^n \Var(X_i) + \sum_{i\ne j} 2\frac{\Var(X_i)+\Var(X_j)}{2} \end{align}

$$\Var\left(\sum_{i=1}^n X_i\right) \leq \sum_{i=1}^n \Var(X_i) + \sum_{i\ne j} \Var(X_i) + \Var(X_j)$$

I am stuck here, somehow I need to manipulate the right hand side to get $$n\sum_{i=1}^n \Var(X_i)$$ but I can't see it. Any help would be great!

One error in your first step: $$\text{Var}\sum_{i=1}^n X_i = \sum_{i=1}^n \text{Var}(X_i) + \sum_{i \ne j} \text{Cov}(X_i, X_j).$$ (There is no $$2$$ here. If you want the factor of $$2$$, you need the sum $$\sum_{i < j}$$ not $$\sum_{i \ne j}$$.)

$$\sum_{i \ne j}(\text{Var}(X_i) + \text{Var}(X_j)) = 2(n-1)\sum_{i=1}^n \text{Var}(X_i).$$ (Count how many times $$X_1$$ appears in the sum, etc.)

• Sometimes when people write $\displaystyle \sum_{i\,\ne\,j}$ they mean $\displaystyle \sum_{i\,:\,i\,\ne\,j}$ where $j$ is fixed, a free variable, and sometimes they mean $\displaystyle \sum_{i,j\,:\,i\,\ne\,j},$ and sometimes when they write $\displaystyle \sum_{i\,<\,j}$ then mean $\displaystyle \sum_{i\,:\,i\,\ne\,j}$ and sometimes $\displaystyle \sum_{i,j\,:\,i\,<\,j}$ and often, as in this case, the context makes it clear what is intended. But$\,\ldots\qquad$ Mar 31, 2020 at 18:25
• $\ldots\,$I would somewhat more frequently not rely on context than most would. And the punch line: maybe $\displaystyle \sum_{\{i,j\}\,:\,i\,\ne\,j}$ is a good notation for what the original poster may have intended. $(i,j)$ is an ordered pair differing from $(j,i);$ and $\{i,j\}$ is an un-ordered pair that is the same as $\{j,i\}.\qquad$ Mar 31, 2020 at 18:25

Your strategy is the right one. We have $$\operatorname{Var}\sum_iX_i\le\sum_i\operatorname{Var}X_i+\sum_{i\ne j}\frac{\operatorname{Var}X_i+\operatorname{Var}X_j}{2}=\sum_{ij}\frac{\operatorname{Var}X_i+\operatorname{Var}X_j}{2}.$$The last expression has $$\operatorname{Var}X_k$$ coefficient$$\sum_{ij}\frac{\delta_{ik}+\delta_{jk}}{2}=\sum_{ij}\delta_{ik}=n\sum_i\delta_{ik}=n.$$

• What does ij mean, or did you forget the symbol :) Thanks a lot for the answer
– Xia
Mar 31, 2020 at 17:47
• @70pr4k I forgot nothing: $\sum_{ij}$ sums over all unordered pairs of values for $i,,j$.
– J.G.
Mar 31, 2020 at 18:02