# Best game strategy in draws from a bin

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?

• You would be correct if you had to decide when to stop in advance, but you haven't taken advantage of your ability to stop the game at any time (in particular to condition on your draws). For example you might choose to stop if you draw a white ball on the first draw but keep going if you draw a black ball. Oct 1 '19 at 7:56
• Yeah but it's an always losing bet so why should I try to draw a white ball if the expected value is always negative? Oct 1 '19 at 8:00
• I need a deeper insight...I'm not understanding how to treat it Oct 1 '19 at 8:18
• I think that now I'm almost getting it : the fact that you can choose where to stop the game means that you can play just ìf some conditions arise and so in some way you can erase the worst cases choosing the strategy 'inside' the game...so my approach is not correct because I'm following an a priori strategy , is it like this? Oct 1 '19 at 9:39
• Yes, that's what I mean. Oct 1 '19 at 9:40

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.

• Very beautiful way to analyze the situation...thank you!! Oct 1 '19 at 10:38
• I took the liberty of editing a small typo in the main formula. Oct 1 '19 at 15:33

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.

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}

$$\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}}$$