I'm reading the wikipedia page for the generalized birthday problem. I have a question about the derivation,
Under the Cast as a collision problem section, they write,
$$p(n;d) \approx 1 - e^{-n(n-1)/(2d)}$$ $$p(n;d) \approx 1 - (\frac{d-1}{d})^{n(n-1)/2}$$
This transformation is done using the limit for $e^x = (1+\frac{x}{n})^n$, with $x=\frac{-1}{d}$ and $n=1$ right?
But I can't figure out the next transformation for $n(p;d)$, eg.
$$n(p;d) \approx \sqrt{2d * \ln(\frac{1}{1-p})}$$
Could anyone explain how that was derived there?
$$p \approx 1 - \left(\frac{d-1}{d}\right)^{n(n-1)/2}$$
so $$\left(\frac{d-1}{d}\right)^{n(n-1)/2} \approx 1-p $$
so $$\dfrac{n(n-1)}{2}\log\left(\frac{d-1}{d}\right) \approx \log(1-p) $$
so $${n(n-1)} \approx \dfrac{2\log(1-p)}{\log\left(\frac{d-1}{d}\right)} $$
and saying $1-\frac1d \approx e^{-d}$ i.e. $\log\left(\frac{d-1}{d}\right) \approx -\frac1d$, and $\log(1-p)=-\log\left(\frac{1}{1-p}\right)$ $${n(n-1)} \approx 2d\log\left(\frac{1}{1-p}\right) $$
and saying $\sqrt{n(n-1)}\approx n $ $$n \approx \sqrt{2d\log\left(\frac{1}{1-p}\right)} $$