Both the birthday paradox probability mass function and cumulative distribution function contain the expression $(1-1/n)(1-2/n)\cdots(1-(k-1)/n)$, which is usually approximated with $e^{-k(k-1)/2n}$. Is there an analytical bound on the approximation error, for example assuming $k \leq \sqrt{n}$?
1 Answer
$\begingroup$
$\endgroup$
1
$$\prod_{i=1}^{k-1} \,\Bigl(1 - \frac in\Bigr) = \exp\biggl(\sum_{i=1}^{k-1}\ln\Bigl(1-\frac in\Bigr)\biggr).$$
Now use Taylor's theorem to bound $C(n,k)$ such that $$-\frac in -C(n,k)\frac {i^2}{n^2}\le \ln\Bigl(1-\frac in\Bigr) \le -\frac in$$ for $1\le i\le k-1$. For $k\le n^{1/2}$, any value greater than $\frac12$ will work for $n$ large enough.
I believe that for $k\le n^{1/2}$ the following is true for $n$ and that the above argument can be used to prove it. $$\exp\Bigl( -\frac{k(k-1)}{2n} - \frac{1}{6n^{1/2}}\Bigr) \le \prod_{i=1}^{k-1} \,\Bigl(1 - \frac in\Bigr) \le \exp\Bigl( -\frac{k(k-1)}{2n} \Bigr). $$
If you want the error term to depend on $k$ as well as $n$, you can use the same method to get one of order $O(k^3/n^2)$.
answered Sep 3, 2017 at 2:45
-
$\begingroup$ Great, thanks (I completely forgot about Lagrange's remainder, grrr)! I'm interested in $k\approx\sqrt{n\log n}$, and indeed I get an error like $\sqrt{\frac{(\log n)^3}n}$. The problem is that empirically the error is much smaller. $\endgroup$– sebaCommented Sep 3, 2017 at 9:01