The Law of Large Numbers

Welcome back. So we're getting to a pretty exciting point in this uh short course on probability theory, where now we can start making some very general statements uh about large numbers of random variables. So these are called limiting theorems, and the first one, the one you've almost certainly seen before and is very intuitive, is the law of large numbers. So we're going to state this one today, and then we're going to build on this and kind of show a more powerful result called the central limit theorem soon. This is the first and kind of simplest in these uh limiting statements you can make about sequences of random variables in the large and limit, in the limit of a large number of random variables. Uh so let's get in, and we're going to use Markov's inequality and Chebyshev's inequality um for these results if we want to prove them. Okay, so I'm just going to state it first, and then we're going to kind of show why it's true.

Given a sequence of independent random variables, I've got a bunch of independent random variables. This could be n different uh coin flips, so n Bernoulli random variables, or you know n of some other distribution is fine too. And let's say that each of these random variables has the same mean mu and the same standard deviation sigma, or variance sigma squared. Then the statement of the law of large numbers is the following: given this sequence, we can define something called the sample mean. Uh the sample mean, which literally means the average of all of my samples. Let's say I don't know a model of this probability density. I don't know if it's Bernoulli or binomial or Poisson. I don't have a model, but I collect a bunch of data. Then the sample mean, which I'm going to define as uh X bar equals 1/n times the sum of all of my independent trials from i=1 to n, this sample mean will converge to the actual mean of the distribution uh mu as n goes to infinity. Okay, this will converge uh to mu, and I'm going to switch colors, as uh n goes to infinity. Okay, so this is a pretty common-sense statement. This this should make a lot of sense to you. If I have a bunch of random variables and they each have the same mean, the same uh expected value, mean, the same, you know, mean value, and there's some variance, then as I collect more and more and more data and I compute the average of that data, it should converge—the data average, the sample mean should converge to the actual mean of the distribution um as n goes to infinity.

So this is intuitive; this should be true, but we can actually now prove that this is true using um Chebyshev's inequality that we um that we derived earlier. Um so I'm going to write—okay, so this is good—and there's actually a slightly more formal way to say this. So I'm going to say uh formally the way we would say this, and I'm actually going to prove this two ways. I'm going to kind of give you a thumbnail sketch of why this is true, and then I'm going to prove formally why it's true. So formally, what this means is the probability of my sample mean minus my actual mean, the absolute value of this, the probability that this is bigger than epsilon uh goes to zero as n goes to infinity. So that's what we mean by this sample mean converging to mu: it means that the the probability of my sample mean being being more than epsilon away from mu goes to zero. So I get within an arbitrary epsilon of my actual mean with my sample mean as n goes to infinity. So this is kind of how, if you were a little bit uptight, you would say this. Good. Um and we're actually going to show this uh on a computer. So we're going to start very soon uh kind of going from our probability module to our statistics module, and in our statistics uh short course or module we're actually going to be dealing with real collected data. So we're going to run experiments uh on a computer; we're going to generate data, and we're going to see how fast this X bar converges to mu. We're going to run this experiment. So we're going to um demonstrate, we're going to demo on a computer uh with real data soon. Okay, so uh we'll actually code this up on a computer soon, but for now we're still in kind of probability land, so we're going to prove that this is true, give you some intuition, and then we'll build some more complicated limiting uh theorems soon. Okay, good.

So how would I actually prove this thing? Um maybe I'll switch colors a little bit. Okay, so how would I prove this? So proof. Okay. Um since all of these X's are independent, we know a lot about um the expectation of X bar. We know that we can compute the expectation of X bar, and it should be the sums of all of these expectations; that's pretty useful. So uh let's just write that: since my x's are independent, independent, then I know that the expected value of my sample mean X bar n is the sum of the expectations of each of my independent random variables. It's equal to 1/n times the sum from i=0 to n of the expectation value of each of my independent random variables x_i, and we know that each of these expectations is equal to um is equal to mu. Okay, so that's good. So we know that um the expected value of X bar is equal to um 1/n times n copies of mu; this just equals mu, equals mu. Good. So at least we know that the expected value of x equals mu, but what this theorem is saying is actually much more powerful um than just the expectation of X bar is mu. It's saying that as n goes to infinity, the standard deviation of X bar around that mu gets smaller and smaller and smaller. So that's going to sound a lot like Chebyshev's inequality, and we're going to use Chebyshev's inequality in a minute, but I'll say this a little bit differently. Let's just compute the variance of this guy and see what it looks like. Uh so Var(X bar n), my sample mean, um again these are all independent random variables, so we know how variances sum. This is going to equal 1/n², 1 over n squared times the sum of all of my independent variances, Var of each x_i, i equals uh one to n, and each of these variances is sigma squared, so I'm going to add up n of these sigma squared, divided by n², so this is going to equal sigma²/n. I have n copies of a sigma squared variance, but the way that variances sum, I get a 1/n squared factor out front, and you should, if you don't remember this, pause the video, go back to the lecture on variance and remind yourself that if I sum up n things um you know n things with variance sigma squared, then I will get um I will get this variance of the sum. Okay, and this is nice because it has a 1/n in it. Sigma² is a constant; 1/n gets smaller as n goes to infinity. So this is kind of obvious that as n goes to infinity, the variance of my sample mean goes to zero, and what that means is that I have a distribution of what I expect to get for X bar, my sample mean, and as n goes to infinity that variance gets smaller and smaller and smaller around an expected value of mu, which is kind of what I'm saying here: as I increase the sample size, it—the sample mean should converge to the actual mean, and the variance of the sample mean should get smaller and smaller and smaller, meaning I get closer and closer and closer to mu as I collect more and more data. This doesn't have to be true, but it's a really reassuring uh and useful property of sample means that they will converge to the actual mean, and the variance of that sample mean will get smaller and smaller and smaller.

So if you wanted to formally prove this statement—so this is kind of um a little hand-wavy; I didn't actually prove this exact statement—if I want to do the formal proof, um then what I would use is Chebyshev's inequality. So uh formally what we can say is that the probability of this variable X bar n minus mu, absolute value, being greater than or equal to epsilon should be less than or equal to the variance of this quantity divided by epsilon squared. This should be less than or equal to the variance of my sample mean divided by epsilon squared. This is just Chebyshev's inequality. Okay, so this statement here uh is that very useful Chebyshev uh inequality that we proved a couple of videos ago, and this is the thing here on the left. What I need to show now is that this goes to zero as n goes to infinity, and so this quantity here is equal to uh sigma²/n * epsilon². This is sigma²/n * epsilon², and of course this goes to zero as n goes to infinity. So this is a little bit more formal; we're actually proving the formal kind of definition that um you know the the probability of my sample mean being more than epsilon away from my actual mean goes to zero as n goes to infinity, and we use Chebyshev's inequality to really tightly bound that very very useful idea. Um and maybe I should just draw a picture here. Very useful idea again that if I have an actual mean mu, and I collect a bunch of random samples X—these don't have to be distributed as Gaussian variables; they can be almost anything—Bernoulli, Poisson, exponential, gamma, it doesn't matter—if I collect a bunch of these variables and I average them, that sample mean will start to have a distribution that peaks around the actual value of mu. So this is my sample mean X bar, and if I have a small n it'll be kind of a broad peak; I'll have some variance, but as I collect more and more n, as n increases, this becomes sharper and sharper and sharper, tighter distributed around the true um average value of mu. Very, very useful result, and the next result will prove the central limit theorem—one of the most central and important properties in all of probability and statistics—goes even farther, and it says that as I collect these variables and I average them, this actually starts to become a normal, normally distributed random variable, regardless of what these uh independent random variables are distributed as. No matter what their distributions are, this sum is going to start to converge to a Gaussian or normally distributed variable with this mean and this standard deviation. Very, very powerful, um and this is actually the basis of Monte Carlo sampling, random sampling, um all kinds of survey sampling and statistics, so sampling a small population to infer something about a big population—one of the most important ideas in all of probability and statistics: the law of large numbers, and the follow-on, kind of Big Brother of the law of large numbers, the central limit theorem, which is coming up next. Thank you.