33 The birthday problem
Imagine you are on the top deck of the Clapham omnibus with nothing in particular to do
but count your fellow passengers going off to work in the early morning. As it is likely
that all the passengers are independent of each other, we may safely assume that their
birthdays are randomly scattered throughout the year. Including you there are only 23
passengers on board. It is not many, but enough to claim there is a better than even
chance that two passengers share a birthday. Do you believe it? Millions do not but it is
absolutely true. Even a seasoned expert in probability, William Feller, thought it
astounding.
The Clapham omnibus is now too small for our needs so we resume the
argument in a large room. How many people must gather in the room so that it
is certain that two people share the same birthday? There are 365 days in a
standard year (and we’ll ignore leap years just to make things simpler) so if there
were 366 people in the room, at least one pair would definitely have the same
birthday. It cannot be the case that they all have different ones.
This is the pigeonhole principle: if there are n + 1 pigeons who occupy n
pigeonholes, one hole must contain more than one pigeon. If there were 365
people we could not be certain there would be a common birthday because the
birthdays could each be on different days of the year. However, if you take 365
people at random this would be extremely unlikely and the probability of two
people not sharing a birthday would be minuscule. Even if there are only 50
people in the room there is a 96.5% chance that two people share a birthday. If
the number of people is reduced still further the probability of two sharing a
birthday reduces. We find that 23 people is the number for which the probability
is just greater than ½ and for 22 people the probability that a birthday is shared
is just less than ½. The number 23 is the critical value. While the answer to the
classic birthday problem is surprising it is not a paradox.
Can we prove it?
How can we be convinced? Let’s select a person at random. The probability
that another person has the same birthday as this person is 1/365 and so the
probability these two do not share a birthday is one minus this (or 364/365). The