3.11 Problem 11: Birthday Paradox

For this problem, it is easier to calculate the probability that 2 persons do not have the same birthday.

Within a group of n persons the probability, that 2 persons do not have the same birthday, is therefore:

         364  363       365 - n + 1
P ′(n) = ----⋅---- ⋅ ...⋅-----------
         365  365           365

This formula can be transformed to:

  ′           -1--       -2--             n --1-
P  (n ) = (1 -  365) ⋅ (1 - 365) ⋅ ... ⋅ (1 - 365 )

The initial problem that 2 persons out of n persons do have the same birthday is then P(n) = 1 -P(n). Figure 10 is a graph of this function P(n). The graph shown that the probability that 2 persons in a group of 30 persons have the same birthday is more than 70%. In a party with 23 persons the probability is already larger than 50%.


PIC

Figure 10: Probability P(n)

The birthday paradox problem has a very useful application in computer science for calculating the probability that 2 entries clashes in a hash table: Given a hash table of size 365, what is the probability that 2 entries clashes on the same memory location after n entries. This is a good example for the fact that the same model can have very different interpretations (or applications) in completely different domains.

Another aspect makes this problem interesting from a modeling point of view. The calculation of the expression for P(n) above is laborious. Isn’t there a simpler model? Indeed we know that:

 x           x2-  x3-                         x
e  = 1 + x + 2! +  3! + ...  ( and for x ≪ 1,e  ≈ 1 + x)

Let x = -1365, then x = -2365, ... then P(n) can be expressed as:

  ′      - 1∕365  - 2∕365       (1-n)∕365
P (n) = e      ⋅ e     ⋅ ...⋅ e
                                     =  e-(1+2+...+(n-1))∕365 = e(n2-n)∕730

Simplifying and replacing by another approximation gives:

             n2∕730
P (n) ≈ 1 - e

Hence, the birthday problem can be approximated by a much simple model that is a very good approximation. One can easily calculate the probabilities using a hand calculator.