# Mean number of distinct marbles drawn at least once before marble #0 is drawn

I'm trying to solve this probability exercise:

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?

I guessed a trial would consist of picking and replacing marbles at succession and counting failures. But the solution disagrees. What am I missing logically? I coded a trial in Mathematica like this:

trial :=
With[{marbles = Range[0, 99]},
Module[{
count = 0,
pick = RandomChoice[marbles]},
While[pick != 0,
count++;
pick = RandomChoice[marbles]];
count]]


With[{n = 10000},
N@Mean@Table[trial, {n}]]


Update

I didn't understand the text, it asks for the number of distinct marbles drawn before the #0. The working code is:

trial :=
With[{marbles = Range[0, 99]},
Module[{pick, picked = {}},
pick = RandomChoice[marbles];
While[pick != 0,
If[! MemberQ[picked, pick],
AppendTo[picked, pick]];
pick = RandomChoice[marbles]];
Length[picked]]]

• Expected time to draw marble #0 is 100. Hence expected number of marbles drawn before #0 is drawn is 99, while expected number of distinct marbles drawn is 99/2. – A.S. Jan 30 '16 at 21:09
• Yes, I can see I didn't understand the text. Yet, why is the expected number of distinct marbles exactly half the expected number of draws? – BoLe Jan 31 '16 at 15:36
• Because the number of times a given marble is drawn is $Geom(\frac 1 2)$, hence the expected number of times a marble is draw given that it's drawn at all is $2$. Hence ratio of marbles drawn to distinct marbles drawn is $2$. The reason is symmetry between "special" marble #0 and any other fixed marble. – A.S. Jan 31 '16 at 17:15

Drawing the $\#42$ marble, then the $\#42$, then the $\#42$, then the $\#0$ only counts as one failure before the first success. If we were counting them as separate failures, then the number of failures before the first success would have one of the versions of the geometric distribution, and would have mean $99$. But that is not the situation here. Now to the solution, which will use the method of indicator random variables.
For $i=1$ to $99$, let $X_i=1$ if marble $i$ is drawn before marble $0$, and let $X_i=0$ otherwise. Then the number $Y$ of different bad marbles drawn before the first $0$ marble is $X_1+\cdots+X_{99}$. We have $E(X_i)=\frac{1}{2}$, and therefore by the linearity of expectation $E(Y)=\frac{99}{2}$.
• Expectation $E(X_i)$ equals one half because marble $i$ is drawn either before $0$ or after? – BoLe Jan 31 '16 at 16:20
• Yes, $X_i=1$ with probability $1/2$, and $X_i=0$ with probability $1/2$, because in a series of draws, if we restrict attention to Ball $0$ and Ball $i$, Ball $0$ is just as likely to come before Ball $i$ as after. Note that the distribution of what I called $Y$ is not easy to get at. But we don't need the distribution to find the expectation. – André Nicolas Jan 31 '16 at 16:38
• I tried these random indicators on this slight modification of the problem: instead of one the bag contains ten marbles marked #0. The question remains the same. The results $E(X_i) = 0 * 10 / 11 + 1 * 1 / 11 = 1 / 11$ and $E(Y) = 99 / 11 = 9$ agree with the result of the modified simulation (in the post update). – BoLe Jan 31 '16 at 18:45