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)) ,

where

    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.