Best game strategy in draws from a bin

game theoryprobabilitystatistics

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?

Best Answer

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.

Related Question