Looking at this answer by Henry birthday problem - expected number of collisions and struggling to figure out why it matches this other formula provided to me on a programming related question. Thanks!
$\begingroup$
$\endgroup$
3
-
7$\begingroup$ $(1 - 1/p)^n = [(1 - 1/p)^{p}]^{n/p}$, and $(1 - 1/p)^p$ approaches $e^{-1}$ for large $p$. $\endgroup$– Christopher A. WongCommented Jun 11, 2014 at 1:22
-
1$\begingroup$ @ChristopherA.Wong You should make that an answer! $\endgroup$– user98602Commented Jun 11, 2014 at 1:48
-
$\begingroup$ you may get confused if you have seen other definitions of $e$, as maybe convergence series. There many ways to get $e$ one of the most common is the one mentioned by Christopher. $\endgroup$– clarkCommented Jun 11, 2014 at 1:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
What you may not know is that $e$ can be defined as $$\lim_{x \to \infty} (1+1/x)^x$$ from which it follows (by a little bit of limit manipulation) that $$\lim_{x \to \infty} (1+r/x)^x=e^r$$ The formula you are asking about can be explained from this; see Christopher Wong's comment above.
$\begingroup$
$\endgroup$
I don't know if you are familiar with Taylor series, but if yes : $$\left(1-\frac1p\right)^n=\exp\left(n\ln\left(1-\frac1p\right)\right)=\exp\left(-n\left(\frac1p+o\left(\frac1p\right)\right)\right)$$ and this gives : $$\left(1-\frac1p\right)^n\sim_{p>>1} \exp\left(-\frac{n}{p}\right)$$
Note than there's no assumption on n.
