# 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?

$$\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, since they are trained over bootstrap samples obtained from the same base dataset, but 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. – OmegaD Feb 10 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 at 16:31