Consider a group $G$ consisting of $n$ distinct elements. Suppose we draw random elements of $G$ (one by one, replacing each element every time) until we draw an element that was drawn before (we say there was a match or collision).
I am in front of the following statement
If elements are drawn at random from $G$ then the expected number of draws before a collision occurs is $\sqrt{πn/2}$
(I suppose it is implicit that all elements of $G$ have the same probability of being drawn). I tried and failed to understand this statement in terms of expectation of the variable that counts the number of draws before the collision occurs. Any ideas?
The probability that the first collision occurs at draw number $k+1$ is the probability that the first $k$ draws are distinct and the $k+1$'th is equal to one of the first $k$. The number of outcomes in this event is $\dfrac{n!}{(n-k)!} k$, so its probability is $$P_k = \dfrac{n! k}{(n-k)! n^{k+1}}$$
The expected number of draws before a collision occurs (before, so not counting the draw on which the collision occurs) is then $$ \sum_{k=0}^n \dfrac{n!\; k^2}{(n-k)!\; n^{k+1}} $$
There is no nice closed form for this sum (unless you like $\mbox{$_3$F$_1$}$ hypergeometrics), but of course for any particular $n$ you can compute it exactly: it will be a rational number, so certainly not $\sqrt{\pi n/2}$. The claim is that it is asymptotic to $\sqrt{\pi n/2}$ as $n \to \infty$.
EDIT: Let $X$ be the number of draws before the first collision. Then $E[X] = \sum_{k=1}^n P(X \ge k)$ where for $1 \le k \le n$, $$P(X \ge k) = \dfrac{n!}{(n-k)! n^k} = \prod_{j=0}^k \left(1 - \dfrac{j}{n}\right)$$ I won't bother with the details, but this can be approximated by $e^{-k^2/(2n)}$. Then $$ E[X] \approx \sum_{k=1}^n e^{-k^2/(2n)} \approx \int_0^n e^{-t^2/(2n)}\; dt = \sqrt{n}\int_0^{\sqrt{n}} e^{-s^2/2}\; ds \approx \sqrt{\pi n/2} $$ because $\int_0^\infty e^{-s^2/2}\; ds = \sqrt{\pi/2}$.