2
$\begingroup$

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]]

And approximate the answer:

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]]]
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.S.
    Jan 30, 2016 at 21:09
  • $\begingroup$ 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? $\endgroup$
    – BoLe
    Jan 31, 2016 at 15:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.S.
    Jan 31, 2016 at 17:15

1 Answer 1

4
$\begingroup$

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}$.

$\endgroup$
4
  • $\begingroup$ Expectation $E(X_i)$ equals one half because marble $i$ is drawn either before $0$ or after? $\endgroup$
    – BoLe
    Jan 31, 2016 at 16:20
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 31, 2016 at 16:38
  • $\begingroup$ 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). $\endgroup$
    – BoLe
    Jan 31, 2016 at 18:45
  • $\begingroup$ Congratulations on continuing the exploration. $\endgroup$ Jan 31, 2016 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .