062 The Birthday Paradox

Adapted from the wikipedia article on "Birthday Paradox":

In probability theory, the birthday paradox states that given a group of 23 (or more) randomly chosen people, the probability is more than 50% that some pair of them will have the same birthday. For 57 or more people, the probability is greater than 99%, although it cannot be exactly 100% unless there are at least 367 people

One way to intuitively accept the birthday paradox is to realize that there are many possible unordered pairs of people whose birthdays could match. Specifically, among 23 people, there are C(23,2) = 23 × 22/2 = 253 pairs, each of which is a potential candidate for a match. Looked at in this way, it doesn't seem so unlikely that one of these 253 pairs yields a match.

The key to understanding this problem is to think about the chances of no two people sharing a birthday: what are the chances that person 1 has a different birthday from person 2 and that person 3 has a different birthday again and person 4, etc. As you add each person to the room, it becomes less and less likely that their birthday isn't already taken by someone else. If one has a sample space of n people, the first person has 365 possible birthdays to choose from. The 2nd person would have only 364, the 3rd would have 363, and so on and so forth. This would be compared with any person being able to have any birthday with no restrictions (in short, all people have 365 possible birthdates.)

The probability of having two people having the same birthday in a sample space of n people is shown below:

n p(n)
10 12%
20 41%
23 50.7%
30 70%
50 97%
100 99.99996%
200 99.9999999999999999999999999998%
300 (1 − 7×10^73) × 100%
350 (1 − 3×10^131) × 100%
366 100%

Well, this paradox shocked me at first, and after a few observations, I found this to be really true, in a few groups of about 20 people, the chances that two people share the same birthday is higher that we'd like to think, one of the wonders of Maths, I would say.