Number   Probability
  of         of
Trials     Success
------   -----------
  1           p
  2           pq
  3           pq2
  4           pq3
  .           .
  .           .
  .           .

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

mq = pq + 2pq² + 3pq³ + ...

m-qm= p + pq + pq² + pq³ + ...

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:

• Number of trials to get a first toy
• Number of trials to get a second toy once you have one toy
• Number of trials to get a third toy once you have two toys
• .
• .
• .
• Number of trials to get the final toy once you have all but one toys

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.