Transcription
Welcome back. Okay, so in this lecture, I want us to start computing slightly more advanced probabilities, things that might be a little unintuitive, things that might involve some pretty big numbers. And I'm going to illustrate some of these concepts on the birthday problem. So I'm going to state this problem really quickly; um, you've probably heard of it before.
So, uh, if there are n people in a room, if there are n people in a room, how large does n have to be before there is at least a 50% chance that two people share a birthday? There are n people in a room; uh, how large does n need to be for at least—I'm trying to state this kind of precisely—at least a 50% chance of at least two people sharing a birthday? A 50% chance of at least two people sharing a birthday. Now you've probably seen this before. Um, if you have young kids or you know nieces or nephews, maybe you can ask them this problem. And the off-the-cuff, kind of intuitive answer that people usually give is something like 365 divided by 2. That's just kind of the, you know, off-the-cuff uh answer a lot of people give, and that's actually really far from the true answer. So, so this is kind of an unintuitive uh probability problem, and it's also pretty hard to compute using the naive way of adding up the ways things can happen. So I'm going to show you another trick that is going to be useful everywhere, which is it's actually much easier to compute the probability that nobody shares a birthday and then take one minus that probability. The probability that at least two people share a birthday is one minus the probability that no people share a birthday. So that's going to be a really, really important kind of trick to make our counting uh these possibilities easier. And we're also going to illustrate that this is just um kind of unintuitive and hard to count the the naive way. Okay, so let's get into it.
I'm going to draw a picture. Um, so I'm going to illustrate my n people um as kind of just standing in a circle... dot dot dot. Okay, this is just like a cartoon of n people standing in a circle uh in a room trying to compare birthdays. And so the first thing I want to do here is just count how many comparisons are there. So let's say that this is person one, person two, person three, four... dot dot dot. And what I'm really trying to do is I'm going around the room looking at unique uh birthday comparisons. So if if there are if two people share a birthday, it could be person one and two, person one and three, one and four... dot dot dot. It could be person two and three, two and four, three and four, and so on and so forth. So one way to do this would be to literally have everybody kind of pair off in every unique combination and just compare their birthdays. And if you uh calculate this number, so there's n people in a room, let's say this is person n, then the number of comparisons: person one compares with n minus one people, person two compares with n minus two people because they've already compared with person one, person three uh sorry, person person one compares n minus one, two n minus two, person three compares with n minus three, and so on and so forth... dot dot dot until the last person has already compared with everybody, so they don't need to compare with anyone else. So all of these integers plus two plus one plus zero, and this is actually an easy formula to compute. Um, there's an old story that Gauss computed this uh when he was three. His parents were maybe getting fed up with him, so his dad sent him off to a corner: add up all of the numbers from 1 to 100. He thought this would keep Gauss busy for a couple of hours. Gauss came back moments later with the formula, which is uh n * n - 1 / 2. Okay, good. That's how many comparisons, unique comparisons, you would have to do to just brute force check um all all to all comparisons. And this gives you some intuition for why this number is much, much smaller than 365 divided by 2. So this number actually gets big faster. So if n is about 20, so for n equals 20, this number of comparisons, this number of comparisons is, I don't know, 20 divided by 2 is 10 * 19 is 190. That's already bigger than 365 divided by two. So, you know, there we're looking for a 50% chance of two people sharing a birthday. So you can imagine with order of magnitude, rough order of 20 people, you should have enough comparisons to get close to 365 divided by two, um a 50% chance of some of these comparisons uh resulting in the same birthday. Okay, this is very heuristic; this is not how you compute the probability. There are a lot of things that can go wrong because each of these unique uh comparisons, if I do all of these 190 unique comparisons for 20 people, I might end up double or triple or even quadruple counting because notice that this says that it's the probability for at least two people sharing a birthday. So there could be three people in this room that share a birthday, or four people that share a birthday, or five, and so I could be double counting a lot uh in this number. So, so the answer is not n equals 20 or 19. We have to precisely compute um the the probability of at least two people sharing the birthday. Okay, good.
Now, uh, the way you actually do this, the easy way of doing this, and maybe I'll just do this uh in red over here, I'll I'll kind of start the problem, is you say that the probability that um kind of—I'm going to use shorthand often times—the thing inside my probability is shorthand, so it's the probability of an event. So the probability that at least two people, greater than or equal to two people, share a birthday, this is equal to one minus the probability that nobody shares a birthday. Okay, so if two people share a birthday, three people share a birthday, four people, five people, six people, so on, that's that's a set of events that that add up to this. The complement of that set, uh if if you don't share if two people don't share a birthday, three people don't, four people don't, etc., etc., the the complement of that set of of events of of things that could happen is that no people share a birthday. And so probability that nobody shares a birthday plus the probability that at least two people share a birthday has to add up to one. Okay, this is like the law of total probability essentially. And it turns out that this is much easier to compute, much easier to compute than this. Okay, so in a minute I'm going to show you how to compute the probability that no one shares a birthday; that's really easy. Just roughly sketching through the probability that two people or three people or four people share a birthday, this one's challenging; this one is hard to compute. And I'll just roughly, roughly show you what this means. So the probability that greater than or equal to two people share a probability is, you know, equal to the probability that, so the probability that greater than or equal to two share is equal to the probability that exactly two people share, the probability that exactly two plus the probability that exactly three plus... dot dot dot dot dot. Okay, and it's even worse than this because I could have, what if these two people shared their birthday and then these three people shared their birthday and then these five people shared their birthday? So I'd essentially have to—there is a way of writing this out, and it's a mess, and I'm trying to keep these uh videos kind of short, so maybe as a homework exercise, try to actually enumerate all of the possible ways that this can actually happen, that you can get exactly equal to two, exactly equal to three, exactly equal to four, and then see am I missing anything? Are there other terms in here? Plus other terms. Try to enumerate how many ways there are to get exact to get greater than or equal to two people sharing a birthday, and I think very quickly you'll realize that you're going to get these nested horrific sums of of cases. Like, first thing I'm going to do is I'm going to say, okay, person one's birthday—we're just going to say that that's a that that's a date—so then I'm going to go and calculate what's the probability that per person two has the same birthday. Okay, then I'm going to say what's the probability that person three has the same birthday as either of them, and that you know given that probability of one and two was not the same birthday. So you're going to get all of these like mixed if-then statements to try to count these probabilities. This is a mess. Okay, that's kind of a a self-guided study problem is try to actually write down all of these combinations; it's going to be a mess; it's going to take you a long time. Very hard to compute. Let's do it this way: the probability that no one shares a birthday—that's actually much, much easier.
So the probability that no one shares—and this is kind of like those um that poker hand example—so what we're going to do is we're going to essentially say that the first person's birthday can be anything, okay, because it doesn't matter what the first person's birthday is. Once we've determined the first person's birthday, let's say it's uh June 17th. Now we know that the second person cannot have the same birthday as the first person. Okay, so given—I'm going to draw a little picture here—I have like the first person's birthday, the second person, the third person... dot dot dot all the way up to the nth person. And this person can choose from any one of 365 days, and it doesn't matter. Okay, so this is person one. Now person two, out of all of the 365 days that they could have, 364 of those days are mean that they will not share a birthday with person one. So there's 364 out of 365 possible um, you know, probability that person two will not share a birthday with person person uh person one. Now person three, these first two birthdays have been have been uh are already chosen; this one was June 17th, let's say this one is October 3rd. So now the third person, out of all 365 days of the year, this person has 363 possible days that they can choose from. So if you randomly assign person three a birthday, 363 of those choices out of 365 will not cause them to have an overlap with person one or person two. And you can keep going and going: we have 362 left out of 365, 361 left out of 365... dot dot dot dot... finally 365 - n + 1 over 365. And I can fill in here for person one, out of all of the 365 days of the year, all 365 of those days don't cause person one a conflict because they're the the first person; they're not being compared. Person two compares with person one, person three compares with person one and two, and so on and so forth. Person one can pick all of those 365 days. So the probability that no one shares is essentially this product here. This is the probability that no one shares um a birthday out of um n people. And you could make this a little more formal; you could say, well, this is the number of ways that you can have unique birthdays, number of unique uh birthdays divided by the total number of choices possible. Now the total number of choices is obviously just 365 to the n; all of these n people could have any birthday. The total number of birthdays is 365 to the n; that's the total number we're dividing by. The number of unique birthdays where no one shares a birthday is this product here; it's uh maybe I'll write this in orange: this number of unique birthdays is 365 factorial / 365 - n factorial. And remember this is that number that we had that was um if you have sampling without replacement, right? So everyone's sampling a birthday, but for them to be unique, when someone picks June 17th, all of these have to sample from the remaining 364, and if this person picks October 3rd, the remaining people have to sample from the remaining 363. The pool gets smaller for us to have unique birthdays. So these are essentially the numbers I'm dividing by. So my formula is really simple: probability no one shares a birthday is 365 factorial divided by 365 - n factorial * 365 to the n. Okay, and this is something that's computable; this is very, very hard to compute; this is very, very easy to compute. Okay, and so this is actually going to be a homework problem for you is I want you to actually code this up for n equals 1, 2, 3. Write a for loop for, you know, n equals 1 until some condition is met, and you're actually going to compute this object here, and you're going to compute the probability as n increases. And what you're going to find is that very quickly, for about—in fact, for exactly n equals 23—at n equal 23, the probability that no one shares a birthday drops below 50%, and so the probability that at least two people share a birthday goes above 50%. So for n equals 23, this number drops below 50%, below 0.5, meaning this number goes above 0.5. So this is the exact number, and you're going to write a for loop uh to compute this number for all of those n, you're going to plot that probability, this probability and this probability, and you're going to find that n equals 23 is where this crosses the 50% line. And so if you were going to like turn in a homework assignment, I might ask you what is the probability, what's the exact probability when n equals 20? Clearly it's going to be a little bit less than 50%, not not a ton less, but a little bit less.
Okay, now you can try uh this on your calculator. So I didn't, you know, I'm not coding this up right now; that's a homework problem for you, but can go uh and try to do this on my calculator. And what you're going to find actually is that this number, you can't type this into your calculator; you can't type in 365 factorial divided by because immediately you're going to get an error because this number is way, way, way too large; this number is bigger than your calculator can easily represent in all of its, you know, bits of uh representation. So you can't actually write this down in your calculator. Now you could try to go to Google and type type this in uh let's do that. Okay, Google says it's an undefined number. Google's apparently not as smart as I thought it was. Uh, you can go to Wolfram Alpha and you can type this in. So if you actually type this into Wolfram Alpha, uh you actually get a number. Let me just type this in. Okay, so the probability for 20 days is about .589, so n equal 20 gives a probability of no shared of about [Music] .589, which means that the probability that two people share a birthday in a room full of 20 is about 40%, 41%. So actually pretty good odds, but not 50. So you can compute this in Wolfram Alpha; you can uh write a for loop. If you're going to write a for loop, like you can't just type this in easily and say go because it might it might error out if it tries to compute this number first; it's too big; it's going to error out. So what I would actually do is in my for loop I would actually multiply by the next number in the sequence; this is the formula you actually want to use when you're computing it. I'd say for, you know, k = 1 to n, this is my first probability, then for n equals 2, I multiply it by this one; this is a tractable number; it's close to one. Then for n equals 3, I multiply it by this number; this is a reasonable number; it's it's close to one. And so as you multiply up, all of these numbers are reasonable, and it's much easier to compute than trying to compute it from this formula directly. Okay, so that's the homework problem: uh, write a for loop, check these different probabilities, make some plots, um, you know, but it gives a couple of important ideas here: probabilities are sometimes unintuitive. So the way you actually count things um it might be really hard to compute the thing you actually want. Actually counting the probability of greater than two people sharing a birthday is very hard; there's all of these weird edge cases: maybe three people share a birthday, maybe four people, maybe two people share a birthday and another two people share a birthday. There's all kinds of weird stuff that can happen; very hard to compute. Very often in those cases where it's hard to compute something, it's easy to compute the complement of that thing not happening. And so that's what we did here; it's a very simple formula to compute the probability of no shared birthdays, which allows us to get this really nice easy expression.
Parting thoughts: you should always be asking yourself what assumptions did I make? So obviously we are assuming that there's no leap years; um, we're assuming that there's exactly 365 days; no one can have a birthday on February 29th. If you in the audience have one, I'm sorry; uh, please write something in the comments so we can see how many of you there are. Um, we're also assuming that all days are equal, which is clearly not true; some seasons people uh have more babies than other seasons. So take your birthday and subtract nine months; um, if you're a mid-November baby, maybe you have a Valentine's Day uh conception. And there are all of these different kind of biases in these probabilities, like all 365 days are not equal, so there will be these kind of hot spots where it's more likely for people to share a birthday than others. And I want you to think about how would these calculations change? What data would I need to make a more refined estimate? Um, if I was in a room with 23 people and five people had the same birthday, would I think that this was a random sample, but I think that that's normal? What are the chances of that, you know, given these assumptions that I made? Okay, uh, code it up, try it yourself; it's kind of a fun problem to test your intuition. Thank you.