8
$\begingroup$

A jar contains $m=90$ white balls and $n=10$ red balls, the balls are drawn under the following constraints:

  1. the ball is thrown away if it is white;
  2. the ball is put back if it is red and another ball is drawn; this time, the ball is thrown away no matter what color it is.

The question is, what is the probability to exhaust all balls and have the last one in white color? My guess is $\frac{1}{2}$ but I might be wrong. Please show how you deduce the answer. Thanks!

EDIT: Thanks for posting the solution and simulation, which are all appreciated. B. E. Oakley and R. L. Perry discussed a very similar problem in their A Sampling Process paper published on The Mathematical Gazette, Vol. 49, No. 367 (Feb., 1965), pp. 42-44.

The problem presented in the paper is:

A bag contains m > 0 black balls and n > 0 white balls. A sequence of balls from the bag is discarded in the following manner:

(i) A ball is chosen at random and discarded. (ii) Another ball is chosen at random from the remainder. If its colour is different from the last it is replaced in the bag and the process repeated from the beginning (i.e. (i)). If the second ball is the same colour as the first it is discarded and we proceed from (ii). Thus the balls are sampled and discarded until a change in colour occurs, at which point the last ball is replaced and the process starts afresh.

The question is: what is the probability that the final ball should be black?

Their induction gives $\frac{1}{2}$ which is what I have here. Apparently having no constraint on colors like what's in the paper changes the situation significantly.

But the story hasn't ended. At the end of their paper, they proposed a seemingly more interesting problem: What is the solution if there are balls of 3 different colours and the sampling process is as before?

  • 0
    Yes. To exhaust all balls and have the last one in white.2012-06-04

3 Answers 3

10

I'll continue on the answer by Ross Millikan, and give an exact solution (I'll just replace $R$ and $W$ by lower case $r$ and $w$, which intimidates me less). So for $r,w\in\mathbb N$, not both zero, let $P(r,w)$ denote the probability of leaving a white ball as last one when starting with $r$ red and $w$ white balls. One obviously has $P(r,0)=0$ for any $r>0$ and $P(0,w)=1$ for any $w>0$; moreover by the argument Ross gives one has the recurrence relation $ P(r,w) = \frac{r^2}{(r+w)^2}P(r-1,w) + \frac{w^2+2rw}{(r+w)^2}P(r,w-1) \quad\text{for all } r,w>0, $ since the first step reduces the problem defining $P(r,w)$ either to the one defining $P(r-1,w)$ or to the one defining $P(r,w-1)$, with the indicated factors as probablilities for the first step.

Now this recurrence has the (surprisingly simple) solution $ P(r,w)=\frac{w}{(r+1)(r+w)}\quad\text{for }(r,w)\in\mathbb N^2\setminus\{(0,0)\}. $ The proof is by a simple induction on $r+w$, expanding the recurrence relation, factoring out $\frac w{(r+w)^2(r+w-1)(r+1)}$ which leaves $r(r+1)+(w+2r)(w-1)$ as other factor, and rewriting that factor as $(r+w)(r+w-1)$ permits some cancelling and arriving at the desired result.

I did not guess the formula just like that of course. Rather I calculated a number of values $P(1,w)$ with exact rational arithmetic, noticing substantial simplifications and easily guessing $P(1,w)=\frac{w}{2(w+1)}$. I proceeded similarly for $P(2,w)$, again with significant simplfications, after which I guessed the general form.

For the concrete problem one gets $P(10,90)=\frac9{110}\approx0.08181818$, a chance of a bit less than $1$ in $12$ to be left with a white ball. In fact one sees that throwing in any number of white balls (with $10$ red balls) initially never even raises the chance to $1$ in $11$. And if there are any red balls at all initially, it is always more likely to be left with one of them than with a white ball!

  • 0
    +1 Exactly the way I meant to tackle the problem. This problem reminds on the tennis game problem, solved by James Bernoulli.2012-06-04
5

I don't know how to derive the exact probability, so I wrote the following C++ code and try to see if the simulated probability fluctuates about $0.5$.

EDIT: My new code is based on the assumption that

  • If a white ball is drawn, discard it.
  • If a red ball is drawn -- If the next ball is red, discard a red. (whites automatically gets discarded).

    #include  #include  #include  using namespace std;  const int TIMES = 1000000;  int main() {     int whiteleft = 0;     int redleft = 0;      int times;     // srand(time(NULL)) doesn't work as it generates the same sequence on my     // computer. I resort to this ↓     srand(rand()%RAND_MAX*32768+rand()*rand()+96485+(unsigned)time(0));      for (times = 0; times < TIMES; ++times)     {         int white = 90; // color = 1         int red = 10;   // color = 0          int discard = 0;         do         {             // rand()%(white+red) gives a random int between 0 and (white+red).             // If rand int is smaller than white, then it's a white.             int color = ( rand()%(white+red) < white)? 1 : 0;             if (color == 0)             {   // a red ball, you discard it if discard is true                 if (discard)                 {                     --red;                     discard = 0;                 }                 else                     discard = 1; // discard the ball on the NEXT loop             }             else             {   // a white ball, you throw it away directly                 // and reset discard                 --white;                 discard = 0;             }         }         while (white>0 && red>0);          if (white)             ++whiteleft;         else             ++redleft;          if ( times % 500000 == 0) // Report progress             cout << " << " << times << endl;     }      cout << " :: Total experiments " << TIMES << " times" << endl;     cout << "    whiteleft = " << whiteleft << ", redleft = " << redleft << endl;     system("pause");     return 0; } 

A sample run of 1M gives:

 :: Total experiments 1000000 times     whiteleft = 81745, redleft = 918255 

So it seems to be that the probability is not $1/2$. Instead it's around $0.082$. The probability of a remaining red is around $0.918$. I'm thinking real hard for an analytic solution but am expecting someone else to answer this.

  • 0
    I read it that you should pull the first ball. If it is red, put it back, pull the second and discard it regardless of color. Then pull the third ball. If the third is white discard it, otherwise put it back and discard the fourth regardless of color.2012-06-04
2

If you have $R$ red balls and $W$ white balls, you remove a red one with probability $\frac {R^2}{(R+W)^2}$ and a white one with probability $\frac {W^2+2RW}{(R+W)^2}$. Just keeping track of the expected number of red and white balls in a spreadsheet, I find the probability the last is red to be a little over $98.9\%$

  • 0
    @MarcvanLeeuwen: I realized later that there is a substantial approximation in this argument, roughly assuming that the decrease in expected value is the expected value of the decrease. Your value validates the simulation of FrenzY DT.2012-06-04