# Variance of average of $n$ correlated random variables

$$\mbox{var} \left( \frac{1}{n} \sum_{i=1}^{n} X_i \right) = \rho \sigma^2 + \frac{1-\rho}{n} \sigma^2$$

where $$X_1, \dots, X_n$$ are identically distributed random variables with pairwise correlation $$\rho > 0$$ and variance $$\mbox{var}(X_i) = \sigma^2$$.

1. How to derive this?
2. How does bootstrap aggregating alleviate the effect of overfitting, according to this formula? What is the relationsip?

By definition, we have

$$\operatorname{var}\left(\sum_{i=1}^n{X_i}\right)=\operatorname{cov}\left(\sum_{i=1}^n{X_i},\sum_{i=1}^n{X_i}\right)=\sum_{i=1}^n{\operatorname{var}(X_i)}+\sum_{i\neq j}\operatorname{cov}(X_i,X_j)$$

which is $$n \operatorname{var}(X_i)+n(n-1)\operatorname{cov}(X_i,X_j)=n\sigma^2+n(n-1)\rho\sigma^2$$, where $$i\neq j$$. Substituting this into the original equation yields the following:

$$\operatorname{var}\left(\frac{1}{n}\sum_{i=1}^nX_i\right)=\frac{1}{n^2}(n\sigma^2+n(n-1)\rho\sigma^2)=\rho\sigma^2+\frac{1-\rho}{n}\sigma^2$$

Each $$X_i$$ can be thought of as a single decision mechanism, call it DM, (e.g. regressor). The variance of your decision was $$\sigma^2$$. By using bootstrap samples and aggregating your DMs' outputs, you end up with a decision variance as above, which is strictly smaller than $$\sigma^2$$ when $$\rho \neq 1$$ and $$n\neq 1$$. DMs will have some degree of correlation of course, because they are trained over bootstrap samples obtained from the same base dataset; however, the correlation between them most probably won't be equal to $$1$$. Overfitted mechanisms in general have large variance, so by aiming to decrease the variance of your DM, you actually address the problem of overfitting implicitly.

• Fantastic! Thank you for so much for your answer. Quick question, in the term $n var(X_i) + n(n-1) cov(X_i,X_j)$ n and n-1 come from. Sorry if it is too obvious question. – Daksitha Withanage Feb 10 '19 at 16:15
• @OmegaD There are $n^2$ pairs of $i,j$, where $n$ of them have $i=j$, and $n^2-n=n(n-1)$ of them have $i\neq j$. – gunes Feb 10 '19 at 16:31
• @gunes This is a great answer, Can you please answer my question also. – Md. Sabbir Ahmed Apr 8 '20 at 14:23
• I know that $\rho\geq -1/(B-1)$ but that does not imply that $\rho>0$ which is stated in the book? Say we have $B=3$ we have that $\rho$ can take the values $-0.5$ without violating anything. How come the proof is only for $\rho\geq 0$? – CutePoison Apr 14 '20 at 13:38
• @CutePoison it is assumed $\rho>0$ in the OP and my proof is based on this assumption. I'm not aware in which book it is, so if you can share the link, I can at least read and comment on it. – gunes Apr 14 '20 at 14:16