An urn with r red balls and b blue balls and a special way of taking the balls out until a single color is left

Question

This is problem 2.13 b) in David Stirzaker's book: "Elementary probability".

The urn contains r red balls and b blue balls and we are to take the balls out until a single color is left in the urn. The special way of taking the balls is as follows:

We are to follow a process where we first grab a ball and take it out of the urn, register its color and then we randomly take balls from the urn until we take out one that is of different color. That ball of different color is RETURNED to the urn and we are to repeat the process until a color is left. Do note that when we start a new process, the first ball that we take will always be pulled out of the urn, so it is well defined to talk about the probability that a color is left (after a finite amount of steps, a color will be singled out in the urn).

Now we are asked to find the probability that the color left in the urn is red. My main approach was to use double induction on the number of red and number of blue balls. One gets that when fixing the number of red balls to 1 and using induction to generalize the number of blue balls, the answer is 1/2.

This is also true for the case of r=2: by induction on b we get 1/2.

I got stuck on the inductive step when we generalize the number of red balls: using conditional probability a complicated sum is formed and I am not sure how to get 1/2 as the answer.

Perhaps there is an easier way so I hope someone can share some ideas or even give the whole solution.

Answer 1

Was able to arrive at the result following your induction idea, but it required a lot of brute force. I feel there should be a more elegant approach but I haven't found one yet.

---

Let $p(r, b)$ denote the desired probability as a function of $r$ and $b$.

Let $p(r, 0) = 1$ and $p(0, b) = 0$.

Warm-up.

For $b \ge 1$ we have $$p(1, b) = \frac{b}{b+1} \left(\frac{1}{b} p(1, b-1) + \frac{1}{b} p(1, b-2) + \cdots + \frac{1}{b}p(1, 0)\right) = \frac{1}{b+1} \sum_{k=0}^{b-1} p(1, k).$$

Using the base case $p(1, 0)=1$ we obtain $p(1, b) = 1/2$ for all $b \ge 1$, as you noted.

General case.

For general $r, b$, \begin{align} p(r, b) &= \frac{b}{r+b}\left(\frac{r}{r+b-1} p(r, b-1) + \frac{(b-1)r}{(r+b-1)(r+b-2)}p(r, b-2) + \cdots + \frac{(b-1)! r}{(r+b-1)!/((r-1)!}p(r, 0)\right) \\ &\qquad + \frac{r}{r+b} \left(\frac{b}{r+b-1} p(r-1, b) + \frac{(r-1) b}{(r+b-1)(r+b-2)}p(r-2, b) + \cdots + \frac{(r-1)! b}{(r+b-1)!/(b-1)!}p(0, b)\right) \\ &= \frac{b}{r+b} \sum_{k=0}^{b-1} \frac{r(b-1)!/k!}{(r+b-1)! / (r+k-1)!} p(r, k) + \frac{r}{r+b} \sum_{k=0}^{r-1} \frac{b(r-1)!/k!}{(r+b-1)!/(b+k-1)!} p(k, b) \\ &= \frac{b! r}{(r+b)!} \sum_{k=0}^{b-1} \frac{(r+k-1)!}{k!} p(r,k) + \frac{r! b}{(r+b)!} \sum_{k=0}^{r-1} \frac{(b+k-1)!}{k!} p(k, b) \\ &= \frac{1}{\binom{r+b}{r}} \sum_{k=0}^{b-1} \binom{r+k-1}{r-1} p(r,k) + \frac{1}{\binom{r+b}{r}} \sum_{k=0}^{r-1} \binom{b+k-1}{b-1} p(k, b) \end{align} If we have the inductive hypothesis $p(r', b')=1/2$ [for $(r', b') \preceq (r, b)$, $(r', b') \ne (r,b)$, $r' \ne 0$, and $b' \ne 0$], along with the base cases $p(r', 0) = 1$ and $p(0, b') = 0$, we have \begin{align} p(r, b) &= \frac{1}{\binom{r+b}{r}} \left(1+ \frac{1}{2} \sum_{k=1}^{b-1} \binom{r+k-1}{r-1}\right) + \frac{1}{2} \frac{1}{\binom{r+b}{r}} \sum_{k=1}^{r-1} \binom{b+k-1}{b-1} \\ &= \frac{1}{\binom{r+b}{r}} \left(1+ \frac{1}{2} \left(\binom{r+b-1}{r} - 1\right)\right) + \frac{1}{2} \frac{1}{\binom{r+b}{r}} \left(\binom{r+b-1}{b}- 1\right) \\ &= \frac{1}{2\binom{r+b}{b}}\left(\binom{r+b-1}{r} + \binom{r+b-1}{b}\right) \\ &= \frac{1}{2}, \end{align} where we used the Hockey-stick identity and Pascal's rule.

Answer 2

At each stage, think of the draw order as determined by a random permutation of the balls (like a deck of cards that gets shuffled). The permutations in which all the red balls come first are in one-to-one correspondence with those in which all the blue balls come first (by reversal), so the probability that the game ends in one step with only blue balls left is equal to the probability that the game ends in one step with only red balls left. In all other cases, we're left with fewer balls in the urn, so the result follows by induction.