Best game strategy in draws from a bin

Question

A bin has 2 white balls and 3 black balls. You play a game as follows: you draw balls one at a time without replacement. Every time you draw a white ball , you win a dollar, but every time you draw a black ball , you loose a dollar . You can stop the game at any time.Devise a strategy for playing this game which results in an expected profit.

According to my reasoning the best strategy is not to play the game at all : the expected value at every extraction remains the same and it's always negative $$E[X]=\left(\frac{2}{5}\right)*1 +\left(\frac{3}{5}\right)*(-1) =-\frac{1}{5}$$ So since I can treat it as a sum of expectations of random variables ,the best strategy is not to play…so the best expected profit is zero dollars right?

Answer 1

Assume that we have $a$ white balls and $b$ blacks balls. We can choose between two things: to play or not to play. In the first case our profit is $0$. Now assume that we choose to play. With probability $\frac{a}{a + b}$ we gain one dollar and we are left with $a - 1$ balls and $b$ black balls. Next, with probability $\frac{b}{a + b}$ we lose one dollar and we are left with $a$ white balls and $b - 1$ black balls.

This gives the following reccurence formula for $P_{a,b}$, the best expected profit we can get for $a$ white balls and $b$ black balls: $$P_{a,b} = \max\left\{0, \frac{a}{a+b}\left(1 + P_{a-1,b}\right) + \frac{b}{a + b} \left(-1 + P_{a,b - 1}\right)\right\}$$

Now, if we have $a$ white balls and no black balls, then obviously the best we can do is to win $a$ dollars. On the other hand, if there is no white balls, then we should not play at all. I.e., $P_{a,0} = a, P_{0, b} = 0$.

Using these formulas, we obtain:

$$P_{0,0} = P_{0,1} = P_{0,2}=P_{0,3} = 0,$$ $$P_{1,0} = 1, P_{2,0} = 2,$$ $$P_{1,1} = \max\left\{0, \frac{1}{2}(1 + P_{0,1}) + \frac{1}{2}(-1 + P_{1,0})\right\} = \frac{1}{2}, $$ $$P_{2,1} = \max\left\{0, \frac{2}{3}(1 + P_{1,1}) + \frac{1}{3}(-1 + P_{2,0})\right\} = \frac{4}{3},$$ $$P_{1,2} = \max\left\{0, \frac{1}{3}(1 + P_{0,2}) + \frac{2}{3}(-1 + P_{1,1})\right\} = 0,$$ $$P_{1,3} = \max\left\{0, \frac{1}{4}(1 + P_{0,3}) + \frac{3}{4}(-1 + P_{1,2})\right\} = 0,$$ $$P_{2,2} = \max\left\{0, \frac{1}{2}(1 + P_{1,2}) + \frac{1}{2}(-1 + P_{2,1})\right\} = \frac{2}{3},$$ $$P_{2,3} = \max\left\{0, \frac{2}{5}(1 + P_{1,3}) + \frac{3}{5}(-1 + P_{2,2})\right\} = \frac{1}{5},$$

i.e., on average we can gain $1/5$ dollars in the inital game. And the strategy is as follows. Look at the numbers above. Assume that we are left with $a$ white balls and $b$ black balls. If $P_{a,b} > 0$, draw a ball, otherwise stop.

Answer 2

There may be a more elegant and/or general way to do this, but here's a brute-force approach.

Consider the following strategy: Draw balls until you've drawn more white balls than black, or if that's no longer possible, until you've drawn both white balls.

Under this strategy, only the following outcomes are possible:

$\begin{align}\\[1ex] \text{W:} \quad & \text{win \$1} && p=\dfrac{2}{5}\\[1ex] \text{BWW:} \quad & \text{win \$1} && p= \dfrac{3}{5}\cdot\dfrac{1}{2}\cdot\dfrac{1}{3}=\dfrac{1}{10}\\[6ex] \text{BWBW:} \quad & \text{break even} && p= \dfrac{3}{5}\cdot\dfrac{1}{2}\cdot\dfrac{2}{3}\cdot\dfrac{1}{2}=\dfrac{1}{10}\\[1ex] \text{BBWW:} \quad & \text{break even} && p= \dfrac{3}{5}\cdot\dfrac{1}{2}\cdot\dfrac{2}{3}\cdot\dfrac{1}{2}=\dfrac{1}{10}\\[6ex] \text{BWBBW:} \quad & \text{lose \$1} && p= \dfrac{3}{5}\cdot\dfrac{1}{2}\cdot\dfrac{2}{3}\cdot\dfrac{1}{2}\cdot1=\dfrac{1}{10}\\[1ex] \text{BBWBW:} \quad & \text{lose \$1} && p= \dfrac{3}{5}\cdot\dfrac{1}{2}\cdot\dfrac{2}{3}\cdot\dfrac{1}{2}\cdot1=\dfrac{1}{10}\\[1ex] \text{BBBWW:} \quad & \text{lose \$1} && p= \dfrac{3}{5}\cdot\dfrac{1}{2}\cdot\dfrac{1}{3}\cdot1\cdot1=\dfrac{1}{10}\\[1ex] \\ \end{align}$

Then your expected winnings are

$\left( \dfrac{2}{5} + \dfrac{1}{10} \right) * (1) + \left( \dfrac{1}{10} + \dfrac{1}{10} + \dfrac{1}{10}\right) * (-1) = \boxed{\dfrac{1}{5}}$

Answer 3

Draw the possible paths. The rectangles represent the number of white/black balls. Transitions to the left correspond to a white ball extracted (plus one). The numbers in blue are the probabilities.

It's clear that when we have zero white balls we should stop and when we have zero black balls we should continue until extracting all balls. Hence we readily can label the "terminal" states with their final scores (in red). In the $(W=1,B=2)$ case there is a tie, any choosing gives the same expected score.

Then we label the internal states, going upwards. For each state, we have the option of stopping there (computed score in red, top), or to continue (computed expected score in red, bottom). We strike out the worse score, and keep the better one. We go up until the initial state.

The expected score is then $1/5$.

The diagram also shows the optimal strategy: in each (internal) state, we choose to stop if the striken number is at the bottom, otherwise we continue.