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

Question

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

Answer 1

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

Answer 2

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