Birthday paradox

The birthday paradox states that if there are 23 people in a room then there is a slightly more than 50/50 chance that at least two of them will have the same birthday. For 60 or more people, the probability is greater than 99%. This is not a paradox in the sense of it leading to a logical contradiction; it is a paradox in the sense that it is a mathematical truth that contradicts common intuition. Most people estimate that the chance is much lower.

Estimating the probability

Calculating this probability (and related ones) is the birthday problem. The theory behind it was described in the American Mathematical Monthly in 1938 in leap years and twins, and assume that the 365 possible birthdays are equally likely. The trick is to first calculate the probability that the n birthdays are different. This probability is given by

<math>p = \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365}<math>

because the second person cannot have the same birthday as the first (364/365), the third cannot have the same birthday as the first two (363/365), etc. Using factorial notation, this expression can also be written as

<math>p = { 365! \over 365^n (365-n)! }<math>

Now, 1 - p is the probability that at least two persons have the same birthday. For n = 23 one obtains a probability of about 0.507.

By contrast, the probability that someone in a room of n other people has the same birthday as you is given by

<math> 1- \left( \frac{364}{365} \right)^n <math>

which for n = 22 gives only about 0.059, and would need n to be at least 253 to give a value over 0.5.

The birthday paradox in its more generic sense applies to hash functions: the number of N-bit hashes that can be generated before probably getting a collision is not 2^N, but rather only 2^N/2. This is exploited by birthday attacks on cryptographic systems (see cryptographic hash function).

A mathematical, as opposed to numerical, view of the birthday paradox

In his autobiography, Paul Halmos wrote:

"A good way to attack the problem is to pose it in reverse: what's the largest number of people for which the probability is less than 1/2 that they all have different birthdays? .... the problem amounts to this: find the smallest n for which

<math>\prod_{k=0}^{n-1}\left(1-\frac{k}{365}\right)<\frac{1}{2}.<math>

The indicated product is dominated by

<math>\left(\frac{1}{n}\sum_{k=0}^{n-1}\left(1-\frac{k}{365}\right)\right)^n

<\left(\frac{1}{n}\int_0^n\left(1-\frac{x}{365}\right)\,dx\right)^n =\left(1-\frac{n}{730}\right)^n

The asserted domination comes from the celebrated relation between the geometric and arithmetic means; the next inequality comes from the definition of the definite integral, and the last one from 1 − x < e^−x. .... The reasoning is based on important tools that all students of mathematics should have ready access to. The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What calculators do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories."

An (non-fatal) error in Halmos' argument (whose general idea is right)

In the argument of Halmos quoted above, the inequality

<math>\sum_{k=0}^{n-1} \left(1-{k \over 365}\right)

<\int_0^n \left(1-{x \over 365}\right)\,dx<math>

is incorrect, as one may readily check. But the argument can be fixed. In the product

<math>\prod_{k=0}^{n-1}\left(1-{k \over 365}\right)<math>

the first factor is equal to 1, and may therefore be discarded. Then we have

<math>\prod_{k=1}^{n-1}\left(1-{k \over 365}\right)

<\left({1 \over n-1}\sum_{k=1}^{n-1}\left(1-{k \over 365}\right)\right)^{n-1}<math>

<math>=\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^2-n)/730}.

<math>

The first inequality above is a case of the inequality of arithmetic and geometric means. The second inequality comes from 1 − x < e^−x.

The value of the last expression is less than 1/2 if and only if

<math>n^2-n>730\log_e 2\cong 505.997\dots<math>

where "log_e" means the natural logarithm. This falls just barely short of 506, and as luck would have it, 506 is one of the values of n² − n ; it attains that value when n = 23.