The Birthday Paradox

birthday-party-ideasIn probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including February 29). However, 99% probability is reached with just 57 people, and 50% probability with 23 people. These conclusions include the assumption that each day of the year (except February 29) is equally probable for a birthday.

The mathematics behind this problem led to a well-known cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of cracking a hash function.

Birthday_Paradox.svg

A graph showing the computed probability of at least two people sharing a birthday amongst a certain number of people.

The birthday problem asks whether any of the people in a given group has a birthday matching any of the others — not one in particular.

In the example given earlier, a list of 23 people, comparing the birthday of the first person on the list to the others allows 22 chances for a matching birthday, the second person on the list to the others allows 21 chances for a matching birthday, third person has 20 chances, and so on. Hence total chances are: 22+21+20+….+1 = 253, so comparing every person to all of the others allows 253 distinct chances (combinations): in a group of 23 people there are pairs.

Presuming all birthdays are equally probable, the probability of a given birthday for a person chosen from the entire population at random is 1/365 (ignoring Leap Day, February 29). Although the pairings in a group of 23 people are not statistically equivalent to 253 pairs chosen independently, the birthday paradox becomes less surprising if a group is thought of in terms of the number of possible pairs, rather than as the number of individuals. Via Birthday problem

This entry was posted in Uncategorized. Bookmark the permalink.