3
$\begingroup$

In a bag there are $a$ red balls and $b$ blue balls ($a,b>0$). You conduct the following process.

  1. Randomly fetch a ball from the bag, record the colour as the current colour. And throw it away. Go to 2.

  2. If there's no ball left, break. Otherwise, randomly fetch a ball from the bag. If the colour coincides with current colour, throw it away, and repeat 2; otherwise, put back the ball, and go back to 1.

Qs:

  • What's the probability that the last ball fetched is red, in terms of $a,b$?

    (I seem to lack the necessary combinatorial tools to tackle it. Yeah I deem it to be combinatorial. Initially thought of constructing some kind of martingale based on the balls fetched and apply optional stopping, but didn't work out...)

  • Does a closed form solution exist?

    (I have absolutely no idea other than imagination about a numerical implementation.)

  • Is it generalisable to multicoloured balls (more than two) cases?

    (This one just for fun.)

$\endgroup$
  • 1
    $\begingroup$ I wish you much fun to solve this exercise. Cheers! $\endgroup$ – callculus May 10 at 17:42
  • $\begingroup$ Cool problem. I'm not sure the result extends to more than two color; it might, but the proof is not obvious to me at the moment. $\endgroup$ – Brian Tung May 10 at 22:25
3
$\begingroup$

This is, I think, a slightly easier strong induction than Ingix's.

We use the same basis: By symmetry, state $(1, 1)$ is equally likely to have its last ball be red or blue.

The induction step is as follows: From state $(r, b)$, the state when we next return to step $1$ of the algorithm has some distribution over the states

$$ (r, 0), (r, 1), (r, 2), \ldots, (r, b-1), \\ (0, b), (1, b), (2, b), \ldots, (r-1, b) $$

By hypothesis from strong induction, each of these states is equally likely to have its last ball be red or blue, except for the two states $(r, 0)$ and $(0, b)$. Since $(r, 0)$ is all red and $(0, b)$ is all blue, the color of the last ball depends on how likely we are to get to those two states.

However, those two states must be equally likely: Getting to $(r, 0)$ corresponds to those sequences of balls where all the blue balls come before all the red ones, and getting to $(0, b)$ corresponds to those sequences where all the red balls come before all the blue ones. Thus $(r, b)$ is equally likely to have its last ball be red or blue, too.

$\endgroup$
  • $\begingroup$ Nice. I don't quite get the last paragraph though. Why are the two types of sequences equally likely? This doesn't look very obvious to me. $\endgroup$ – Vim May 11 at 0:09
  • $\begingroup$ Ok I get it. They are both $r!b!$ out of $(r+b)!$ permutations. $\endgroup$ – Vim May 11 at 0:54
  • $\begingroup$ By the way I also think the induction argument extends naturally to multicoloured cases. For $k$ colours, the base is $(1,\cdots,1)\in\Bbb N^k$. We first induct on the first coordinate, to prove the statement holds true for any $(n_1,1,1,\cdots,1)$; given this, we induct on the second coordinate, to prove for $(n_1,n_2,1,\cdots,1)$. And so on. $\endgroup$ – Vim May 11 at 1:21
  • $\begingroup$ (continued). For edge states with only colour $i$ completely eliminated eg. $(n_1,\cdots,n_{i-1}, 0, n_{i+1},\cdots, n_k)$ where only the $i$-th coordinate is zero, this reduces to a $k-1$ colour case. So we need an additional induction on the dimensionality. I'll try to flesh out an complete answer later. $\endgroup$ – Vim May 11 at 1:41
  • 1
    $\begingroup$ +1. I once took a probability course from Gian-Carlo Rota, and instead of proving things by equations, he would prove things by "pure reason" alone (as much as possible). your proof would qualify. :) on another note, and @Vim - sadly the result doesn't generalize to $>2$ colors -- see my answer for a counter-example $\endgroup$ – antkam May 15 at 12:16
3
$\begingroup$

The solution for the 2-color case is surprisingly:

If $a,b > 0$ then the probability to fetch either color last is $\frac12.$

This can be proved via strong induction on $a+b$.

Induction start: For $a=b\;(=1)$ the probability is $\frac12$ for symmetry reasons, as the algorithm doesn't handle any color special.

Induction step: Assume the probability to fetch a red ball last is $\frac12$ $\forall a,b > 0, a+b < n$ for some $n > 2$. Consider any $a,b > 0, a+b = n$.

Let's first consider that happens when we fetch a red ball in step 1 at the beginning! In that case, in step 2 there are 2 possibilities:

a) all the remaining $a-1$ red balls are fetched before finally a blue ball is fetched (and put back), or

b) there is still at least one red ball in the bag at end of step 2, when we return to step 1.

For a) to happen, the first ball fetched in step 2 must be red (probability $\frac{a-1}{a+b-1}$), and the second ball fetched must be red (probability $\frac{a-2}{a+b-2}$, if first fetched ball was red), a.s.o until the $(a-1)$-st ball must be red (probability $\frac{1}{b+1}$, if all previously fetched balls were red). Overall, the probability that case a) happens is

$$p_{red,a}=\frac{a-1}{a+b-1}\frac{a-2}{a+b-2}\ldots\frac{1}{b+1}=\frac{(a-1)!\,b!}{(a+b-1)!}$$

Since a) and b) are complementary events, we have

$$p_{red,b}=1-p_{red,a}.$$

If a) happens, we have no longer any red balls when we return to step 1), so the probability to fetch a red ball last is $0$. For case b), we have still $b$ blue balls and some number $0 < a' \le a-1$ of red balls, so by induction hypothesis the probability to fetch a red ball last is $\frac12$. That means the probability to fetch a red ball last (provided a red ball was fetched first) is

$$p_{red}=0p_{red,a} + \frac12p_{red,b}=\frac12 \left(1-\frac{(a-1)!\,b!}{(a+b-1)!}\right).$$

If we consider the case of fetching a blue ball first in step 1, we get a similar partition into to possibilities as before

a) all other blue balls are fetched in step 2 before we return to step 1, or

b) there is still at least one blue ball in the bag at end of step 2, when we return to step 1.

Case a) happens with probability

$$p_{blue,a}=\frac{(b-1)!\,a!}{(a+b-1)!}$$

(same derivation as above) and again

$$p_{blue,b}=1-p_{blue,a} = 1-\frac{(b-1)!\,a!}{(a+b-1)!}$$

Now, if case a) happens we are guaranteed to fetch a red ball last; in case b) we are back at the induction hypothesis. This leads to the following formula for the probability that we fetch a red ball last, assuming we fetched a blue ball first:

$$p_{blue}=1p_{blue,a}+\frac12\left(1-p_{blue,a}\right) = \frac12 + \frac12p_{blue,a}= \frac12+\frac12\frac{(b-1)!\,a!}{(a+b-1)!}$$

Now, the probability to fetch a red ball or a blue ball first in step 1 are $\frac{a}{a+b}$ and $\frac{b}{a+b}$, resp. That means we can finally calculate the probability of a red ball being fatched last:

$$ \begin{align} p & = \frac{a}{a+b}p_{red} + \frac{b}{a+b}p_{blue} \\ & = \frac{a}{a+b}\frac12 \left(1-\frac{(a-1)!\,b!}{(a+b-1)!}\right) + \frac{b}{a+b}\left(\frac12+\frac12\frac{(b-1)!\,a!}{(a+b-1)!}\right)\\ & = \frac12\frac{a}{a+b} - \frac12\frac{a!\,b!}{(a+b)!} + \frac12\frac{b}{a+b} + \frac12\frac{a!\,b!}{(a+b)!}\\ & = \frac12\frac{a}{a+b} + \frac12\frac{b}{a+b}\\ & = \frac12. \end{align} $$


I guess there is a much easier solution that uses some equivalent formulation of the algorithm to prove the result in a much shorter way, but I can't think of any at the moment.

$\endgroup$
  • $\begingroup$ @Henry: I also interpreted the problem the same way as Ingix did, and came up with the same result. I think the induction can be made easier in the sense that we don't need the actual probabilities of getting, in one run, to all red or all blue; we just need to show that those are equally probable, and then the result follows. $\endgroup$ – Brian Tung May 10 at 22:24
  • $\begingroup$ Ingix & @BrianTung Ok - I may have read the question wrong and assumed you only did part 2 once each time. I will delete my other comments $\endgroup$ – Henry May 10 at 22:26
3
$\begingroup$

Just a note on the $>2$ colors case: Unfortunately, the symmetry breaks down. :( I.e. it is false that each color "wins" with equal chance even if there are unequal no. of balls.

Consider $2$ Red, $1$ Blue, $1$ Green balls.

  • Prob(next draw is Blue) = Prob(next draw is Green) $= \frac14$.

  • Prob(next 2 draws are Red) $= \frac12 \times \frac13 = \frac16$.

  • In the above cases only $2$ colors are left and they each "win" with prob $\frac12$.

  • Prob(next draw is Red, then next draw is not Red) $= \frac12 \times \frac23 = \frac13$. In this case $3$ colors are left with $1$ ball each, so they each "win" with prob $\frac13$ by symmetry.

  • Overall, Prob(last draw is Blue) $= (\frac14 + \frac16) \times \frac12 + \frac13 \times \frac13 = \frac5{24} + \frac19 = { 23 \over 72} < {24 \over 72} = \frac13$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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