Skip to content

Red Card Black Card Game

Level: L3-L5 Topics: Dynamic Programming, Probability, Expected Value, Game Theory

Problem Statement

You have a shuffled deck containing an equal number of red and black cards. You draw cards one at a time from the top:

  • Drawing a red card: you gain $1.
  • Drawing a black card: you lose $1.

You can stop at any time and keep your current earnings (which can be positive, zero, or negative). If you draw all cards, your net earnings will always be $0 (since there are equal reds and blacks).

Find the optimal stopping strategy and the expected earnings under that strategy.

Background & Constraints

  • The deck has R red cards and B black cards, where R = B.
  • Cards are drawn without replacement.
  • At each step, you know how many red and black cards remain (you can see the card you draw).
  • Your decision to stop is based on your current state: (reds remaining, blacks remaining, current balance).
  • The key insight is that the state can be captured by just (reds remaining, blacks remaining) since the balance is determined by how many of each have been drawn.

Examples

Warm-up: 1 red, 1 black

Start: balance = 0, deck = [R, B] (shuffled)

50% chance first card is red: balance = +1. Should you stop?
  - If you stop: +$1
  - If you continue: next card is black, balance = $0.
  - Better to stop: +$1

50% chance first card is black: balance = -1.
  - If you stop: -$1
  - If you continue: next card is red, balance = $0.
  - Better to continue: $0

Expected earnings: 0.5 * $1 + 0.5 * $0 = $0.50

Small case: 2 red, 2 black

The optimal strategy yields an expected earning of $0.67 (approximately).
The exact computation requires evaluating the DP tree for all (reds, blacks) states.

Hints & Common Pitfalls

  • DP with memoization. Define f(r, b) as the expected earnings with optimal play when r red and b black cards remain. At each state, you draw a card (which is red with probability r/(r+b) and black with probability b/(r+b)), and then decide whether to stop.
  • Recurrence: 
    draw_value(r, b) = (r/(r+b)) * f(r-1, b) + (b/(r+b)) * f(r, b-1)
f(r, b) = max(current_balance, draw_value(r, b))
    But note: current_balance = (R_initial - r) - (B_initial - b) where R_initial and B_initial are the starting counts.
  • Base case: f(0, 0) = current_balance (no cards left, you must stop). Also, f(0, b) = max(current_balance, current_balance - b) = current_balance (stop immediately, since only black cards remain).
  • Common mistake: Thinking you should always stop when you're ahead. Sometimes it's worth continuing even with a positive balance if the remaining deck is red-heavy.
  • Common mistake: Forgetting that the balance is implicit in the (r, b) state — you don't need a third dimension.
  • For 100 red and 100 black: the expected value is approximately $5.19.

Follow-Up Questions

  1. With 1 red and 1 black card, what is the expected earning? (Answer: $0.50.)
  2. With 100 red and 100 black cards, what is the expected earning?
  3. What is the time and space complexity of the DP solution?
  4. Can you describe the optimal strategy in simple terms? (Hint: it relates to the proportion of reds remaining.)
  5. How does the expected earning grow as a function of n (where the deck has n red and n black cards)?