Birthday paradox

The birthday paradox states that if there are 23 people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. This means that in a typically-sized school class, where the 'paradox' is often cited, an even higher probability often applies. For 60 or more people, the probability is already greater than 99%. This is not a paradox in the sense of 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 than 50:50. Calculating this probability (and related ones) is the birthday problem. The mathematics behind it has been used to devise a well-known cryptographic attack named the birthday attack.

Implications of inequalities

For variations of the birthday scenario in broader contexts, a different flavor of argument is essential. The argument below, exploiting important inequalities, is adapted from an argument of Paul Halmos{{rf|1|Halmos}}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The probability of coincident birthdays, p(n), is one minus the probability that no two birthdays coincide, 1 − p(n). The usual argument given above says that p(n) is the product

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:prod_{k=1}^{n-1}left(1-{k over 365} ight) .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

We are interested in the smallest n such that p(n) > 1/2; or equivalently, the smallest n such that p(n), shown here, is less than 1/2. The general idea is to repeatedly replace the complicated product by simpler expressions, each of which is no smaller in value. If our final simple expression is less than 1/2, then the true value must be also. Results obtained this way may be overly conservative, in the sense that a smaller value of n might suffice; but they are always safe.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Because of the inequality of arithmetic and geometric means, we have

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:sqrt{prod_{k=1}^{n-1}left(1-{k over 365} ight)} < {1 over n-1}sum_{k=1}^{n-1}left(1-{k over 365} ight).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Here the left side is the geometric mean (root of a product) and the right side is the arithmetic mean (division of a sum). Neither side is greater than one, so raising both sides to the power n−1 does not change the inequality. Thus our first replacement is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:prod_{k=1}^{n-1}left(1-{k over 365} ight) < left({1 over n-1}sum_{k=1}^{n-1}left(1-{k over 365} ight) ight)^{n-1}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

That is, we substitute the sum raised to n−1 for the product. The sum splits into (∑ 1) − (∑k)/365; and since the first is a constant (summing to n−1) and the second an arithmetic progression (summing to n(n − 1)/2), we can replace the sum by an exact expression:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:left({1 over n-1}sum_{k=1}^{n-1}left(1-{k over 365} ight) ight)^{n-1} = left(1-{n over 730} ight)^{n-1} .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Our next substitution uses the inequality 1 − x 

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:left(1-{n over 730} ight)^{n-1} < left(e^{-n/730} ight)^{n-1} .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

By the usual laws of exponents, (ea)b = eab; so we can simplify again:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:left(e^{-n/730} ight)^{n-1} = e^{-(n^2-n)/730} .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Noting that e−x = 1/ex, we see that e−x < 1/2 is the same as ex > 2 (reciprocating reverses the inequality). We can take logarithms of both sides without changing the ordering; thus our original inequality demand, that the probability product be less than 1/2, finally simplifies to the much more manageable

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:n^2-n > 730log 2 ,! .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(Here "log" refers to the natural logarithm.) Now 730 log 2 is approximately 505.997, which is barely below 506, the value of n2 − n attained when n = 23. Therefore, 23 people suffice.

Related Topics:
Log - Natural logarithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note that Halmos' derivation only shows that at most 23 people are needed to ensure a birthday match with even chance; since we haven't studied how sharp the given inequalities are, the argument leaves open the possibility that, say, n = 22 could also work.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~