Probability of first collision with replacement Suppose I have a bag of N balls, each labeled with a distinct integer. The experiment starts when I draw a ball from the bag, record its label, and then return the ball back to the bag. I repeat this step until I draw a ball that I have already drawn before. Let X be the number of balls I drew in the experiment. Let P be the probability distribution of X.
Is there a name to this probability function P?
Is there a closed form for P?
Actually, I would be satisfied if there is a closed form for E[X] and Var[X].
Please help.
 A: $P(X)=(X-1)N^{1-X}\frac{(N-1)!}{(N+1-X)!}$, for $X=2,3,\ldots N+1$.
A: There's no closed form for this expectation. However, you can get good approximations. One common way to do this is with generating functions. Herb Wilf's book is an excellent reference.
As noted, the probability that the first collision occurs on the $n$th draw with  $m$ balls is $p_n=d_{n-1}\frac{n-1}m$, where $d_n=\frac{m!}{m^n (m-n)!}$. Consider the ordinary generating function $D(x)=\sum_{n=0}^{m}d_nx^n$. Then the expected number of draws to get a collision would be $\langle p\rangle=\sum_{n=1}^{m+1} n\cdot p_n$ or, in terms of the generating function,
$\langle p\rangle=\frac{d^2}{dx^2}(xD(x))|_{x=1}$. 
The generating function $D(x)$ is not summable. However, its exponential counterpart is: $E(x)=\sum_{n=0}^{m}\frac{d_n}{ n!}x^n=(1+x/m)^m$. The ordinary and exponential generating functions are related by the Laplace transform, $D(x)=\frac 1x\int_0^\infty e^{-t/x}E(t)dt$. Differentiating under the integral twice  and then evaluating at $x=1$, we get $\langle p\rangle=\frac 1m\int_0^\infty e^{-t}(t^2-2t)(1+t/m)^mdt$. The dominant part in this integral comes from the $t^2$  term. So, $\langle p\rangle\approx\frac 1m\int_0^\infty e^{-t}t^2(1+t/m)^m dt$, and substituting $u=t/m$, we get $\langle p\rangle\approx m^2\int_0^\infty e^{m(-u+\log(1+u))}u^2 du$. This integral can be nicely approximated with Laplace's method, where the exponent $-u+\log(1+u)$ is replaced with its second order Taylor series about its maximum (at $u=0$), which turns out to be just $-u^2/2$. So, $\langle p\rangle\approx m^2\int_0^\infty e^{-u^2 m/2}u^2du=\sqrt{{\pi m}/2}$.
If you need greater accuracy or if you want to consider higher moments of the distribution, you can always consider the other terms in the first integral representation of $\langle p\rangle$ and higher order terms in the Laplace's method. Another avenue to analyze this expectation, as suggested in the wikipedia article on the birthday problem, is to learn about the Ramanujan $Q$-function.
