[MUSIC] Consider the following problem. We have 28 randomly chosen people, and we are interested in the following pairs (i,j), such that the i-th person with number i has a birthday on the same day as the person with number j-th, and we are interested in the number of such pairs. We would like to show that the expectation of this number is greater than 1, that means that on average, we will have at least one pair of people with the same birthday. Okay, let's discuss in more details what are these pairs, and what are we computing. If there are two people with the same birthday, then they form a pair of people with birthday on the same day. So they contribute one to the number of pairs we are interested in. If there are three people with the same birthday, they will form three pairs. And so if you have three people, then there is a pair of the first one and the second one, the second one and the third one, and a pair of the first one and the third one. So these people who contribute three to the number of pairs we are interested in, so that's what we are going to compute. Okay, the problem looks a bit surprising. So there are just 28 people, and we are saying that it is fair to expect. It would be good to expect that there are two of them with the the birthday on the same day, but we will show that this is in indeed the case. Okay, on the other hand, we have to formalize the problem a little bit. So the current statement is not completely formal. We assume for this problem that birthdays are distributed uniformly among all days of the year. And we assume that there are 365 days of the year for simplicity. We will not discuss it, but actually if our redistribution of our birthdays among days of the year is not uniform, which is actually the case in real life, then this expectation we're looking at will all increase. But for simplicity, we consider a uniform distribution among all days. And also, we have to specify whether we choose people independently and uniformly. Randomly here, means that we just pick random people different on birthdays. Okay, let's proceed to the proof. And of course we will use the linearity of expectation here, to have a bound on the expectation we are looking at. Let's denote the number of pairs of people with the same birthday, the number we're looking at, by f, this is a random variable. And let's introduce our more random variables. Let's enumerate people from 1 to 28. And let's consider a random variable g sub ij. It will be equal to one if persons i and j have birthday on the same day, and otherwise, it will be equal to 0. And now, an important observation. f is equal to the sum of all gij over all unordered pairs of i and j. Now, that's an Important observation you will make. And note that this is the observation that will help us to use linearity, we break our complicated random variable f into the sum of more simple random variables. But let's see why this is true, why f is equal to the sum of all these random variables. And let's consider an example, it's easier to see an example. Suppose, we have five people, 1, 2, 3, 4, 5, and let's just list all of the pairs. There are five, choose two pairs, which is ten. And here, they are all listed. First, we list pairs which contain person number 1, then we list pairs that contain person number 2. Then we list pairs with contained person number 3, and that wasn't counted before. And there is finally one person, one pair that doesn't contain anyone from 1 in 1, persons 1, 2, and 3. This is a pair 4 and 5, so we have ten pairs. And suppose the following happens. The first person and the third person has the same birthday, and the fourth and fifth person have the same birthday. Okay, so then the values of our new random variables are like this. So we are all 0s except two cases, except g1,3 and g4,5. Okay, note that f, in this case, is equal to 2. There are 2 pairs of people that have birthday on the same day. And note that, on the other hand, the sum of all gij is also equal to 2, because exactly 2 of them are equal to 1 and others are equal to 0. So in this case, it is easy to see that f is equal to the sum of all gij. It is just the number of pairs, such that gij = 1. And if we sum up all gij, we will obtain exactly the same number. So that's why we have our problem then, we will use. Okay, now let's get back to the proof. We know now with the expectation of f is bilinearity, is equal to the expectation, to the sum of all expectations of all gij, overall pairs {i, j}. And there are two things left, we need to compute these expectations with expectations of simpler random variables. And second, we need to count how many pairs of i and j do we have. Okay, let's proceed to the first task. Let's compute the expectation of individual gij. And it is very easy to compute because this will look as only two outcomes, 1 and 0. And the first outcome happens in the probability 1 over 365. And with the second one happens with probability 1 minus 365, but that doesn't matter since the second outcome is 0. So it doesn't matter by which number we multiply 0, and the expectation will be 1 over 365. So now, why the probability of value 1 is equal to 1 over 365? We can just compute it directly. How many possible outcomes are there for the birthday of two different people? Each of them can have a birthday in 1 of 365 possible days. If you have a pair of people, then there are 365 times 365 possible outcomes. And note that only 365 outcomes are good. Only 365 possibilities for them to have a birthday on the same day. We have to pick one day and then they have to have birthday, both of them should have have birthday on this day. So we divide 365 by 365 squared, and we obtain our probability. So we have computed the expectation of gij, and now we can proceed to the second part. How many pairs of i and j do we have? So there are 28 people in total, and we are interested in an ordered pairs of people. These are combinations, and there are 28 chose to first, which is 25 x 27 divided by 2 = 378. So there 378 possible pairs of 28 out of 28 people. Let's briefly recollect why it's 28, choose to. Here is a short reminder. For the first person, we have 28 options, and there are 28 possible people. Now, we would like to have a pair of different people. So for the second person, there are only 27 options left. Finally, we have counted each pair twice. If we have a pair of the first person and the second one, we have counted them twice. First, when we repeat the first one, the first person first and the second person second. And the second time, we put the second person first and the first person second. So we've counted each pair twice so we have to divide by two, and here is why the number of pairs is equal to 28. Okay, now let's get back to our proof and finally, we have everything we need. We know that the expectation of f is the sum of expectations of gij for all pairs of i and j. We know the expectation of each gij, it is equal to 1 over 365. And we know that there are 378 pairs of people. So overall, we have to add up 1 over 365 as many times as there are pairs of people. So overall, we have 378 divided by 365 which is greater than 1. That's what we needed to show. So we computed the expectation of our number, and it turned out to be greater than 1. [MUSIC]