Birthday Problem - An Upper Bound

An Upper Bound

The argument below is adapted from an argument of Paul Halmos.

As stated above, the probability that no two birthdays coincide is

As in earlier paragraphs, interest lies in the smallest n such that p(n) > 1/2; or equivalently, the smallest n such that p(n) < 1/2.

Using the inequality 1 − x < e−x in the above expression we replace 1 − k/365 with e−k/365. This yields

Therefore, the expression above is not only an approximation, but also an upper bound of p(n). The inequality

implies p(n) < 1/2. Solving for n gives

Now, 730 ln 2 is approximately 505.997, which is barely below 506, the value of n2 − n attained when n = 23. Therefore, 23 people suffice. Solving n2 − n = 2 · 365 · ln 2 for n gives, by the way, the approximate formula of Frank H. Mathis cited above.

This derivation only shows that at most 23 people are needed to ensure a birthday match with even chance; it leaves open the possibility that, say, n = 22 could also work.