Draw All Balls

There are 100 distinguishable balls in an urn. Each time you draw one ball and put it back. How many times do you expect you need to draw in order to have drawn each ball at least once?

Solution:

So on your first draw, you obviously draw a ball you've never drawn before. On your next draw, there's a 99/100 chance you draw a different one. After you've drawn 2 distinct balls, there's a 98/100 chance you draw a different one from those 2. And so on. The expected number of draws is just the reciprocal of the probability of that event happening.

So we simply have: 1 + 100/99 + 100/98 + ... +100/3+100/2+100.

I wasn't asked to evaluate this sum during the actual interview, and quite frankly I wouldn't know how to do this exactly. I probably would have taken the integral of 1/x over 1 to 100, which is ln 100 ~= 4.61 so about 461 draws.

The actual answer is 518.74 so that approximation would be way off--not surprising. I'm gonna be anal here and look at the graph--okay, so half of the 1st bar of the sum I'm approximating by the integral isn't included. That got an area of 50! Add 50 to 461 and we have 511. That's much better.

I suppose at this point, if you have gone this route, an interviewer could start talking about numerical methods, especially if he happened did his thesis on something related.

ps. check out the harmonic series page from mathworld. the closed form formula for the sum is... certainly not fair game for an interview.