Proof of the Central Limit Theorem

Welcome back. So today we're going to prove the central limit theorem. This is one of the culminations of everything we've been learning about probability theory. So we're going to synthesize a lot of things we've learned. For example, the moment generating function is going to be used, and lots of other facts, to prove the central limit theorem, which is one of the most important and central results in all of probability. It's also going to be the foundation of lots of what we're going to do in statistics.

I'm just going to state the theorem, give kind of some alternative ways of thinking about it, and then we're going to dive into the proof. It's going to be pretty technical. This is kind of an advanced video, and I'll try to link to other concepts that you'll need to know to build on. I'm not going to do a ton of review; I'm just going to dive in. Okay, so the central limit theorem is a surprising result that says that if I have a bunch of independent identically distributed (IID) random variables X1 through Xn, then if I take the sum of those random variables, and that itself is a new random variable, then that sum tends to become normally distributed in the limit of large n—a large number of samples or random variables.

In the proof that I'm going to do, we're going to assume that each of these n random variables have mean zero and variance Sigma squared, and that they are all sampled from the same identical distribution, and they're sampled independently. So this could be n coin flips; this could be n samples from a Poisson distribution; this could be n measurements of a physical system—measurements of the speed of light. Okay. And as long as that random variable has a mean zero and a variance Sigma squared, then this proof is going to apply. Now notice in my examples, actually the mean is not zero for the speed of light; the mean is not zero for a Poisson distribution; and the mean is not zero for a Bernoulli coin flip random variable. All of this can be generalized very, very easily to a mean mu, a non-zero mean. It's just easier to show you the proof for zero mean IID random variables X1 through Xn. Okay, good. So, and this is very surprising. It doesn't say what the distribution of these Xs are; it just says that they have to have—they have to be sampled from the same distribution independently, and they have to have the same mean and variance. Good. And so this sum SN is going to tend to be a normally distributed random variable in the large n limit. And so the way we mathematically say this is that the limit of the probability—so this is kind of—notice that I'm using this big Phi function here, the cumulative distribution function of the standard unit normal with zero mean and standard deviation one. This S is not going to have standard deviation one. Okay, so I'm going to have to normalize it by its standard deviation, which in this case is going to be Sigma times the square root of n, where n is the number of these random variables. So if I take SN divided by its standard deviation, Sigma *√n, then that random variable will become normally distributed with a standard unit normal—mean zero, standard deviation one. Good. And this is how we say it: We say that the cumulative density function of this random variable converges to the cumulative density function of the standard unit normal.

Now there are some equivalent ways of writing this. I'm just going to—before I prove it, I want to write a couple of more intuitive ways of writing this. Equivalently, you could say—equivalently, you could say that SN, this SN, is normal itself with mean zero and variance n Sigma squared, or standard deviation √n Sigma. And that's kind of what we're using here is that if we divide SN by its standard deviation, it becomes a standard unit normal, normal(0,1). But SN itself is a normal with mean zero and standard deviation n Sigma squared. And it also says that the average value of these, which we're going to call X-bar, and we're going to define this as 1/n times the sum of n—so this is just the average value of all those random variables—this is normal with mean zero and standard deviation or variance Sigma squared over n. Okay, so these are kind of equivalent to this statement here. It's just that what we're going to try to do is show that the moment generating function of this random variable is equal to the moment generating function of the standard unit normal. So it's nice to normalize in the statement of the central limit theorem, but these are completely equivalent statements. And I'll leave it as an exercise for you to show how this changes when we have a non-zero mean—when the mean of these random variables is some mu—how do these statements change? Okay, probably we'll have like a, you know, minus mu here or something like that. Okay, good. So now I'm just going to jump into the proof, and it's got a bunch of steps, so I'll go through them, and then we'll zoom out and kind of summarize what the big picture is. Okay, good. Okay, so let's start our proof, and I think I'll just—I'll just start going. So the proof, and I want to give myself some room here because this is going to take a little bit of space. So I'm going to break this down into steps. The first step is that we're going to show—it's to state how we're going to prove it. Step one, basically, is we want to show that this random variable has the same moment generating function as a standard unit normal. So we want to show that the random variable—I'm going to call it Z equals this thing, SN/√n Sigma—and we want to show that that is standard normal with mean zero and standard deviation one. And we're going to show this specifically by showing that they have the same moment generating functions. So we want to show that this is true, and we will show—we will show that they have the same—maybe I'll put this in pink to highlight it—the same moment generating functions (MGFs). And I had a whole set of lectures on the moment generating functions; if you don't remember, go back and watch those. But the moment generating function for the standard unit normal, the M(t) for the standard unit normal, is e^(t²/2). So we're going to try to build the moment generating function of this random variable here, and we're going to show that in the n goes to infinity limit it converges to this, which is the moment generating function of the standard unit normal. And because the moment generating function uniquely identifies the probability distribution, if they have the same moment generating function, then they will have the same probability density function; they'll be the same distribution. So this is what we're going to do is show these moment generating functions are equal, and we're going to build this in stages. So this is Step One—just stating how we're going to approach this problem. Good. Maybe I'll just kind of switch colors throughout these different phases of the proof here; maybe I'll go to blue. So Step Two is what I'm going to do now is I'm going to let each of these individual Xs have their own moment generating functions, and then we're going to build the moment generating function of this from those individual moment generating functions. Good. And remember we know at least the first and second moments of these moment generating functions. Good. We know the mean and the variance. Good. So now what we're going to do is we're going to let each of my Xis, Xi, have a moment generating function M(t). Okay, each of these random variables has a moment generating function M(t), and they are all the same moment generating functions because they come from the same distribution; they're independently identically distributed. So they have the same PDFs; they're sampled from the same distributions. So each of them have the same moment generating function, and we know this property that the M—the moment generating function of a sum of random variables is the product of each of their moment generating functions. So we know that the moment generating function of SN is the product of all of these n moment generating functions. So this is going to be written as M(t)^n. Okay, good. So we're doing really good so far. We don't know what the moment generating function M(t) is; we're just going to call it some function M(t), but we at least know the first and the second moment, so that's useful, and we know that the moment generating function of SN is just the product of all n of these identical moment generating functions. That's pretty useful. Okay, good. So now where do I go from here? Okay, just put a little line here so I can keep track of things. Okay, now Step Three, what I'm going to do is I'm going to actually Taylor series expand this moment generating function, and I'm also going to plug in this SN/√n Sigma, so I'm going to do this correction factor and show what that moment generating function is as well. Okay, good. So I think what I want to do here is now do my Taylor series approximation. Good. So Step Three is we're going to Taylor series expand M(t). And this is kind of cool because the coefficients of this Taylor series expansion are in fact my moments. So we can say M(t) = M(0) + tM'(0) + t²/2M''(0) + ... And what I'm going to do is I'm going to just call that ... some number. Okay, so M(0), the zeroth moment, is always one. This is essentially, if you write this down, it's the sum of 1 times the probability, so that all adds up to one. So this equals one. M'(0) is just the mean, okay, so this is also zero. Sorry, this is equal to one; this is equal to zero. Okay, because M'(0) is zero; this is zero mean. So if this was mu, I'd plug in a mu here. Okay, this guy is t²Sigma²/2 because the mean is zero. Okay, so this is t²Sigma²/2, and we're going to call all of these higher-order terms—we're just going to call this some epsilon of order t³ or higher. Okay, so all of these terms are higher order in this t. Okay, so the third, the fourth, the fifth moments, I'm going to lump them all into this higher-order term here, and what we can do is essentially we're going to, you know, take the limit as n goes to infinity, and we're going to show some interesting properties of how this moment generating function behaves. But I can, of course, also take this and plug it in here and take this to the nth power if I wanted to. Good. Okay, so Step Four, there's a lot of steps to this, so bear with me. So now what we have is we have an expression for SN, the sum, in terms of M(t), the moment generating function of each of these, and we can Taylor expand each of those M(t)s and get terms in terms of the mean and the variance that we already know and some higher-order terms. And so probably I'm going to plug this in here and take it to the nth power, but before I do that, I'm not just trying to show that SN is distributed as this normal; it's easier to show that SN divided by √n Sigma is the standard unit normal. Okay, so I'm going to have to transform this by dividing by √n Sigma, and so there's a little identity that I think you should know here, which is basically if I have a new random variable Y = bX, then the moment generating function of Y equals the moment generating function of X times bT. And so what this implies is that the moment generating function of this Z variable, the moment generating function of this Z variable with respect to t, is equal to the moment generating function of SN evaluated at t/√n Sigma. Okay, so that essentially means that it's pretty easy to find the moment generating function of this Z variable, which has an easier distribution to fit, by taking the moment generating function of SN and plugging in t/√n Sigma into this moment generating function. And just the last step, because we know that it's equal to this simple M(t)^n, this is M(t/√n Sigma), all of that to the n power. Okay, good. So this is just a useful fact that allows us to take this slightly more complicated expression for this sum and normalize it by its standard deviation, and now all we have to do is show that this moment generating function is equal to the moment generating function of the standard unit normal. Good. So now I can use this Taylor series expansion, and I can evaluate it at t/√n Sigma, and I can take this whole thing to the nth power. And so we're super, super close; we're basically there—just a couple more steps, and we'll have this proven. Good. So maybe I'll do pink now. Okay, so Step Five, this is where kind of the rubber hits the road, is now I'm going to compute this M(t/√n Sigma). I'm going to plug that into this Taylor expansion, so I'm going to get an expansion for this inner term, and then I'm going to take it to the nth power. Okay, so M(t/√n Sigma) is approximately equal to this Taylor series expansion where I plug in this for t. Okay, so this is approximately equal—or this is, I guess, exactly equal to—1 + (1/2)Sigma²t²/(Sigma²n) + epsilon of all these higher-order terms, which I'm going to say, you know, they're still order t³, but I'm just going to write down, you know, the third-order term would be like this. Okay, so each of these is going to be divided by like n^(3/2), n^(4/2), n^(5/2), n^(6/2), and so on. So this is kind of my higher-order terms, and this is kind of bad notation; it really should just be epsilon(t³), but I want to explicitly show that each of these terms has a bigger and bigger power of n in the denominator because when we take the limit as n goes to infinity, all of these terms are going to die out. Okay, good. These Sigma squares cancel, and so this is going to be, you know, 1 + (1/2)t²/n + this epsilon ..., okay, all this higher-order terms. And of course this epsilon goes to zero as n goes to infinity; that's the really important part here is that this goes to zero as n goes to infinity. Okay. And now the last step is take this to the nth power and take the limit as n goes to infinity. Okay. Last step; maybe I'll do this in yellow. Okay, Step Six. Okay, we're going to take this expression to the nth power and then take the limit as n goes to infinity. So the limit as n goes to infinity of my moment generating function of Z(t) is equal to the limit as, again, n goes to infinity of all of this stuff—of 1 + (1/2)t²/n + this epsilon, let's say epsilon_n, all of that to the nth power. The epsilon goes to zero as n goes to infinity, and so this—and it goes to zero fast—so this is a technical point that I'm not going to exactly cover, but this epsilon_n goes to zero fast enough that we can neglect it, and this equals the limit as n goes to infinity of (1 + t²/2n)^n. Now you'll remember that the limit of (1 + a/n)^n is just e^a. So maybe I'll write this down. Kind of just a fact: limit as n goes to infinity of (1 + a/n)^n just equals e^a. This is a definition of the exponential of a is this formula here. And so this expression here equals e^(t²/2). That is the moment generating function of my Z variable, and notice that the moment generating function of my Z variable is exactly equal to the moment generating function of my standard unit normal. So this is the proof; we've proven it. I'm going to put my little square down here. This is a big proof, so we get to use math notation; we finished the proof. Okay, so now let's just zoom out and summarize and make sure we still believe every step and that this makes sense.

Okay, so we're trying to prove the central limit theorem—that the sum of a bunch of IID random variables becomes normally distributed. So the sum of a bunch of IID random variables becomes normally distributed with a new variance that's related to the variance of each of those variables. And the way we state that more mathematically is that if we normalize this sum by its standard deviation, we say that that normalized variable Z becomes a standard unit normal variable. And we prove that by constructing the moment generating function of Z and showing that it converges and equals the moment generating function of a standard unit normal in the large n limit, as n goes to infinity. Now we've done this for a mean of zero, but you could also substitute in a mean equals mu and go through all of these steps and convince yourself that this is still true and modify these. That's a really good exercise for you to make sure that you understand the mechanics of what's going on here. Okay, so the steps now are to somehow construct the moment generating function of Z and show that it converges to the—to the moment generating function of a standard unit normal. So the moment generating function of Z is related to the moment generating function of this sum SN, and the moment generating function of my sum is the product of all of the moment generating functions of each of these Xi, but because they're IID, they have the same moment generating function. So the moment generating function of SN is just m^n, where m is the MGF for each of these random variables. Good. This is kind of the simplest step here. Now what we're going to do is we're going to try to get an expression for this M(t) and then take it to the nth power, and we're also going to have to do a correction because we don't actually want the MGF of the sum; we want the moment generating function of this normalized sum, where it's normalized by its own standard deviation; we want this Z variable because it has the simpler distribution. Okay, so what we're going to do—this is kind of two steps that you could have taken in either order—so first thing we're going to do is we're going to normalize this SN by its standard deviation, and we're going to show that the moment generating function of Z is equal to the moment generating function of S where you now evaluate it at t/√n Sigma. So this is a nice easy expression here; you just are relating Z to SN. Similarly, we're going to Taylor expand this little simple moment generating function of my Xi, and the moment generating function—if you Taylor expand it—this is super cool; the coefficients of that moment generating function are the moments themselves. So the coefficients of the Taylor series expansion—you'll notice this is the zeroth moment, first moment, second moment, and so on—so that's another intuitive understanding of what these moments mean is that they're coefficients in my Taylor series expansion. Okay, so now we take all these pieces together. We can compute the this expression for our Z variable is just all of these little M(t)s evaluated at t/√n Sigma taken to the nth power. So so now we're taking these two facts and we're kind of plugging them into here. Okay. And what we're doing now—let's see where we have that—so we take this Taylor series expansion, we evaluate it at this t/√n Sigma, and we can expand this thing out and find this very, very simple expression for the Taylor series expansion of this individual normalized element, and this epsilon are all of the higher-order terms in my moment generating function, and you'll notice that they all have bigger and bigger powers of n in the denominator, so these are going to go to zero as n goes to infinity. Finally, we plug all of this into our expression for this moment generating function of Z, which is the moment generating function of each little element to the nth power; we take the limit as n goes to infinity, and we have convinced ourselves that this epsilon goes to zero very, very fast because it has big powers of n in the denominator, and we're left with the limit as n goes to infinity of (1 + t²/2n)^n, which is exponential—e^(t²/2). And because Z and our standard unit normal have the same moment generating functions, that means that they have the same probability distribution function, the same cumulative distribution function, and thus we have proven the central limit theorem.

Okay, so I want you to slow down and convince yourself this is true. I want you to ask yourself what happens if the mean of these random variables is a mu instead of a zero. Basically, nothing changes; it's just a little bit more complicated to derive everything. And I hope that this is as satisfying for you as it is for me. This is kind of the culmination of, you know, our understanding of moment generating functions, probabilities of things that are independently identically distributed, and this is one of the most important results in all of probability and statistics. We're going to use this all the time when we start sampling data from distributions—like actually collecting data and trying to infer things about that distribution—we're going to use the central limit theorem all the time, so it's really good to have a really strong intuition and understanding for why this is true and how we actually construct a proof. Okay, thank you.