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:

• 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
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.