Monday, February 22, 2010

Monday Probability 7: Balls and b bins

There is an infinite supply of balls and b bins. Each ball is tossed and is equally likely to fall in any of the bins and the tosses are independent. Find the expected number of tosses before each bin has atleast one ball.

Answer: b*(1+1/2+1/3+...+1/b)


  1. E[j+1]=E[j]+b/(b-j);
    hence E[b]=b*(1+1/2+1/3+1/4+...1/b)

  2. E(x)=1+x/b*E(x)+(1-x/b)*E(x+1)
    So E(x)=b/(b-x)+E(x+1)
    Hence E(0)=b*{1/b+1/(b-1)+...1}=b*H(b) where H(b) is the harmonic number. This is asymptotically b*log(b).

  3. I am a pessimist. So I would keep throwing balls and never be satisfied. So the answer for pessimist is infinity. The answer for an optimist is b. The answer for an average Joe is b*H(b) where H(b) is the harmonic number.

  4. I still think this looks like a porn website!!! :p


Old Problems

Follow me