9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ If there are r red cards and b black cards left, so far 26-r red cards and 26-b black cards where drawn, so n=26-r - (26-b)=b-r. Note that because of symmetry, if you are currently ahead, you expectation for the future is negative and if you are currently behind, you expection is positive. $\endgroup$
    – quarague
    Jul 9, 2022 at 10:39

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Why shouldn't we stop after drawing a red card on the first turn? If we continue, then on the second turn, the probability of drawing a red card is less than 50%. Wouldn't it be better to stop, pocket the dollar, and restart another game with 52 cards so that our probability of drawing a red card is 50%? $\endgroup$
    – JLee
    Jul 9, 2022 at 12:08
  • $\begingroup$ @JLee "What is the optimal stopping rule in terms of maximizing expected payoff and how much are you willing to pay for this game?" Certainly if any game is free to play and can be played repeatedly as many times as you like, you can always stop while you are ahead and repeat. That doesn't tell you how much you should pay to play or how to maximize the value of each attempt. After drawing one red card, there are so many cards left in the deck, you are likely to eventually be up more than one even if it's less than 50% after just the next draw (and the stakes are low since you can only lose 1). $\endgroup$
    – tehtmi
    Jul 9, 2022 at 12:18
  • 1
    $\begingroup$ ok, I didn't interpret that quoted statement as there being a separate price to even begin playing the game. I was thinking that the "price" was how ever much one would lose in the game, but it does make more sense that each game with 52 cards would have a separate price. There are only 495,918,532,948,104 ways to order 26 red and 26 black cards. Let me just check them all real quick. :) $\endgroup$
    – JLee
    Jul 9, 2022 at 12:26
9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ That's some slightly cursed but quite clever code. $\endgroup$
    – A username
    Jul 10, 2022 at 3:35
  • $\begingroup$ Can we draw some human-friendly strategy out of this? $\endgroup$
    – justhalf
    Jul 10, 2022 at 5:11
  • $\begingroup$ @justhalf See my answer. $\endgroup$
    – isaacg
    Jul 10, 2022 at 17:59
2
$\begingroup$

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%.

$\endgroup$
2
  • $\begingroup$ You can do better than that. It's possible to make a profit even if you pay $2.62 for each pass through the deck. $\endgroup$ Jul 9, 2022 at 15:52
  • 1
    $\begingroup$ My answer was made with the (mis)understanding that the game is free, like most casino games, but that the cost would come in the form of losses. $\endgroup$
    – JLee
    Jul 9, 2022 at 16:36
2
$\begingroup$

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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.