Variance of average of $n$ correlated random variables Reading about deep leaning, I came across the following formula. 
$$ \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$.


*

*How to derive this?

*How does bootstrap aggregating alleviate the effect of overfitting, according to this formula? What is the relationsip?

 A: 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.
