Playing with Balls of Two Colors

Imagine that prior to every round, the remaining balls are lined up in a random order and you simply pick the balls from left to right. A round corresponds to a sequence of balls of the same color. The balls before the last round are one color, the balls before the penultimate round are in two groups of different colors, say black balls on the left, followed by white balls on the right. It could be the other way round. Regardless of the size of each group, these two orders are equally likely. But the order of the groups does impact the result: in one case, the last ball will be white, in the other it will be black. Thus the probability of either is $\displaystyle \frac{1}{2}.$

Let an urn contain $m \gt 0$ black balls and $n \gt 0$ white balls. Let $u_{mn}(b)$ be the probability that the sequence of balls being discarded should begin and end with a black ball. Let $u_{mn}(w)$ be the probability that it should begin with a white ball and end with a black ball. We require $u_{mn}= u_{mn}(b) + u_{mn}(w).$ We have

(1)

$\displaystyle u_{mn}(b)=\frac{m}{m+n}\left(u_{m-1,n}(b)+\frac{n}{m+n-1}u_{m-1,n}\right).$

Equation (1) also holds if $m=1$ and $n\ge 1$ since both sides are zero.

Similarly, for $m\ge 1,$ $n\ge 2,$

(2)

$\displaystyle u_{mn}(w)=\frac{m}{m+n}\left(u_{m,n-1}(w)+\frac{m}{m+n-1}u_{m,n-1}\right)$

and again, since $\displaystyle u_{m1}(w)=\frac{1}{m+1},$ $u_{m0}(w)=0$ and $u_{m0}=1,$ equation (2) holds if $m\ge 1,$ $n=1.$

The problem is analogous to the Lost Boarding Pass problem.

Balls come in runs of the same color. The first passenger gets somebody's seat, some after him get in their seats until comes a fellow on whose seat sits #1. The round starts anew. The last fellow to enter the plane has the probability of 1/2 to get into his own seat. This probability is independent of how many people sit in their assigned seats and how many are in somebody else's.

The analogy is in the sequence of runs/rounds. The passenger runs can be looked at as the balls of the same color.

Consider the case of one white $(W)$ ball and two black $(B)$ balls. You have four possible sequences in which the balls are drawn from the urn. (a dash designates an interruption due to a color change so that the ball before a dash is back into the urn):

$\displaystyle \begin{array}{c|c|c} Action & Result & Probability\\ \hline WB-BB & win & 1/3\\ BW-WB-B & win & 1/6\\ BW-BW-W & loss & 1/6\\ BBW-W & loss & 1/3 \end{array}$

Two white balls and one black ball:

$\displaystyle \begin{array}{c|c|c} Action & Result & Probability\\ \hline WB-BW-W & loss & 1/6\\ WB-WB-B & win & 1/6\\ BW-WW & loss & 1/3\\ WWB-B & win & 1/3 \end{array}$

Three white balls and one black ball:

$\displaystyle \begin{array}{c|c|c} Action & Result & Probability\\ \hline WWWB-B & win & 1/4\\ WWB-WB-B & win & 1/8\\ WWB-BW-W & loss & 1/8\\ WB-WWB-B & win & 1/12\\ WB-WB-WB-B & win & 1/24\\ WB-WB-BW-W & loss & 1/24\\ WB-BW-WW & loss & 1/12\\ BW-WWW & loss & 1/4 \end{array}$

The penultimate round will begin with an urn with composition of black and white balls. For each of these urn compositions (not equally likely as penultimate rounds), there are just two ways to have a penultimate round draw, and they are equally likely from that urn. The two ways will have different pay-offs.

Let $P(B,W)$ be the probability of winning given that the urn contains $B$ black balls and $W$ white balls. We can compute $P(B,W)$ as follows

$\displaystyle P(B,W)=\frac{B}{B+W}V(B-1,W,black)+\frac{W}{B+W}V(B,W-1,white)$

where $V(B,W,x)$ is the probability of winning given that there are $B$ black balls and $W$ white balls remaining and the last ball drawn is of color $x$. $V(B,W,x)$ can be calculated as

$\displaystyle \begin{align} V(B,W,black)&=\frac{B}{B+W}V(B-1,W,black)+\frac{W}{B+W}P(B,W)\\ V(B,W,white)&=\frac{B}{B+W}P(B,W)+\frac{W}{B+W}V(B,W-1,white) \end{align}$

Boundary conditions are given by

$V(B,0,x)=P(B,0)=1\\ V(0,W,x)=P(0,W)=0$

Plugged the formulas into a spreadsheet and got $P(B,W)=0.5$ for $B$ and $W$ greater than zero and less than 30 (my guess is that it is always the case).

This is a problem from P. Winkler's Mathematical Mind-Benders (A K Peters/CRC Press, 2007, pp 76, 79-80) and also from M. Gardner's The Colossal Book of Short Puzzles and Problems (Norton, 2006, 2.16 from Ch 1).

Gardner announces the result and refers to a paper "A Sampling Process" by B. E. Oakley and R. L. Perry in The Mathematical Gazette (February 1965, 42-44), see the Recursion from the original above. Winkler refers to Gardner and gives a solution by Sergiu Hart from the Hebrew University of Jerusalem. Solution 1 is a paraphrase of that in Winkler's.

Winkler mentions Hart's observation that the game is isomorphic in a sense to the Lost Boarding Pass Problem.

P. Nahin offers that as a Challenge Problem (#10) in his Will You Be Alive In 10 Years From Now? (Princeton University Press, 2013) where he offers computer similation that confirms the probability of $\displaystyle \frac{1}{2}.$ Like Gardner and Winkler, he refers to the long proof by Oakley and Perry.

I am grateful to Joshua B. Miller for a fruitful discussion. Examples above and Solution 2 are his. Joshua acknowledges the team work on part of Thamizh Kudimagan.

The Experimental setup is by Alejandro Rodríguez.