13.1 Variance of Sums and Averages

Let $\{X_j\}_{j=1}^n$ denote a collection of random variables. Let:

denote the sum of the variables, and:

denote their sample average.

How variable is $S_n$? What about $\bar{X}_n$?

Expectation¶

To address their variance, we will first need their expectation. We’ve worked out these expectations before, but, we will ened them repeatedly in this chapter. So, we’ll recall them a last time before progressing.

Variance of a Sum¶

Two Variables¶

Let’s start with the simplest case, $S_2 = X_1 + X_2$.

Since we are only working with two variables, drop the subscripts and denote the random pair $[X,Y]$, and the sum, $S$.

We could proceed by solving for the distribution of $S$ explicitly (see Section 10.3). If the variables are independent we could use convolution. In practice, this is difficult unless the random variables are drawn from convenient distributions. It also will not scale easily to sums of $n$ variables. If you want to learn more about the distribution of $S_n$, wait for Section 13.4.

For now, we’ll try to work out the variance using properties of expectation:

The expectation of a sum is the sum of the expectations, so:

Let $X_0 = X - \mathbb{E}[X]$, and $Y_0 = Y - \mathbb{E}[Y]$ denote the centered variables. Then:

Now, expand the square:

Then, use additivity and linearity to break the expectation into a sum of pieces:

Finally, apply the definition of variance and covariance in Sections 4.3 and 11.1 to identify each term:

Therefore:

In the special case when $X$ and $Y$ are uncorrelated, as when they are independent, then the covariance is zero. So:

If $X$ and $Y$ are positively correlated, then $\text{Var}[X + Y] > \text{Var}[X] + \text{Var}[Y]$. So, when $X$ and $Y$ are positively correlated, their sum is more variable than it would be if they were uncorrelated. If $X$ and $Y$ are negatively correlated, then their sum is less variable than it would be if they were uncorrelated.

We can extend these results to a sum of $n$ variables.

$n$ Variables¶

To extend to $n$ variables, $\{X_j\}_{j=1}^n$, we will need to track the covariance between every possible pair. We can track all of the covariances using a covariance matrix.

Then, we can rewrite our equation for the variance of a sum of a pair of random variables:

In other words, the variance of a sum of two variables is the sum of every entry of the covariance matrix for the two variables. It is the sum of all possible pairwise covariances we can construct out of pairs of variables selected from the sequence.

This result extends naturally to $n$ variables.

If all of the variables are uncorrelated, as when they are mutually independent, then the covariances between distinct variables are all zero. Then:

In the special case when the variables are uncorrelated, and identically distributed, then $\text{Var}[X_i] = \sigma^2$ for some $\sigma > 0$. Then:

This result is an important scaling law for variances of sums and averages. The variance of a sum of independent, identical variables grows proportionally to $n$. We can now show that the opposite is true for averages. While the variance in a sum increases as we add more terms, the variance in a sample average will decrease, provided the variables are sufficiently uncorrelated.

Example: Variance of Binomial Random Variables¶

Suppose that $S \sim \text{Binomial}(n,p)$. What is the variance in $X$?

Let’s adopt the strategy we used to find the expectation of the binomial in Section 4.2.

A binomial random variable represents the total number of successes in $n$ independent, identical, binary trials with success probability $p$. Let $\{I_j\}_{j=1}^n$ represent the string of indicators associated with each trial. Then $I_j = 1$ if the $j^{th}$ trial succeeded, and $I_j = 0$ otherwise. Then, we can write $S$ as a sum, $S = \sum_{j=1}^n I_j$.

It follows immediately that:

We don’t need to add any covariance terms since the trials are independent, so their indicators are uncorrelated.

The trials are also identical, so the variance in a binomial random variable is the variance in a sum of $n$ independent, identically distributed variables. So:

for any $j$ we like. For simplicity, set $j = 1$. Then $\text{Var}[S] = n \text{Var}[I_1]$.

To finish the problem, we need the variance in an indicator. We’ll solve for this variance directly:

The variable $I_1^2$ is the same as the variable $I_1$ since $0^2 = 0$ and $1^2 = 1$. Therefore:

Recall that the expected value of an indicator is the chance of the event it indicates. Therefore, $\mathbb{E}[I_1] = p$, the success probability. Then:

So, the variance in an indicator is a product of the success and failure probabilities. It follows that:

Variance of a Sample Average¶

We can use the results we derived for sums to work out the variance of a sample average. This time, we can just use the scaling rule for variances (see Section 4.3). Recall that, $\text{Var}[a X] = a^2 \text{Var}[X]$ for any constant $a$ and variable $X$. Therefore:

So, to find the variance of a sample average, just plug in the variance of a sum, and divide by $n^2$.

We’ll study the result in the general case, the uncorrelated case, and the uncorrelated and identical case.

First, the general case.

So, to compute the variance in a sample average, find all the covariances, fill in the covariance matrix, then average the entries.

Just as the variance of a sum is the sum of all the covariances, the variance in an average is the average of all the covariances.

If the variables are uncorrelated, then all the off-diagonal entries of the covariance matrix are zero, so:

If the variables are uncorrelated, and all have the same variance, $\sigma$, then $\bar{\sigma} = \sigma$.

This result is an important scaling law for variances of sums and averages. The variance of an average of uncorrelated variables with matching variances decays proportional to $1/n$. In particular, the variance in an average of independent, identical random variables is proportional to $1/n$.

This is our first example of a concentration phenomena. The distribution of sample averages of independent, identical random variables concentrates about its expectation as $n$ increases since the variance in the sample average decays to zero as $n$ diverges. This is why sample averages of independent, identical variables form reliable estimators. The variance in the sample average decreases as the number of samples grows!

Special Case: Independent, Identical Variables¶

The case when $\{X_j\}_{j=1}^n$ are independent and identically distributed is both the simplest and most important. We’ll highlight it here.

Sample Averages are Consistent Estimators¶

Let’s put these ideas together to prove that sample averages of large collections of samples, are good estimators for unknown expectations.

To start, suppose that $\{X_j\}_{j=1}^n$ are drawn independently and identically with unknown $\mathbb{E}[X_j] = \mu$ and unknown, but finite, standard deviation $\text{SD}[X_j] = \sigma$. Then, as suggested in Section 12.1, estimate the unknown mean using the sample average:

How accurate is this estimator?

We can measure accuracy with the expected squared error:

Let’s compute the expected square error when we adopt the sample average as our estimator for the unknown mean.

First, the bias. We’ve shown that $\mathbb{E}[\bar{X}_n] = \mu$, so the estimator is unbiased. Therefore, $\text{bias}(\hat{\mu})^2 = 0$. Then, the expected square error in our estimate is exactly the variance in the sample average:

Plugging in our formula for the variance of a sample average:

Since $\sigma$ is finite:

So, the expected square error in the estimate $\bar{X}_n \approx \mu$ converges to zero in the limit as $n$ diverges to $\infty$.

This is a form of consistency. In the limit of infinitely many samples, the expected error in the estimator vanishes.

Example: Frequencies Estimate Chances¶

All the way back at the start of the course we defined chance as long run frequency. We can now justify that definition.

Suppose that $E$ is some event. Let $p = \text{Pr}(E)$ denote the chance that $E$ occurs.

To relate this chance to a measurement we could produce from an experiment we need a procedure for estimating $p$ from data. The simplest procedure is to repeat the random process $n$ times, making sure that all repetitions are unrelated to each other (independent) and are identical. Let $I_j = 1$ if $E$ occurs on the $j^{th}$ repetition and zero otherwise. Then, the total number of times $E$ occurs in the $n$ trials is $S_n = \sum_{j=1}^n I_j$.

So, the observed frequency with which the event $E$ occurred is:

The variable $S_n$ is binomial with unknown success probability $p$ on $n$ trials. Recall that the observed frequency, $s/n$ is the maximum likelihood estimator, $\hat{p}(s)$, for the success probability of a binomial random variable. Therefore $\text{Fr}(E)$ is a maximum likelihood estimator for $p$.

Is the frequency a consistent estimator?

To show consistency, we need to show that it is unbiased (or, if biased, that the bias vanishes in the limit as $n$ diverges), and that the variance in the estimator converges to zero as $n$ goes to infinity.

To show that the frequency is an unbiased estimator, write the frequency as a sample average of the indicators:

Then, $\mathbb{E}[\text{Fre}(E)] = \frac{1}{n} \sum_{j=1}^n \mathbb{E}[I_j] = \frac{1}{n} \sum_{j=1}^n p = p$. So, the frequency is an unbiased estimator.

To show that it is a precise estimator, and becomes more precise as $n$ increases, let’s compute its variance. We already know the variance in an indicator is $p(1 - p)$ and in a binomial random variable is $n p(1 - p)$. So, the variance in the observed frequency is:

So, the variance in the frequency decays proportional to $1/n$. As we collect more samples, our estimate to the unknown probability becomes more stable.

At largest, $p(1 - p) = 1/2 \times 1/2 = 1/4$, so, at largest:

Then $\lim_{n \rightarrow \infty} \text{Var}[\text{Fr}(E)] = 0$ no matter the value of $p$. It follows that the expected square error in the estimate, $\text{Fr}(E) = \frac{1}{n} S_n = \hat{p}(S_n) \approx p$ vanishes in the limit of infinitely many samples. So the frequency is a consistent estimator in the expected square sense. This result justifies the definition:

We can also use this analysis to generate finite sample guarantees. For example,

The larger $n$, the smaller this upper bound. We’ll exploit this analysis at length in Section 13.3. For now, we’ll use it to give suggested sample sizes to ensure reliable estimates of unknown chances.

Suppose that we want to estimate $p$ with the observed frequency, and want the standard deviation in our estimate to be smaller than some error threshold $\sigma > 0$. Then, since we don’t know $p$, we should set the upper bound on the standard deviation less than $\epsilon$. That way, even in the most variable case, our estimator will have standard deviation at most $\sigma$. This requires:

Since sampling is expensive, we should pick the smallest $n$ that satisfies the bound. That is $n = \lceil (2 \sigma)^{-2} \rceil$ where $\lceil x \rceil$ means “round $x$ up to the nearest integer.”

Suppose, for example, that we wanted to guarantee that the standard deviation in our estimator was less than $0.05 = 1/20$. Then we would need, at smallest, $n = \lceil (2 \frac{1}{20})^{-2} \rceil = \lceil (\frac{1}{10})^{-2} \rceil = \lceil 100 \rceil = 100$ samples. If we had instead demanded that the standard deviation in our estimator was less than $0.005 = 1/200$ then we would have needed, at least, $n = 10,000$ samples.

Here’s a table of suggested sample sizes for different error controls:

Notice the diminishing returns. We can always decrease the standard deviation in our estimator by collecting more samples, but, to actually make the estimator precise, we need very large sample sizes.

Example: Asymptotic Analysis of Biased Estimators¶

The consistency of sample averages can help us study the behavior of estimators that can be expressed as a function of a sample average. For example the maximum likelihood estimator to the parameter of a Geometric distribution, based on $n$ independent, identical draws, $\{W_j\}_{j=1}^n$ is (see Section 12.2):

In Section 12.2 we showed that this estimator is biased using Jensen’s inequality (see Section 4.1). Jensen’s inequality explains the sign of the bias (the estimator has positive bias, so systematically overestimates) but provides no insight into the size of the bias.

In this section we will study an approximate to the bias based on a Taylor series expansion of the function $1/x$. This approximation will approximate the bias using the variance in the sample average $\frac{1}{n} \sum_{j=1}^n W_j$. We’ll see that, since the variance in the sample average vanishes as $n$ increases, so does our approximation to the bias. To see the derivation based on a Taylor series, open the dropdown below.

Let’s find the bias in the approximation to the maximum likelihood estimator:

Since expectations are additive and linear (see Section 4.2):

The middle term cancels since $\mathbb{E}[\bar{W}_n - 1/p] = \mathbb{E}[\bar{W}_n] - 1/p = \mathbb{E}[W_1] - 1/p = 1/p - 1/p = 0$. The last expectation is a variance since $1/p = \mathbb{E}[\bar{W}_n]$. Therefore:

The second term is the bias

We can work out a closed formula for this bias using our formula for the variance of a sample average:

The variance in a geometric random variable is $(1 - p)/p^2$. Therefore:

So, the bias in the approximate maximum likelihood estimator vanishes as the number of samples diverges. It is asymptotically unbiased.

Although this analysis is not exact, it correctly recovers the asymptotic behavior of the bias in the maximum likelihood estimator. The maximum likelihood estimator is also asymptotically unbiased with bias that vanishes at rate $\mathcal{O}(n^{-1})$. This behavior is typical. Many maximum likelihood estimators are asymptotically unbiased with a bias that vanishes at rate $\mathcal{O}(n^{-1})$ in the sample size.

Dependent Variables¶

What if the samples are not identical? What if they aren’t independent? Can we identify more general situations where sample averages converge?

So, even sample averages of dependent random variables may converge provided the dependences are weak enough. If you go on to study stochastic process, or Monte Carlo methods, you’ll see this argument appear in a wide variety of useful models.