Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Is this process repeated until there are no balls left? –  copper.hat Jun 4 '12 at 4:22
    
Yes. To exhaust all balls and have the last one in white. –  Rock Jun 4 '12 at 4:25

3 Answers 3

up vote 9 down vote accepted

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!

share|improve this answer
    
+1 Good on you for an exact solution. My approach had a significant approximation which turns out to matter. But we are both far from $\frac 12$. –  Ross Millikan Jun 4 '12 at 11:10
    
+1 Exactly the way I meant to tackle the problem. This problem reminds on the tennis game problem, solved by James Bernoulli. –  Sasha Jun 4 '12 at 13:35
    
The simplified expression is good-looking. The simulation approach I took really fluctuates though. –  FrenzY DT. Jun 4 '12 at 13:53

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 <iostream>
    #include <ctime>
    #include <cstdlib>
    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.

share|improve this answer
    
I don't think this is correct. It appears that if you draw three red balls to start, the first sets discard to true (and stays in the bin), the second is discarded but discard stays true, and then the third is discarded. –  Ross Millikan Jun 4 '12 at 5:54
    
@Ross The question states that: 2.the ball is put back if it is red and another ball is drawn; discard next. So I think that the first ball just sits there if it is red. Discard whatever is the next (red). –  FrenzY DT. Jun 4 '12 at 5:58
    
@Ross But I got some confusion. How should I treat three consecutive red balls? –  FrenzY DT. Jun 4 '12 at 6:00
    
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. –  Ross Millikan Jun 4 '12 at 6:05
    
@Ross Thanks. I now understand the logic. Just gave the new code. Ooops still need some edit. Sorry for this. –  FrenzY DT. Jun 4 '12 at 6:10

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\%$

share|improve this answer
    
Are you saying the last is red or white? And can you show how you come up the probabilities? Why square? Thanks! –  Rock Jun 4 '12 at 5:59
    
@Rock: to remove a red ball you have to draw two reds in a row, which gives the square. I am saying it is very likely the last is red. –  Ross Millikan Jun 4 '12 at 6:03
    
You probably misprogrammed your spreadsheet, the true value should be about $91.8181818$%. –  Marc van Leeuwen Jun 4 '12 at 9:24
    
@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. –  Ross Millikan Jun 4 '12 at 10:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.