Birthday Problem - Approximations

Approximations

The Taylor series expansion of the exponential function (the constant e = 2.718281828, approximately)

provides a first-order approximation for ex for x << 1:

To apply this approximation to the first expression derived for p(n) set . Then, Then for each term in the formula for p(n) .
For i = 1,

The first expression derived for p(n) can be approximated as

\begin{align} \bar p(n) & \approx 1 \times e^{-1/365} \times e^{-2/365} \cdots e^{-(n-1)/365} \\ & = 1 \times e^{-(1+2+ \cdots +(n-1))/365} \\ & = e^{-(n(n-1)/2) / 365}. \end{align}

Therefore,

An even coarser approximation is given by

which, as the graph illustrates, is still fairly accurate.

It is easy to see that the same approach can be applied to any number of "people" and "days". If rather than 365 days there are n, if there are m persons, and if m<

Read more about this topic:  Birthday Problem