Birthday problem

Fruit, Vegetables and Grain NCI Visuals Online

The Birthday problem is a famous problem in probability theory that concerns the probability that, in a set of randomly chosen people, some pair of them will have the same birthday. The problem is often used to illustrate the counterintuitive nature of probability, as the probability of a shared birthday becomes surprisingly high even with a relatively small number of people.

Problem Statement

The classic form of the Birthday problem can be stated as follows: In a group of \( n \) people, what is the probability that at least two people share the same birthday? For simplicity, it is usually assumed that there are 365 days in a year and that each person's birthday is equally likely to be any of these 365 days.

Calculation

To solve the Birthday problem, it is easier to first calculate the probability that no two people share the same birthday and then subtract this probability from 1.

No Shared Birthday

The probability that the first person has a unique birthday is 1 (or 365/365). The probability that the second person has a different birthday from the first person is 364/365. For the third person, the probability that their birthday is different from the first two is 363/365, and so on.

The probability \( P(n) \) that all \( n \) people have different birthdays is given by: \[ P(n) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{365-n+1}{365} \]

This can be simplified to: \[ P(n) = \frac{365!}{(365-n)! \cdot 365^n} \]

Shared Birthday

The probability that at least two people share the same birthday is: \[ 1 - P(n) \]

Example

For a group of 23 people, the probability that at least two people share the same birthday is approximately 50.7%. This result is surprising to many because 23 is much smaller than 365, yet the probability is already greater than 50%.

Generalizations

The Birthday problem can be generalized to other scenarios, such as the probability of at least two people sharing the same birthday in a group of \( n \) people when there are \( d \) possible birthdays, or the probability of at least \( k \) people sharing the same birthday.

Applications

The Birthday problem has applications in various fields, including cryptography, where it is related to the birthday attack on hash functions. It is also used in statistics and combinatorics to illustrate the principles of probability.

See Also

• Birthday attack
• Probability theory
• Combinatorics
• Cryptography