$\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!


2 Answers 2


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.)

  • $\begingroup$ 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$ $\endgroup$ Mar 31, 2020 at 18:25
  • $\begingroup$ $\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 $ $\endgroup$ 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.$$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .