Number Probability of of Trials Success ------ ----------- 1 p 2 pq 3 pqSince there must eventually be a sucess the sum of probabilities is:^{2}4 pq^{3}. . . . . .

p + pq + pq

The mean number of trials (m) is:
m = p + 2pq + 3pq^{2} + 4pq^{3} + ...

mq = pq + 2pq^{2} + 3pq^{3} + ...

m-qm= p + pq + pq^{2} + pq^{3} + ...

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.

Michael Shackleford, A.S.A.