bag of marbles
You have 100 marbles numbered 0 to 99 in a bag. You repeatedly draw a marble from the bag (all marbles being equiprobable), note its number, and replace it in the bag. On average, how many of the marbles numbered 1 through 99 will have been drawn from the bag (one or more times) before drawing marble #0?
Solution by Michael A. Gottlieb
The sample space consists of all possible sequences of the (marble) numbers 1
through M=99 (where each number can appear any number of times - I am not
including the terminating 0 in the sequence). I propose to solve the problem by
answering the question, "For a given (marble) number m (between 1 and M), what
is the probability P that m occurs (one or more times) in a sequence of our
sample space?" Then the answer to the problem, which is the expected number of
(marble) numbers that occur one or more times in our sequences will equal P*M.
I will show that P = 1/2, implying the answer to this problem is 99/2.
First note that all sequences in the sample space having length n have the same probability: the probability of selecting M out of M+1 marbles with replacement and then selecting marble 0, equal to
(M/(M+1))^n * 1/(M+1)
= (M^n) / (M+1)^(n+1).
Furthermore, the probability that a given marble m will occur one or more times in a sequence of length n is equal to the probability that all n elements of the sequence are not selected from the remaining M-1 (non-0) marble numbers, so it's equal to
1 - ((M-1)/M)^n.
Thus the joint probability that a sequence in our sample space has length n AND that a given marble number m appears in it one or more times is equal to the product of these probabilities,
(1 - ((M-1)/M)^n) * (M^n) / (M+1)^(n+1)
= (M^n - (M-1)^n) / (M+1)^(n+1).
Summing this joint probability for n=1 to k and then taking the limit as k goes to infinity should give us P, the probability that a given marble number m occurs (one or more times) in a sequence of our sample space .
The sum from 1 to k comes out to be:
(1/2) * (1 - f(k)) ,
f(k) = (2M^(k+1) - (M-1)^(k+1)) / (M+1)^(k+1),
which clearly converges to 0 when k increases without bound, so P = 1/2.