How to understand this integral result?

Question

I was reading this page on Wikipedia: Birthday Attack

I can understand up until how to approximate the minimal number of attempts for a given probability $$n(p; H) \approx \sqrt{2H \log \frac 1{1-p}}$$

Later on the page gave an expected value of number of attempts as $$Q(H) \approx \sqrt{\frac \pi 2H}$$

I think this is probably an integral over the first result times the probability. Can anybody give a few steps how to deduce the second result from the first result? I could not get the second result by myself.

Answer 1

Let $X$ be the number of attempts without a collision. Then, we have

$\mathbb{E}[X]$ $= \displaystyle\sum_{k = 1}^{\infty}k\Pr[X = k]$ $= \displaystyle\sum_{k = 1}^{\infty}\sum_{n = 1}^{k}\Pr[X = k]$ $= \displaystyle\sum_{n = 1}^{\infty}\sum_{k = n}^{\infty}\Pr[X = k]$ $= \displaystyle\sum_{n = 1}^{\infty}\Pr[X \ge n]$.

The probability that $X \ge n$ is simply the probability of having no collisions in $n$ attempts, which is the complement of the probability having a collision in $n$ attempts. Thus, $\Pr[X \ge n] = 1-p(n;H) \approx e^{-\tfrac{n^2}{2H}}$. (This approximation is given in the Wikipedia article in the equation immediately before the first equation in your question).

So, the expected number of attempts without a collision is approximately

$\mathbb{E}[X] = \displaystyle\sum_{n = 1}^{\infty}\Pr[X \ge n] = \displaystyle\sum_{n = 1}^{\infty}[1-p(n;H)] \approx \displaystyle\sum_{n = 1}^{\infty}e^{-\tfrac{n^2}{2H}} \approx \displaystyle\int_{0}^{\infty}e^{-\tfrac{x^2}{2H}}\,dx = \sqrt{\dfrac{\pi}{2}H}$.

Answer 2

No, the calculation of the expected number of attempts before the first repeated value is a completely different problem than the number of attempts needed for the probability of a hit is some given $\rho$.

The sum you are doing in the expected value problem is

$$1 + \frac{1}{H} + 2 \frac{H-1}{H} \frac{2}{H} + 3 \frac{H-1}{H} \frac{H-2}{H} \frac{3}{H} + \cdots$$

This is $$1+\sum_{n=1}^H n^2 \frac{(H-1)!}{H^n (H-n)!}$$

The trick to this is to use Stirling's approximation for the factorials, ending up with a geometric series plus lower-order terms. The miracle is that in the highest order term, the constant $e$ has disappeared (but the $\pi$ in Stirling's approximation has stuck around.

The next order term in the approximation for the expected value is not at all easy to get right.