Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
This is a variant of the birthday problem. It looks like even the wikipedia article on this has the information you're asking for. –  Russell May Sep 18 '12 at 13:46
    

2 Answers 2

up vote 1 down vote accepted

$P(X)=(X-1)N^{1-X}\frac{(N-1)!}{(N+1-X)!}$, for $X=2,3,\ldots N+1$.

share|improve this answer
    
I tried a few cases with small N and X, and this looks good. By the way, calculating the expected value seems difficult because of the factorial. I don't suppose I could trouble you further for some suggestion how E[X] and Var[X] could be solved? –  user26604 Sep 18 '12 at 18:26
    
I'm sorry, no simple closed form expression for the moments; but they can be calculated easily, E[X]=2,5/2,26/9,103/32,2194/625,1223/324, and Var[X]=0,1/4,44/81,879/1024,463864/390625,160235/104976 for N=1,2,3,4,5,6. What more can you want...? –  Carlo Beenakker Sep 18 '12 at 21:00
    
I was trying to use E[X] = f(N) as an estimator to estimate the number of objects in a set of unknown size N: suppose after conducting a large set of experiments I get an empirical average y, I can then solve for N in the equation y = f(N). So, I was hoping there's a closed form for f. –  user26604 Sep 19 '12 at 3:25

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.