scott wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull 
> one out at random (replacing it each time), on average how many times 
> would you expect to pull out a ball until you have seen all the balls 1 
> to N?

N is trivially the lower bound.

Each ball appears with probability 1/N, so the probability for all balls 
to appear (given that these events are clearly independent) in N trials 
would be (1/N)^N, which is 1/(N^N).

Hmm, but wait! This does not count for ordering. There are N! 
permutations of N events, so taking *that* into account, we now actually 
have N! / N^N.

Now, if we perform K trails, the probability of seeing all the balls is 
(N! + (K-N)!) / N^N. (Assuming K >= N.)

Assuming that by "on average" you mean "with probability > 50%", it is 
now a matter of choosing K such that the above formula comes out to more 
than 0.5.

Post a reply to this message