You have 4 cards, 2 black and 2 red. You play a game where during each round you draw a card. If it's black, you lose a point. If it's red, you gain a point. You can chose to stop at any time. What's the expected value of this game?
What is the best way to solve this question? I tried drawing a tree diagram and I am not able to use the various cases that are possible.
I'm assuming you don't replace a card once it's drawn. There are $9$ possible states of the deck, telling you which cards are in it:
I'll denote these as $(b,r)$, where $b$ is the number of black cards and $r$ the number of red cards. Let $V(b,r)$ be the expected value to you of state $(b,r)$.
If you choose to draw a card in state $(b,r)\ne (0,0)$, with probability $b/(r+b)$ you draw a black card, losing $1$ point, and then you are in state $(b-1,r)$, while with probability $r/(r+b)$ you draw a red card, gain $1$ point, and go to state $(b,r-1)$. The expected value is thus
$$ \dfrac{b}{r+b} (-1 + V(b-1,r)) + \dfrac{r}{r+b} (1 + V(b,r-1))$$
However, if this is negative, you should stop. Thus
$$ V(b,r) = \max\left(0, \dfrac{b}{r+b} (-1 + V(b-1,r)) + \dfrac{r}{r+b} (1 + V(b,r-1))\right) $$
with $V(0,0) = 0$.
I get $V(2,2) = 2/3$.
You should never stop when you are losing because you can guarantee $0$ by drawing all the cards. Clearly you should stop after three cards if you are $+1$ or after two cards if you are $+2$ as you can only get worse. You should not stop if you are even after two because you can only get better. The only question is whether to draw if you are $+1$ on the first draw.
We compute the expectation if you draw red first and draw again. You have $\frac 13$ chance of drawing red again and ending $+2, \frac 13$ chance of drawing two blacks next and ending $0$, and $\frac 13$ chance of drawing black-red and ending $+1$. This gives $+1$, so it doesn't matter whether you draw or not.
Now we compute the expectation at the start. If you draw red (probability $\frac 12$) you end $+1$. If you draw black and then draw two reds (probability $\frac 16$) you end $+1$ Otherwise you break even with probability $\frac 13$. Overall, the value is $\frac 23$
With intelligent play, you never have a negative result (as you can always continue until all the cards have been dealt. The best play expectation is $\frac12$ for the chance of the first card being good, plus $\frac16$ for the chance that the first card is bad but the next two are good, for a total of $\frac23$.
Assume you say “stop” and collect your money at the optimal point, but keep drawing cards until they’re gone. There are six equally likely orders in which your four picks will occur: $rrbb, rbrb, rbbr, brrb, brbr, bbrr$. If you always “stop” after you see the second red card (you should never proceed, since the remaining cards are all black), your winnings will be, respectively, $2, 1, 0, 1, 0, 0$, with an average of $\frac{2}{3}$ dollars. The only hand on which you could have done better by stopping sooner is $rbbr$, but if you try to capitalize on that with a new strategy (stopping if the first card chosen is red, and if not, continuing through the second red card), then your winnings become $1,1,1,1,0,0$, which has the same expectation.
We can represent the process as a movement in a 3 x 3 table as below, where moving right means picking a red card, and moving down means picking a black card.
You only move down or right, and the probability of moving in a certain direction is proportional to the number of cells in that direction.
We start by filling the table with the number of points you get if you stop at each given cell.
$$ \begin{array}{|c|c|c|} \hline \phantom{-}0 \phantom{| \frac{2}{3}} & \phantom{-}1 \phantom{| 1} & \phantom{-}2 \phantom{| 1} \\ \hline -1 \phantom{| \frac{1}{3}} & \phantom{-}0 \phantom{| \frac{1}{2}} & \phantom{-}1 \phantom{| 0} \\ \hline -2 \phantom{| 0} & -1 \phantom{| 0} & \phantom{-}0 \phantom{|0}\\ \hline \end{array} $$
We can now compute the expected return of continuing from each point.
We start from the bottom right (always 0), and proceed upwards and leftwards.
At each state, the expected return of picking one more card is the weighted average between the best result of going down and the best result of going right.
We end up with the following:
$$ \begin{array}{|c|c|c|} \hline \phantom{-}0 | \frac{2}{3} & \phantom{-}1 | 1 & \phantom{-}2 | 1 \\ \hline -1 | \frac{1}{3} & \phantom{-}0 | \frac{1}{2} & \phantom{-}1 | 0 \\ \hline -2 | 0 & -1 | 0 & \phantom{-}0\\ \hline \end{array} $$
The left numbers are the outcome of stopping at each point, as before. The right numbers are the expected outcomes of continuing to play.
In filling this table, your last computation should be for the top left cell. There, if we choose to move, we have $\frac{1}{2}$ of chance of going right, which can give us 1 point in average, and $\frac{1}{2}$ of chance of going down, which can give us $\frac{1}{3}$ (by not stopping).
The expected number of points for an intelligent player in this game is thus $\frac{2}{3}$.
We conclude that the only places you must stop are the cells in the right column (that is, after having picked two red cards). These are the cells where the left number is greater than the right one.
If you start by picking a red card, choosing to continue does not change your expected outcome (you have equal chances of ending up with 0, 1 or 2 points).
In all other cases, you should continue to play.
Expected value is defined as probability of the event times the value of the event. However, since you can decide when to end the game, this is hard to compute. That is, of course, if you do not specify that we play intelligently.
EDIT: Since this is in essence a chance game, there would really not be a set "intelligent" way to play. However, one good way to limit our possibilities is to use the strategy of once we get the first black card, we end the game. This is because the expected value at the beginning of the game is $0$ (make sure you see why this is true). Now we see that the probability we end after one round is $\frac{1}{2},$ and our net earnings is $-1,$ so this contributes $-\frac{1}{2}$ to the overall. For two rounds and stop, this will contribute $0$ (you win, then you lose). For three rounds, the addition is $2 \times \frac{1}{4}.$ For four, it is $3 \times \frac{1}{8}.$ In general, the expected sum is $$-\frac{1}{2} + \sum_{n = 3}^{\infty} \frac{n}{2^{n}},$$ which is $\boxed{\frac{1}{2}}.$ This should also make some intuitive sense.
