Probability you run out of white balls first?

Question

I saw this question online (interview brainteaser prep), and can't get my head around it.

You have $r$ red balls, $w$ white balls in a bag. If you keep drawing balls out of the bag until the bag only contains balls of a single color (i.e you run out of a color) what is the probability you run out of white balls first? (in terms of $r$ and $w$).

Supposedly the answer is just $r/(w+r)$, but I have no idea how this is arrived at. Any guidance?

Thanks

Answer 1

Think of the order you draw the balls out as a sequence, and consider the very last ball in that sequence - whichever colour it is will be the colour left in the bag when you reach the given stopping condition (i.e. if the last ball to be drawn would be white, then you must have drawn all the red balls already, and vice versa). Since we only care about what that last ball is, we can assign its colour first and then ignore the rest of the sequence, and that will be red with probability equal to $\frac{\# \mbox{ of red balls}}{\# \mbox{ of total balls}} = \frac{r}{w+r}$.

Answer 2

Depending on OP's (and the interviewer's) background, the below may or may not be more persuasive as this problem is a straightforward martingale.

Reformulation:
This game runs until there is only one ball left and that ball's color gives the winning color. You should be able to convince yourself that this doesn't change the winner over any sample path. So we want to know the probability of only having 1 red ball left at termination.

$n := w +r$

let $R_t$ be the number of red balls remaining after $t$ drawings. Then

$E\Big[R_{t+1}\big \vert R_0, R_1, ..., R_t\Big] = R_t - \frac{R_t}{n - t}= \frac{n-t-1}{n-t}R_t = \frac{n-(t+1)}{n-t}R_t$

martingales are amendable to affine transforms (because conditional expectations are), so it's a standard result that you should, perhaps after fiddling with rescaling, get a martingale here, and the stopping time $T$ is bounded (i.e. the game ends WP1 after n-1 turns).

you should be able to see

$\frac{1}{n-(t+1)}E\Big[R_{t+1}\big \vert R_0, R_1, ..., R_t\Big]= \frac{1}{n-(t+1)} \cdot\frac{n-(t+1)}{n-t}R_t =\frac{1}{n-t}R_t$

so $R_t^*:= \frac{R_t}{n - t}$ is a martingale. If you are still uncertain, you may want to consider boundary conditions to confirm, in particular

$E\Big[R_{1}^*\big \vert R_0^*\Big]= \frac{1}{n - 1} \cdot E\Big[R_{1}\big \vert R_0\Big]= \frac{1}{n - 1}\cdot \frac{(n-1)R_0}{n} = \frac{R_0}{n} =\frac{r}{n}=R_0^* $

application of the martingale stopping theorem gives
$E\big[R_T^*\big] = E\big[R_0^*\big] = \frac{r}{n} = \frac{r}{r+w}$

but at the time of stopping, we have a Bernouli, i.e. if you win
$R_T^*$ takes on $1\cdot \frac{1}{n-(n-1)} = 1$ with probability $p$

and takes on the value of 0 if you lose so the probability of winning is
$p = E\big[R_T^*\big] = \frac{r}{r+w}$

it's easy to get bogged down in the bookkeeping here depending on interview dynamics. But, supposing your interviewer knows what a martingale is, my guess is you'd get bulk of the credit if you recognized this is a fair game and correctly computed $E\Big[R_{t+1}\big \vert R_0, R_1, ..., R_t\Big] = R_t - \frac{R_t}{n - t}$

Answer 3

The act of drawing the balls produces a sequence of colors, equivalent to putting $r$ red balls and $w$ white balls in a row from left to right. Even though you may not draw all the balls, the fact that you draw until one color has run out means each sequence could logically be finished by placing the remaining balls (which are all one color) after the last ball drawn.

Now convince yourself (or someone else) that each row of balls is equally likely to occur. This may be easier to see if you don’t track the individual balls to say that one white ball was drawn before another (for example). The sample space then has just $\binom{r+w}{r}$ outcomes, each one described by the places in the row of balls that are occupied by red balls. (You can equally well say there are $\binom{r+w}{w}$ outcomes identified by where the white balls are; it’s the same number of outcomes.)

Then what’s the color of the very last ball in the row, ball number $r+w$ counting from the left? The probability that this ball is red is $r/(r+w),$ just like the first ball on the left (the first color drawn) or like the ball in any particular position in the row.

Now note that you run out of white balls first if and only if the last ball in the row is red.

Answer 4

Let's label the balls with $1,...,N$, so that the balls $1,...,w$ are white, and the others are red.

We now draw all balls, and write down their exact order.

Let $\Omega = (i_1,..,i_N)\in \{1,..,N\}^N\mid \forall p,q\in \{1,..,N\}: i_p \neq i_q\} $.
Then this experiment has the probability space $\Omega,P(\Omega), U_\Omega)$, i.e. it is a Laplace-experiment, as every order has the same probability.
Laplace-spaces have the advantages that if we have an event we care about, we can just count the number of results to find out the events probability.

We're now interested in the probability of the event that we draw all white balls before we draw the $r$-th red ball. So we have to count all drawing orders, in which we have $w$ white balls before we have $r$ red balls.

These are exactly all drawing orders, in which in the first $w+r-1$ drawn balls, we have exactly $w$ white balls.

So we place the balls $1,..,w$ onto the first $w+r-1$ fields. We have
$w+r-1$ possibilities for ball number 1,
$w+r-2$ possibilities for ball number 2,
...
$r$ possibilities for ball number w,
.

Now, onto the remaining $r$ fields we place the remaining $r$ red balls, which gives another $r!$ possibilities.

All in all we therefore have $\frac{(w+r-1)!}{(r-1)!} r!$ drawing orders in which we the last white ball first.

Therefore its probability is $$\frac{\frac{(w+r-1)!}{(r-1)!} r!}{\Omega}= \frac{\frac{(w+r-1)!}{(r-1)!} r!}{N!}= \frac{\frac{(w+r-1)!}{(r-1)!} r!}{(w+r)!} = \frac{r}{w+r}$$