First I'll show that if the probability of an event happening is p then the mean number of trials to obtain a sucess is 1/p.

Number   Probability
  of         of
Trials     Success
------   -----------
  1           p
  2           pq
  3           pq2
  4           pq3
  .           .
  .           .
  .           .
Since there must eventually be a sucess the sum of probabilities is:
p + pq + pq2 + pq3 + ... = 1.

The mean number of trials (m) is: m = p + 2pq + 3pq2 + 4pq3 + ...

mq = pq + 2pq2 + 3pq3 + ...

m-qm= p + pq + pq2 + pq3 + ...

m(1-q) = 1.

m = 1/(1-q) = 1/p.

Second, the answer to the problem can be express as the sum of the following:

The number of trials to get one toy is obviously one.

Once you have one the probability of getting a different toy in the next box is (n-1)/n, thus the expected number of trials is 1/((n-1)/n) = n/(n-1) to get the second toy.

By the same logic the number of trials to get the third is n/(n-2), and n/(n-3) to get the fourth, ... and n to get the final toy. Summing these yields n * (1/n + 1/(n-1) + 1/(n-2) + ... + 1 ).

I'd like to thank Michael Brasher for providing this solution.


Nick Hobson sent in the following method to approximate the solution:

you can use Euler's approximation to get a good idea of how the expected number grows with increasing n.

1 + (1/2) + ... + (1/n) ~= log n + (1/2n) + Y, where Y ~= 0.57721, and is known as Euler's constant.

So, E(n) ~= n * (log n + Y) + (1/2).

Even for n = 4 this approximation is within 3% of the true value. For larger n the percentage error is much smaller.

Here's elegant way of proving that if the probability of an event happening is p then the mean number of trials to obtain a success is 1/p.

Consider the situation after the first trial.

Either the event has happened: contribution 1 * p, or it has not: contribution (1 + m) * q.

Therefore, m = p + (1 + m)*(1 - p), from which m = 1/p.


Michael Shackleford, A.S.A.