Transcription
Welcome back. So we have been looking at how to compute, uh, probabilities of things like, uh, how many poker hands are there that have straight flushes, or how many poker hands have full houses, or things like that. And at the end of the day, this involves counting how often that given event is out of the total number of things that can happen; out of all of the poker hands, how many of them are flushes, or how many of them are full houses, or whatever. And so that really just means counting events: counting total poker hands, counting total poker hands where there's one king, things like that. And we've come up with some really useful formulas. Uh, so I'm going to write down one useful formula, and we're going to relate this to something called the binomial coefficient, and then we're going to generalize it to the multinomial distribution. And I think of this as being useful for calculating how many hands of poker, uh, are possible. So if I deal out a five-card hand of poker out of a 52-card deck, that's going to be distributed according to the binomial distribution. If I deal out two hands of poker—so if there's two people playing—how many ways can I deal out two hands, or three hands? That's the multinomial distribution; super, super useful, very good set of formulas to know, and it'll, if you want to calculate lots of kind of complicated probabilities, okay.
So the number of unordered samples I can collect, number of unordered samples, uh, samples are out of n objects, out of n total objects. So n would be 52 cards; my sample would be five cards for a hand. The number of unordered samples are out of a total of n without replacement—meaning after I deal the first card, there's only 51 cards left; after I deal the second card, there's only 50 cards left—uh, so unordered samples without replacement is n choose R. And remember n choose R, um, in shorthand, sometimes we call this n choose R; it's a formula, uh, literally n choose R. Just recall this is n factorial / (n-R) factorial * R factorial. Okay, that is the formula; that's the that's how we count how many, let's say, hands of poker could be dealt, how many five-card hands could be dealt out of a 52-card deck without replacement, and knowing that the order doesn't matter; I don't it doesn't matter if I get a seven first then a nine, or a nine first and then a seven. This is the number of unordered samples of R out of n; it's n choose R. And this, uh, this number is related to something called the binomial coefficient. I just want to show you this because it's really interesting, and you've probably seen it before in the context of Pascal's triangle and computing, um, the coefficients of polynomial expansions.
So if I take, um, maybe I'll switch colors here to blue. If I take, uh, (x + y)^2, or let's say to the nth power; we know (x + y)^2 is x^2 + 2xy + y^2. Let's say I take this to the, uh, to the nth power; I will get an expansion, a sum of terms like x^k y^(n-k), sum from k = 0 to n. And the coefficients of these monomials are going to be n choose k; these binomial coefficients. So, um, and it's called binomial because we're taking an essentially taking two terms, adding them together, and taking them to a power. So this, uh, this polynomial is the sum of all of these monomials where the coefficients are these binomial coefficients. And if you want to compute these, you can compute these using Pascal's triangle. So you've probably seen this before. So if I look at the coefficients, let's say, of, um, (x + y)^2, I'm just going to write this out for a few different numbers: (x + y)^3, uh, (x + y)^4, I'll go up to fifth power, (x + y)^5. And I don't actually want to expand this out; remember how much of a pain it is to like actually expand out a third or a fourth or a fifth order polynomial expansion; it's it's not nice, but it's relatively easy to do this using Pascal's triangle. So, um, the coefficients, and I guess I should have given myself room, (x + y)^1 and (x + y)^0; I really didn't give myself any room here at all. Pascal's triangle is going to start with one for the if I take (x + y)^0; it's just one. (x + y)^1, I get a one outside of x and a one outside of y; those are the coefficients. (x + y)^2, the coefficients are 1, 2, 1; that's x^2 + 2xy + y^2. (x + y)^3, I have x^3 + 3x^2y + 3xy^2 + 1y^3. And notice that this triangle, to get the next term, I'm just adding the two terms above it; so it's really, really easy. (x + y)^4, the coefficients are 1, 4, 6, 4, 1. The coefficients of (x + y)^5 are 1, 5, 10, 10, 5, 1. And so I can read off what the coefficients of this polynomial expansion are from Pascal's triangle; really easy to construct, very cool idea, and it relates to this n choose k binomial coefficients that come up in probability all of the time. And you'll notice this this really cool symmetric structure is quite beautiful; it's very fascinating. But you'll notice that in the limit as I go to, um, n large, if I go to (x + y)^100, this distribution of coefficients is going to start converging to the normal distribution. You can already almost see it happening here; you can start seeing this distribution converging to a normal distribution. In fact, you might even want to code this up in your computer; try a large n, build this triangle, and plot the different rows one after the other after the other, and it's going to converge to this beautiful, uh, Gaussian or normal distribution. Those of you who remember, I think it was The Price Is Right, that Plinko game where you drop a ball and it bounces on this lattice and it falls in these different, uh, different buckets; sometimes that's called a Galton board, or in German, the Galtonbrett. That distribution, if you drop a bunch of beads on this lattice of of pegs and they're bouncing, they will also fall and trickle into this Gaussian distribution. So this Pascal's triangle is how you easily compute the coefficients of an expanded polynomial, but at the end of the day, your those coefficients are these binomial coefficients, n choose k, that come up all the time when we're computing probabilities. So if I want to calculate how many, uh, five-card poker hands I can draw out of a 52-card deck, it's just 52 choose 5. Okay, really easy to compute.
Now, the multinomial distribution is how this generalizes to higher-order distributions, to to more complicated card games. So let's say now I want to deal out two poker hands; I'm going to play with my friend, so there's two five-card hands. How many ways can that happen? And that ends up being a multinomial distribution, which is also pretty easy to compute. So maybe I'll do this in, uh, orange just to keep it interesting. So n objects divided into R classes of size n1, n2, ..., nR. n objects divided into, uh, R classes of size—I'm going to write this precisely—of size n1, n2, ..., all the way up to nR. So if I'm dealing with, you know, two decks of, you know, two hands of cards, I might deal out, um, you know, five and five, um, something like that. And order isn't important. So n objects divided into R classes, and we're going to say order, uh, not important, then the number of samples, the total number of samples, is this object called n choose (n1, n2, n3, ..., nR). And I'll point out, um, I'm going to define what this is; this is not the product; this is not n1 * n2 * n3 ..., it's not n choose this big number; it's a new distribution; it's n choose (n1, n2, n3, n4, ..., ...), okay. And it's defined in the following way: it's defined as n! / (n1! * n2! * ... * nR!). Okay, there's one more assumption I need to tell you about; this assumes that these ns add up to the total n. So n, the whole deck of 52 cards, is being divided into R hands. So imagine you're playing spades; you divide the deck, all the deck into, let's say, four players, then there would be four hands, and all of those would add up to 52 cards. So this assumes that n1 + n2 + ... + nR = n. Okay, it's slightly different if you want to compute how many five-card hands I can deal out of 52, but it's related, okay; the same basic idea here you could use to compute how many five-card hands there are out of 52. This is assuming that you divide the entire set n into these R groups. Okay, good. And this is the formula. Um, I think it's actually helpful to prove that this is the formula, to actually build this formula from, uh, first principles, because it's going to help you get, uh, comfortable with these calculations. So this isn't just, you know, I didn't just pull this formula out of a hat; you can derive this from common sense counting these possibilities.
So kind of the proof of this, the proof; if I actually want to construct this probability, is that this number of things that can happen, n choose (n1, n2, ..., nR), I start by dealing out n1 cards. How many ways can I do that? Well, that's n choose n1; that's just n choose n1. Now that I've done that, I'm going to deal out my second group; that's (n - n1) choose n2. Now that I've done that, I have (n - n1 - n2) cards left, and I'm going to use those to deal out n3; so that's (n - n1 - n2) choose n3, ..., ..., all the way up to, um, the final one, which is, uh, a little hard to write down, but it's (n - n1 - n2 - ... - nR-1) choose nR. And each of these simple, uh, uh, simple arrangements can be calculated; these are each just binomial numbers of how many ways can I deal out a hand of n of n1 cards from a total of n, and so on and so forth. So I can write down the formula for all of these and multiply them together, and you're going to see that they cancel out in a really cool way to get this formula. So this equals—I'm going to give myself a tiny bit more space—this is n! / (n1! * (n - n1)!). This guy is—and I just switch the order of these here to make it a little easier; things will cancel better—this one is just (n - n1)! / (n2! * (n - n1 - n2)!). This guy, and you're going to see these start to cancel. The next ones, these are going to cancel. I'm going to write out the third one: * (n - n1 - n2)! / (n3! * (n - n1 - n2 - n3)!), ..., ..., and eventually I'm left with this term here, which is this factorial divided by; so this is, uh, (n - n1 - n2 - ... - nR-1)! / (nR! * (n - nR)), but this (n - nR), because these all add up to n, is just 0!; 0! is defined as 1; that's just a definition. Okay, the number of ways you can, uh, arrange no elements; there's one way you can arrange no elements; it's like this is the definition; 0! = 1. And that's a whole different idea why that's why that's true. So now you see that this cancels with this, this cancels with this, this cancels with ..., and then this one will cancel, and you get the formula n! / (n1! n2! ... ...). Okay, let's zoom out, and this is called the multinomial distribution. So I can use this to compute lots of things. If I have, um, the product of a factory, if I'm building widgets and some of those widgets are good and some of those widgets are bad, I can divide those into two groups, n1 and n2, and that will be a multinomial distribution; I can compute probabilities of how likely it is to get, you know, some bad elements given a sample using this multinomial distribution. I can use this for, uh, calculating how many hands of spades are there, how many poker hands, things like that, um, using this. And so, um, lots of things you can compute. So let's say that there are, um, an even number of people, let's say 2n people. How many ways can you pair those people off? How many possible pairs can you pair those people off? That's a homework problem; you're going to compute that for some values of n. Or what if you have a committee, you're trying to form, you know, a subcommittee; you have seven people, and you're going to build subcommittees with two people, three people, and three people. How many ways can you form those subcommittees out of your total of seven people? Those are the kinds of things you can compute with the multinomial distribution, and it's a generalization of the binomial distribution; these binomial coefficients; it's really beautiful; it's the coefficients of polynomial expansions; it comes from Pascal's triangle, and the limit for large n, for large sizes, ends up converging to the normal distribution. So this is going to be a whole lecture; we're going to show that you can get this normal distribution from the binomial distribution in a future lecture, but I wanted you to kind of see these here because with these basic, uh, n choose R and the multinomial generalization, you can compute all kinds of neat probabilities for things like cards, um, and, you know, card games and things like that. Okay, thank you.