The birthday problem - rFronteddu/general_wiki GitHub Wiki

The birthday problem

The birthday problem in probability theory explores the likelihood that in a group of n randomly selected people, at least two of them will share the same birthday. It's a classic problem that demonstrates how human intuition often underestimates the probability of certain events.

The Birthday Problem

The core question of the birthday problem is:

  • How large does the group of people need to be for there to be a better than even chance (greater than 50%) that at least two people in the group share the same birthday?

The Birthday Paradox

  • The surprising result, known as the birthday paradox, is that you only need 23 people in a room for there to be a greater than 50% chance that at least two of them share a birthday.
  • This result is counterintuitive because 23 people seem like a small number compared to 365 possible birthdays, but the probability rises quickly as the group size increases.

Explanation

  1. Calculating the Probability:
  • To find the probability that at least two people share a birthday, it's easier to first calculate the opposite probability: that no one shares a birthday.
  • For the first person, there are 365 possible birthdays.
  • For the second person, to avoid matching the first person's birthday, there are 364 possible different days.
  • For the third person, to avoid matching the first two, there are 363 days, and so on.
  • The probability that all n people have different birthdays is:
    • P(no shared birthdays) = $\frac{365}{365} * \frac{364}{365} * \frac{363}{365}$ * ... * $\frac{365-n+1}{365}$
  • To get the probability that at least two people share a birthday, subtract this from 1:
    • P (at least one shared birthday) = 1- P(no shared birthdays)
  • for n = 23
    • When you compute this for 23 people, the probability of no shared birthdays is approximately 49.3%.
    • This means the probability that at least two people share a birthday is about 50.7%, which is just over 50%.

Why is it Counterintuitive?

  • Large Number of Pairs: The key reason for the paradox is the number of pairs of people you can form in a group. With 23 people, you can form $\binom{23}{2}$ = 253 unique pairs.
  • Each pair is a change for a shared birthday, so even though there are 365 possible birthdays, the large number of comparisons make a match likely.