How to understand this integral result? 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.
 A: 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}$.
A: 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.
