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