Expected Value : Poker You are dealt $4$ cards face down on a table. You know that $2$ are red and $2$ are black. Let’s say you are given $100 to bet on this game and you are able to bet after each card is dealt and before the next one is on whether the outcome will be red or black. If you play this game optimally, what’s your expected value?
Thinking along the lines that at first there is 1/2 probability of red or black. If first is red then second round has probability of picking black 2/3. If second round is black then 1/2 probability that 3 rd round has black or red. Final round will have probability 1. I was thinking that this was optimal play.
Edit - actually I think I messed up round 3 probability.
 A: This is an extension to a classical dynamic programming problem that involves optimal stopping. I will present a solution that works in the general case.
Let $f(r, b, x)$ denote the optimal expected value for $r$ and $b$ remaining red and blue cards, respectively when we have $x$ remaining dollars. Under this notation, we want to compute $f(2, 2, 100)$. Note that we have the following recurrence:
$$f(r, b, x) = \max_{0 \leq y \leq x}\left\{\frac{r}{r + b} \cdot (y + f(r - 1, b, x + y) + \frac{b}{r + b} \cdot f(r, b - 1, x - y), \frac{b}{r + b} \cdot (y + f(r, b - 1, x + y) + \frac{r}{r + b} \cdot f(r - 1, b, x - y)\right\}.$$
since we have the option to bet anywhere between $0$ and $x$ dollars (inclusive) at any given state, and it doesn't make sense to bet on the less probable option. Moreover, we have the base cases $f(1, 0, x) = 2x$ and $f(0, 1, x) = 2x$ since we're certain to make money when there's only one card remaining (just bet that color).
You can use a dynamic programming algorithm that runs in $\mathcal{O}(RBM)$ time, where $R$ denotes the initial number of red cards, $B$ denotes the initial number of blue cards, and $M$ denotes the initial bankroll.
