Drawing Balls Strategy
Jane Street
You have a jar with 3 +1\$ balls and 2 -1\$ balls inside, you draw one by one without replacement and can stop at any time. How much would you pay to play this game?
Answer
We're asked how much we'd pay to play this game - meaning what is the expected value of this game. But note there is a strategy element to this, as we get to choose when we stop playing the game. So effectively the question is asking what would be your optimal strategy and then if you were to play this strategy, how much would you gain / lose on average.
Our rule should be something like: if the expected value of continuing to play the game is negative, stop playing. So we need the expected value of continuing to play at any point. When you start off, you have 3 +1\$ balls and 2 -2\$ balls, meaning you have $\frac{3}{5}$ chance of drawing a +1\$ ball and continuing to play the game with 2+1\$ and 2 -2\$ balls; and $\frac{2}{5}$ chance of drawing a -1\$ ball and continuing to play with 3 +1\$ balls and 1 -1\$ ball. If we denote $EV(a,b)$ as the expected value of the game when you have a +1\$ balls and b -1\$ balls left, we can write: $$EV(a,b) = \frac{a}{a+b}(+1+EV(a-1,b))+\frac{b}{a+b}(-1+EV(a,b-1))$$So notice we have a recurrence relation, where each subsequent EV will be calculated the same way. We can represent this visually as a tree of possible outcomes:
Each branch up implies drawing a +1\$ ball, whereas downward branches are for drwagin a -1\$ ball. At each node, we continue to play if the expected value of continuing to draw is positive. Note therefore the boundary conditions: if we are left with no +1\$ balls (i.e. EV is of the form $EV(0,b)$), the expected value of continuing to draw would be -b, so in this case we stop playing under optimal strategy and set $EV(0,b)=0$. Similarly, if we only have +1\$ balls left (i.e. $EV(a,0)$), we should continue to draw and with probability 1 we will gain +a\$. Therefore we set $EV(0,b)=0$ and $EV(a,0)=a$.
As you see all roads in the tree lead to boundary condition of one of these two forms. This means we can work backwards to calculate previous nodes from the future ones, using the recurrence relation we've defined: $$EV(1,1)=\frac{1}{2}(+1+EV(0,1)) + \frac{1}{2}(-1+EV(1,0))=\frac{1}{2}$$Continuing down this line of reasoning, we can work backwards through all nodes: $$EV(1,2)=\frac{1}{3}(+1+EV(0,2))+\frac{2}{3}(-1+EV(1,1))=0$$ $$EV(2,1)=\frac{2}{3}(+1+EV(1,1))+\frac{1}{3}(-1+EV(2,0))=\frac{4}{3}$$ Now that we have $EV(1,2)$, $EV(2,1)$ and $EV(3,0)$ we can determine $EV(2,2)$ and $EV(3,1)$: $$EV(2,2)=\frac{2}{4}(+1+EV(1,2)) + \frac{2}{4}(-1+EV(2,1))=\frac{2}{3}$$ $$EV(3,1)=\frac{3}{4}(+1+EV(2,1))+\frac{1}{3}(-1+EV(3,0))=\frac{9}{4}$$Now we can retract to the initial starting point, which we are asked for: $$EV(3,2)=\frac{3}{5}(+1+EV(2,2))+\frac{2}{5}(-1+EV(3,1))=\frac{3}{2}$$