Yet Another Card Payoff Game

Question

From A Practical Guide to Quant Interviews:

A casino offers yet another card game with the standard 52 cards (26 red, 26 black). The cards are thoroughly shuffled and the dealer draws cards one by one. (Drawn cards are not returned to the deck.) You can ask the dealer to stop at any time you like. For each red card drawn, you win \$1; for each black card drawn, you lose $1. What is the optimal stopping rule in terms of maximizing expected payoff and how much are you willing to pay for this game?

My approach: If I have n dollars currently and r red cards left and b black cards left, my expected payoff at this stage will be $(r/(r+b)) * (n+1) + (b/(r+b)) * (n-1)$ and this should be greater than $n$. I get after solving $b<0$, which is impossible. I don't understand why I am wrong.

Answer 1

If I have n dollars currently and r red cards left and b black cards left, my expected payoff at this stage will be (r/(r+b))∗(n+1)+(b/(r+b))∗(n−1)

This is how much money will win on average if you draw one more card and then stop (and as you note, you should compare this to $n$, the amount of money you get by stopping now). But, maybe you shouldn't stop after the next draw. For example, as JLee points out, if you are behind, you can continue playing until the end of the deck to guarantee breaking even. So, this is not the correct valuation of the position.

I get after solving b<0, which is impossible.

$(r/(r+b))(n+1)+(b/(r+b))(n−1)>n$ simplifies to $(r-b)/(r+b) > 0$ or $r > b$. This makes sense: if you the next card is more likely to be red, you will likely pull ahead with the next draw and vice versa; but as mentioned above, this does not fully characterize the problem.

it would helpful if someone could point me in the right direction.

It is natural to solve this kind of problem using dynamic programming. The value of a position is the value of that position under optimal play, so the maximum between the value when stopping versus the value when drawing and then continuing to play optimally. The value when stopping is simple. The value when drawing and continuing to play optimally can be computed recursively as a "subproblem": it is the weighted average of the values of successor positions according to their probabilities of occurring. This will set up a recursive relation that can solve the problem, and the strategy at each position is given by comparing the value when staying versus the value when drawing.

(Maybe there is also a more clever solution or easy closed form simplification of the dynamic programming relation; who knows? But for this problem, brute force dynamic programming is easily tractable for a computer although it would be very tedious by hand.)

P.S. The answer will not tell you to stop after drawing a red card on the first turn.

Answer 2

Dynamic programming solver:

// Calculate optimal payoff if there are 'r' red cards and 'b' black cards left in the deck
function f(r, b) {
  if (r == 0) return 0;
  if (b == 0) return r;
  const k = r + ' ' + b;
  if (k in f) return f[k];
  return f[k] = Math.max(0, (r * (1 + f(r-1,b)) + b * (f(r, b-1)-1))/(r+b));
}

f(26, 26) = 2.624475548993925

---

Given R red cards, how many black cards should there be before I stop?

Array.from({length:27}, (_,r) => Array.from({length:27}, (_,b) => b).filter(b => f(r,b) == 0)[0])

[0, 2, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 25, 26, undefined, undefined, undefined, undefined, undefined, undefined]

(So with 0 red cards left, stop on 0 or more black cards left. With 1 red card left, stop if there are 2 or more black cards left. ... With 20 red cards left, stop if there are 26 black cards left. With more than 20 red cards left, keep drawing.)

Alternately, minimum number of red cards that can be left, to keep playing with B black cards:

Array.from({length:27}, (_,b) => Array.from({length:27}, (_,r) => r).filter(r => f(r,b) == 0).pop())

[0, 2, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 25, 26, undefined, undefined, undefined, undefined, undefined, undefined]

Looked for a while; the stopping range increases (with around 1000 red and 1000 black, stop if there are about 38 more black than red), but I couldn't find identify the rule.

Answer 3

I wanted to summarize @ralphmerridew's optimal strategy in a more human-friendly way, as requested by @justhalf.

Call the "excess" how many more red than black cards have been drawn, or equivalently how many more black than red cards are left in the deck. This is our profit, if we stop now.

Then our strategy is based on the current excess:

• Excess 6: Stop.
• Excess 5: Stop if ≥ 8 red drawn (≤18 red in deck).
• Excess 4: Stop if ≥ 14 red drawn (≤12 red in deck).
• Excess 3: Stop if ≥ 19 red drawn (≤7 red in deck).
• Excess 2: Stop if ≥ 23 red drawn (≤3 red in deck).
• Excess 1: Stop if ≥ 25 red drawn (≤1 red in deck).
• Excess ≤0: Don't stop.

Here's an equivalent but easier to memorize formulation:

Call the excess x. Multiply x by 2x+1, then divide by 3, giving $(2x^2 + x)/3$. If the number of red cards in the deck is less than or equal to $(2x^2 + x)/3$, stop. Otherwise, continue.

For instance, suppose the current excess is 4. We then calculate a threshold of $4 * 9 / 3 = 12$. If the number of red cards in the deck is at most 12, we stop. Otherwise, we continue.

---

This strategy is equivalent to this array given by @ralphmerridew:

Given R red cards [left in the deck], how many black cards [left in the deck] should there be before I stop?

[0, 2, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 25, 26, undefined, undefined, undefined, undefined, undefined, undefined]

Answer 4

Notice that you can never lose any money in this game because if you are down, simply play on until you break even, which you are guaranteed to do, even if you have to play out the whole deck.

The best strategy is to draw until you are $1 in the positive, and then quit the game and start another, where your win probability returns to 50%. When you are in the positive, your win probability is less than 50%.