The Birthday Problem and Other Chance Encounters The Birthday Problem is easy to understand, yet the answer seems counter-intuitive. It is normally stated as: How many randomly-chosen people are needed so that the probability that there exists at least one pair who share the same birthday is greater than 50%? The following needs to be made clear: "Birthday" means month and day only, not the year. "Chosen at random" means the people are chosen with no intentional bias. For example, one would avoid choosing twins since they share the same birthday. "At least one pair" leaves open the possibility more than one pair may exist, or three people share a common birthday, or any combination thereof. More importantly, "at least one pair" follows the rules of logical quantifiers, as will be seen in a moment. The leap day is not counted, or, if one insists, the leap day February 29 is "paired" with March 1. This does not change the outcome of the problem at all, so whether to include the leap day or ignore it makes no difference. It is difficult to account for all possible ways birthdays can be shared, e.g. one pairing, more than one pairing, three or more people sharing a common birthday, and so on. All of these cases fall under the umbrella of "at least one shared birthday". The negation of "at least one" is "no/none", and vice-versa. It is easier to find the probability that no one shares a birthday with any other in the group. The tactic is to find the minimum number of people necessary so that the probability that no one shares a birthday is below 50%. Thus, the negation, "at least one pair shares a birthday", will be above 50%. The Brute Force Method Start with one person. That person has a birthday. A second person is randomly chosen. The probability that person does not share the same birthday as the first person is 364/365. A third person is randomly chosen. Since the first two people have "used up" two of the possible days, the probability that this third person does not share a birthday with the any of the first two people is 363/365. Thus, the probability that among these three people, there are no shared birthdays is the product (364/365)(363/365), which is about 0.992, or 99.2%. Therefore, the probability that there is a shared birthday among the three people is 1 − 0.992 = 0.08, or 0.8%, slightly less than 1 percent. The process continues. Assuming there are no shared birthdays among the first three people, then a randomly-chosen fourth person has a probability of 362/365 of having a different birthday than any of the first three, and the probability that among these four people, there are no pairs who share a common birthday is the product (364/365)(363/365)(362/365), which is about 0.984, or 98.4%, so that the probability that among these four people, there exists at least one pair who do share a common birthday is 1 − 0.984 = 0.016, or 1.6%. Now that the structure of the problem is more evident, it can be generalized. The structure is summarized in the table below: No. of people (n) Probability of no shared birthday Prob of at least one shared birthday 2 364/365 = 0.997, or 99.7% 1 − 0.997 = 0.003, or 0.3% 3 (364/365)(363/365) = 0.992, or 99.2% 1 − 0.992 = 0.008, or 0.8% 4 (364/365)(363/365)(362/365) = 0.984, or 98.4% 1 − 0.984 = 0.016, or 1.6% 5 (364/365)(363/365)(362/365)(361/365) = 0.973, or 97.3% 1 − 0.973 = 0.027, or 2.7% To generalize this structure, note that for a given value n, the probability of no shared birthdays is P(no shared bithdays) = (364/365)(363/365)(362/365) ... . There is actually another factor in this string: 365/365 (which is 1). This represents the first person. Including it will make the subsequent equation using permutations more sensible. Thus, P(no shared bithdays) = (365/365)(364/365)(363/365)(362/365) ... .   (n factors) Therefore, the probability that among n people, there are no shared birthdays is P(no shared birthdays) = P(365,n)/365n. And finally, the probability that there exists at least one pair of people in the group who share a birthday is 1 − P(365,n)/365n. For now, to solve for the desired n value means plugging in values of n until the second column's value drops below 0.5, so that the third column's value rises above 0.5. This magical value n is 23. In any group of 23 randonly-chosen people, the probability there exists at least one pair who share a birthday is above 50% (it's actually 0.507, or 50.7%). Below is a spreadsheet showing how often a shared birthday occurs among a group of 23 people. (click to enlarge) Finding n analytically Is there a way to find n without having to plug in values until the desired answer is found? Approach this problem from a different angle. There are actually two values of interest: n, the number of people, and k, the number of pairings of two people chosen from this group of n people. These values are related by the combination equation: C(n,2) = k. In other words, "n people, chosen 2 at a time, is k". The value k represents the number of opportunities of possible pairings. For example, in a group of 4 people, there are C(4,2) = 6 opportunities for a pairing. If the group consists of Al, Bob, Chuck and Dave, then there are 6 pairings: Al & Bob, Al & Chuck, Al & Dave, Bob & Chuck, Bob & Dave, and Chuck & Dave. Note that the number of possible pairings (k) is always greater than the number of people (n) in the group. The method is to find k first, then work backwards to find n. Among any two people, the probability they do not share a birthday is 364/365. If there are k possible pairings of people, then it is desired that each pair of people not share a birthday, which is the quotient 364/365 multiplied to itself k times, that is, (364/365)k. And this value is to be slightly below 0.5. Set (364/365)k equal to 0.5, and solve for k using logarithms: (364/365)k = 0.5,   so that   k = ln(0.5)/ln(364/365) = 252.65. Since k must be an integer, then k is 253. Note that (364/365)252 = 0.5009 and that (364/365)253 = 0.4995, which confirms the calculation. Since (364/365)k is to be below 0.5, then k = 253 is the desired number of pairings for which there are no shared birthdays. Now find n using the equation C(n,2) = k. In general, C(n,2) = n(n − 1)/2. Set this equal to 253: n(n − 1)/2 = 253. Multiplying by 2 gives n(n − 1) = 506. Distributing to clear parentheses and combining all terms to one side gives n2 − n − 506 = 0. This is quadratic, and factoring gives (n + 22)(n − 23) = 0 Solving, n = −22 or n = 23 (The negative value is not considered). Thus, n = 23 randomly-chosen people is the minimum number of people necessary so that the probability at least one pair share a birthday is above 50%. What is the minimum number of people needed so that the probability of at least one pair sharing a birthday is 90%? Following the same method, first seek the number of pairings, k, so that (364/365)k = 0.1, where 0.1 represents 10%, the probability that no pairing share a common birthday. This k is (364/365)k = 0.1,   so that   k = ln(0.1)/ln(364/365) = 839.29. Thus, k = 840. Now, set C(n,2) = 840 and skip to the quadratic step: n(n − 1)/2 = 840,   so that   n(n − 1) = 1680,   which gives   n2 − n − 1680 = 0. Using the quadratic formula, n = [−(−1) ± √((−1)2 − 4(1)(−1680))]/2, which gives n = 41.49 and n = −40.49 as roots. The negative root is ignored. Note that n = 41.49 people does not make sense. It must be either 41 people or 42 people. Using the permutation notation (from above) to check n = 41 gives P(365,41)/36541 = 0.097, and for n = 42 gives P(365,42)/36542 = 0.086. In this case, it is desired that P(365,n)/365n be below 0.1 "for the first time", and this happens when n = 41. As a check, when n = 40, P(365,40)/36540 = 0.109, which is above 0.1. Thus, in any group of 41 randomly-chosen people, the probability there exists at least one pair of people with a shared birthday is over 90%. Below is a table in Excel that shows the probability of no shared birthdays, then the probability of at least one shared birthday, for a given number of people. At 23 people, the probability of a shared birthday is 50.7%. Interestingly, at 27 people, the probability rises above 60%, at 30 people the probability rises above 70%, at 35 people it hits 80% and at 41 people, it hits 90% as we just noted above. At 68 people, the probability of a shared birthday is nearly 99.9%. (click to enlarge) In a group of 365 people, the probability of at least one shared birthday is just a smidge below certain, as it is possible each of the 365 people has a different birthday from everyone else. But at 366 people, the probability of at least one shared birthday is certain. This should be intuitive. If the first 365 people all had different birthdays, then the 366th person must have a birthday on a day already taken by one of the first 365 people. This is called the "pigeonhole principle".