Expected Value : Poker

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.

With an initial bankroll of $$100$, the simple strategy to go all-in when the outcome is certain, i.e. when there is only one color left, else bet nothing, will yield the maximal expected value of $$267$, with a standard deviation of $$94.3$.

In fact, there are in infinite number of strategies that will yield the same optimal expectation (but different variance).

While we cannot increase the expectation further, we can find the strategy of these that has the lowest variance. In fact, there is a unique strategy that will yield a guaranteed final bank-roll of $$267$ (zero variance). This strategy is to always bet on guaranteed outcomes (as before), except for the second card where you bet 1/3 of your bankroll on the color not seen on the first card. This kills off the variance and ensured a non-stochastic final bankroll.

---

Figure 1. The state is the number of colored cards remaining (black, red). The green function $E(black, red; x)$ is the expected final bankroll if starting with $x$ in that state.

(0, 0) Consider starting with $x$ when there are no cards left (0, 0). There is nothing do bet on, so the final bankroll will be unchanged at $x$. So $$E(b,r,x) = E(0, 0, x) = x.$$

(1, 0) Consider starting with $x$ when there is one black cards left (1, 0). Outcome is certain so we go all-in, so the final bankroll will be $2x$. So $$E(1, 0,x) = 2x.$$

(0, 1) Same as (1,0) due to symmetry. So $$E(0,1,x) = 2x.$$

(2, 0) Consider starting with $x$ when there are two black cards left (2, 0). Next outcome is certain so we go all-in twice in a row, so $E(2,0,x) = 4x$. Note that this is the same as going all on the first card, realize $2x$ and start a new game at (1,0). So $$E(2,0,x) = 1 cdot E(1,0, 2x) = 2 (2x) = 4x.$$

(0, 2) Same as (2,0) due to symmetry. So $$E(0,2,x) = 4x.$$

(1, 1) Consider starting with $x$ when there is one black and one red card left (1, 1). Next outcome is uncertain with 50/50 and the value at the next state is the same for either outcome (symmetry), so the value is invariant to what we bet. Note that while the expected value doesn't depend on what we bet, the variance is increasing by betting, so we prefer to bet zero. So $$E(1,1,x) = E(1,0, x) = 2x.$$

To convince yourself, assume you bet $0 leq wleq x$ on red; if you win you have $x+w$ to invest at state $(1,0)$; if you lose you have $x-w$ to invest at state $(0,1)$. If you bet on red the expected value is $E(1,1,x)_r = E(1,1,x)| text{"bet } w text{ on red"} = tfrac{1}{2} E(1,0, x+w) + tfrac{1}{2} E(0,1, x-w) = 2x$. Due to symmetry, $E(1,1,x)_b = E(1,1,x)| text{"bet } w text{ on black"} = 2x$. Note that both values are equal, and invariant to the betting size. So we are indifferent to whether we bet or not.

Since we have the liberty to chose the bet arbitrarily without affecting the expected value, let us see if we can decrease the variance instead. The 2nd moment is given by $M_2(1,1,x)| text{bet } w text{ on red} = tfrac{1}{2} E(1,0, x+w)^2 + tfrac{1}{2} E(0,1, x-w)^2 = 4(x^2 + w^2)$, and so variance is $V(1,1,x)| text{"bet } w text{ on red"} = 4w^2.$ So we set $w=0$ to have minimum variance (remember expectation is unaffected). We do the same for betting black, byt due to symmetry, we see that we would also bet zero on black (betting zero on red = betting zero on black).

(2, 1) Consider starting with $x$ when there are two black and one red card left. If you bet on red then $E(2,1,x)| text{"bet } w text{ on red"} = tfrac{1}{3}E(2,0, x+w) + tfrac{2}{3}E(2,0, x-w) = tfrac{8}{3}x.$ If you bet on black then $E(2,1,x)| text{"bet } w text{ on black"} = tfrac{1}{3}E(2,0, x-w) + tfrac{2}{3}E(2,0, x+w) = tfrac{8}{3}x.$ Value is invariant of what card you bet on and betting size.

Since we have the liberty to chose the bet arbitrarily without affecting the expected value, let us see if we can decrease the variance instead. If you bet on red then $V(2,1,x)| text{"bet } w text{ on red"} = tfrac{1}{3}E(2,0, x+w)^2 + tfrac{2}{3}E(2,0, x-w)^2 - left(tfrac{8}{3}x right)$ has minimum variance of $tfrac{8}{9}x^2$ at $w=x$. If you bet on black then $V(2,1,x)| text{"bet } w text{ on black"} = tfrac{1}{3}E(2,0, x-w)^2 + tfrac{2}{3}E(2,0, x+w)^2 - left(tfrac{8}{3}x right)$ has zero minimum variance at $w=x/3$. So we pick betting on black since expected value is the same for both bets, but we can kill off the variance by betting on black.

$$E(2,1,x) = tfrac{8}{3}x.$$

(2, 2) Due to similar reasoning as (1,1), we bet nothing $$E(2,2,x) = tfrac{8}{3}x = 2.67x$$

---

In general we have

begin{align} E(b, r, x) &= max left(max_w E(b,r,x)_{text{red}}, ;max_w E(b,r,x)_{text{black}} right) end{align} where begin{align} E(b,r,x)_{text{red}} &= tfrac{r}{b+r}E(b, r-1, x+w) + tfrac{b}{b+r}E(b-1, r, x-w), \ E(b,r,x)_{text{black}} &= tfrac{r}{b+r}E(b, r-1, x-w) + tfrac{b}{b+r}E(b-1, r, x+w). end{align} and boundary conditions begin{align} E(0,0) &= x \ E(r,b) &= 0 text{ if } r<0 text{ or } b<0 end{align}

---

from scipy.optimize import minimize

def pr_black(b, r):
    return b / (b + r)

def pr_red(b, r):
    return r / (b + r)

def E_bet_black(w, x, b, r):
    w = w[0]
    return pr_black(b,r) * E(b-1, r, x + w) + pr_red(b,r) * E(b, r-1, x - w)

def E_bet_red(w, x, b, r):
    w = w[0]
    return pr_black(b,r) * E(b-1, r, x - w) + pr_red(b,r) * E(b, r-1, x + w)

cache = {}
def E(b, r, x):
    if (b, r) in cache:
        return cache[(b,r)]*x # Assume linear value mapping.
    elif r==0 and b==0:
        return x
    elif r<0 or b<0:
        return 0.0
    else:
        bnds = [(0, x)]
        res_black = minimize(lambda w,x,b,r: -E_bet_black(w,x,r,b), x0=x/2, args=(x,b,r), bounds=bnds)
        res_red = minimize(lambda w,x,b,r: -E_bet_red(w,x,r,b), x0=x/2, args=(x,b,r), bounds=bnds)
        val_black, w_black = -res_black.fun, res_black.x
        val_red, w_red = -res_black.fun, res_black.x
        color,w,value = ('black', w_black, val_black) if val_black > val_red else ('red', w_red, val_red)
        cache[(b, r)] = value/x
        return value
    
b, r = (2, 2)
x = 100

print(    'E(b,r,x) = E({},{},{}) = {}'.format(b,r,x, round(E(b, r, x), 2))    )

E(b,r,x) = E(2,2,100) = 266.67