Sorry, please disregard my previous post, I hit submit by mistake.
Thanks for your fast reply CRGreathouse! I have tried the way you suggested, but still a closed form solution evades me! Here is my analysis:
First, I think the problem is stated a little ambiguously, so this is my understanding of it. Suppose I perform the following experiment: take b empty bins and start tossing balls into them at random. As soon as a ball lands in already occupied bin, I record the number of throws I had made. The problem asks to find the expected value of these recorded numbers, which will be the average over this experiment performed great many times. In other words, I need to find the expected number of tosses that result in a single collision on the last toss.
I have approached this from two paths.
First way is define a random variable X such that event X=k means that after k-1 tosses, there were no collisions, but k'th toss resulted in a collission. In other words, X=k is the event that k'th toss results in a single bin having two balls, while all the rest have at most one. Then probability of X=k is:
P(X=k) = \frac{(b)_{k-1}(k-1)}{b^k}
Where (b)_{k}=\frac{b!}{(b-k)!}. And the expected value that the problem is to compute is:
E(X) = \sum_{k=2}^{b+1} kP(X=k) = \sum_{k=2}^{b+1} \frac{(b)_{k-1}(k-1)}{b^k}k
This is a solution in a form of a sum.
From the fact that X is a random variable and that it takes values from 2 to b+1, we also have:
\sum_{k=2}^{b+1}P(X=k) = \sum_{k=2}^{b+1}\frac{(b)_{k-1}(k-1)}{b^k} = \frac{1}{b}\sum_{k=1}^{b}\frac{(b)_{k}k}{b^k}=1
A second way of getting an answer is define an indicator random variable I_{k} such that the event I_{k}=1 means that there was k'th toss, and define I_{k}=0 otherwise. In other words, it means that previous tosses have resulted in no collisions, and therefore we made k'th toss, the result of which is unknown. The probability of this event is equals to the probability that previous k-1 tosses had no collisions. It is:
P(I_{k}=1) = \frac{(b)_{k-1}}{b^{k-1}} = E(I_{k})
And random variable X can be expressed in terms of I's:
X=\sum_{k=1}^{b+1}I_k
So by linearity of expectations we have:
E(X)=\sum_{k=1}^{b+1}E(I_k) = \sum_{k=1}^{b+1}\frac{(b)_{k-1}}{b^{k-1}} = \sum_{k=0}^{b}\frac{(b)_k}{b^k}
And I can show that this formula for E(X) is consistent with previous formula for E(X) by direct derivation:
\sum_{k=1}^{b+1}\frac{(b)_{k-1}(k-1)}{b^k}k = \sum_{k=1}^{b}\frac{(b)_{k-1}}{b^{k-1}}k - \sum_{k=1}^{b}\frac{(b)_k k}{b^k} + \frac{b! b (b+1)}{b^{b+1}} = \sum_{k=1}^{b-1}\frac{(b)_k}{b^k}(k+1) - \sum_{k=1}^{b}\frac{(b)_k k}{b^k} + \frac{b! (b+1)}{b^b} = \sum_{k=1}^{b-1}\frac{(b)_k}{b^k} + \frac{b!}{b^b} = \sum_{k=1}^{b}\frac{(b)_k}{b^k}
But I still don't have a closed form solution! This problem has been annoying me for about a day already. I think the authors wouldn't put this with other simple problems if it wasn't relatively simple to solve, so I still believe that a closed form solution is out there. Does anyone have any ideas?
Thank you.
