Approximating $\left(\frac{D-1}{D}\right)^n$ by $\displaystyle e^{-n/D}$ in the birthday problem

63 Views Asked by At

It has come to my attention (more on why below) that the expression $\left(\frac{D-1}{D}\right)^n$ can be pretty accurately approximated by $e^{-n/D}$. Why is that? What is the relationship between these two expressions?

For some context, these expressions come from the solution to the case of the birthday problem in which you want to know the expected number of unique birthdays present given $n$ people (so $D=365$ in this case).

I saw that the generalized solution is given by: $D\left(1 - \left(\frac{D-1}{D}\right)^n\right)$

But I see that elsewhere $D\left(1 - e^{-n/D}\right)$ is used and is extremely accurate.

1

There are 1 best solutions below

2
On BEST ANSWER

Using the fact that $\log(1+x)\approx x$ for small $x$ yields $$ \log\Big[\Big(\frac{D-1}{D}\Big)^n\Big]=n\log\Big(1-\frac{1}{D}\Big)\approx -\frac{n}{D} $$ for large $D$, hence $\Big(\frac{D-1}{D}\Big)^n\approx e^{-\frac{n}{D}}$.