19A.  Central Limit Theorem


These are draft notes extracted from subtitles. Feel free to improve them. Contributions are most welcome. Thank you!

Contents

01 Introduction

So today, you’re in for a treat. You’re goingto learn a theorem and I won't prove anythingto you, you learn it by doing but this theoremis really important for all of statistics. So let’s dive in.And what this theorem really is about many coinflips. Almost generally it’s about thedistribution of the sum of many things.So let’s study many things.

Selection_001.png

02 Counting Outcomes 1

So let’s look at a coin. It has outcome 0-1 andwe’ve already learned that the probabilityof the sum equals exactly K for N coin flips;; looks like this cryptic formula over here:N factorial divided by N minus K factorial andK factorial. And then we had some other term here,if the coin is fair, it is like 2 to the minusN. Right now, I’m just going to care about thesecoins over here. I won't care about the probabilityfor the time being. I want you to help meconstruct a table for these counts as N gets larger.So we start with N equals 1, go all the way to Nequals 4, obviously outcomes range from zeroall the way to 4 at 4 coin flips. So here’s ourtable. It’s also quite obvious that these guysover here can never occur: if you flip the coinonly once, the outcome can’t be 2. So we’re goingto fill out this table over here together for thecoin over here. Tell me, for N equals 1, what arethe two values that go right over here,just those two values.

unnamed.jpg

03 Counting Outcomes 1 Solution

And the answer is 1 and 1,N factorial over N minus K factorial,K factorial - they are all ones,just 1, 1, 1. That was easy.

04 Counting Outcomes 2

Let’s go to equal 2 and ask for the sum,what are these coefficients for an equal 2?

unnamed (1).jpg

05 Counting Outcomes 2 Solution

And the answer is 1, 211. Let’s plug-in zero.2 factorial is 2 divided by 2 factorial givesus 1 and zero factorial is 1. So that’s 1 overhere. But if you plug-in 1SK we get 2 factorialover here which is 2 divided by and another1 stays 2. So this is the correct answer.

06 Counting Outcomes 3

Let’s go N equals 3. Now, it gets interesting.

unnamed (2).jpg

07 Counting Outcomes 3 Solution

The correct answer for this formula is 1, 3, 3, 1and you plug them in, you can see it’s correct.This is actually called a Pascal Triangle. If youhave never seen this before, you can check it onWikipedia. It’s actually quite easily calculated.

08 Counting Outcomes 4

Each element over here is the sum of the valueabove plus the value on the left. This guy overhere, sum of the value above, be zero plus valueon the left. So let’s fill in the same for N equals 4.

unnamed (3).jpg

09 Counting Outcomes 4 Solution

The answer is 1, 4, 6, 4, 1. I used the Pascaltrick but when you plug it in, you get exactlythe same number over here.

10 Shape

So let’s look at these distributions over here.They are really interesting. In the first case,you get something like this: just the counts . In thesecond case, it looks more like this. In thethird case and in the fourth case, we getsomething that looks really interesting, likethis form over here. So here is a questionfor you. What happens when N equals10,000? When I draw it like a diagram likethis, will it look like that, like that, like that?Check the one that looks most plausible.

unnamed (4).jpg

11 Shape Solution

And it so turns out it looks like this over here.You can see it over here. It looks pretty muchlike a function that’s very high in the centerand flattens out to the sides. So how doesthis relate to anything of interest?

12 Number of Outcomes

So let’s look at a more complicated case. Say wehave a three-sided die and it can come up withthe outcomes 0, 1 or 2. And again I just wantto count, I don’t want to work in probabilitiesjust like before, I’m going to help you a little bit.First, I’d like to know what’s the possiblelargest sum, the largest number I put over herefor anything that’s four tosses if eachoutcome can be between 0, 1 and 2. Just writein the box over here.

unnamed (5).jpg

13 Number of Outcomes

And if that outcome is eight, if I toss itfour times, the largest value is two everysingle time. Two times four is eight.

14 Counting Outcomes 5

So, let’s now go all the way to eight and computethose numbers, and it just the counts, not theprobabilities. Give me the first threenumbers right over here.

unnamed (6).jpg

15 Counting Outcomes 5

When we throw this die exactly once,what do you get is one, one and one.

16 Counting Outcomes 6

Now the tricky part starts at n equals two andI will construct this for you, you can take overfor three and four. For the one of the leftto have the sum equal to one, we stay at one,which is we add up the value above and the twoon the left because there’s no three outcomes.This guy over here is two, it’s the one aboveand the two in the left, there’s nothing overhere but there is something over here.This guy here is three, it’s a sum over the oneabove and the two on the left gives us three.We go down to two, which is a one above zeroand the two on the left, all the way back to one.And this already looks very much like thetype distribution we talked about like this.

unnamed (7).png

17 Counting Outcomes 7

Now, it’s your turn. Give me all those valuesover here. There’s six of them and just to helpyou a little I give you one of them. This overhere is a six. Please fill them in.

unnamed (7).jpg

18 Counting Outcomes 7

And we would do just like before, we take thevalue from above, plus the two left ones. So one,two plus one is three, three plus two plus one issix, two, three and two with seven, six, threeand one.

19 Counting Outcomes 8

So now for the final question, there’s nine totalvalues to be filled in, I give you two of them,four over here and there is a sixteen over here,so please fill in the seven remaining values.

unnamed (8).jpg

20 Counting Outcomes 8

And as before we take the one above plus thetwo left, one here, these two are four, six, three,one is ten, six, seven, three is sixteen, six,seven, six is nineteen, sixteen, back to ten,four and one.

Selection_002.png

21 Conclusion

And when we graph this, it looks about likethis. It’s a big function that has the highestvalue at the center, nineteen and then fallsdown in some interesting way that looks awfullymuch like the way the previous exercise fell down.So even for this different experiment withthe die, we get about the same phenomenon thatthe sum of those seems to have a distinct highprobability for what’s the most likely outcomefour and then it falls off in some interesting way.So this is effectively what’s called the centrallimit theorem. And this sounds complicated andin fact it is, but here is the simple versionto remember. Suppose you’re doing manyexperiments. Each of these experiments overhere have some distribution, we don’t care,it has to just be reasonable and you sum thoseall up for some very large number and if N islarge then the joint distribution of the sum ofthose with approach a function it looks like this.That’s called a Gaussian. We discuss theGaussian in depth. It has its own formula andtypically if N is as big as thirty that is maybeyour test thirty people whether they havecancer or not, that’s usually good enough toapproximate this really complicated binomialover here with this relatively simple Gaussianfunction. We’ll learn more about this later,but the key thing to remember is we take manyexperiments, you add them up and outcomes afunction just like this. That’s called thecentral limit theorem.

Selection_003.png