Expected Value of an Optimal Stopping Card Game

Expectation · Hard · Free problem

You have a deck of $n$ cards. Each card's value is drawn independently and uniformly from the set $\{-1, +1, +2\}$. You turn the cards over one at a time. After seeing a card you may keep it (adding its value to your running gain and then deciding again on the next card) or stop and walk away with nothing more from this point. Because you can always walk away, a run of bad cards never drags your gain below $0$: this is a keep-or-discard game whose value is floored at $0$. You play to maximize expected payoff. Write $V_n$ for the value of the game with $n$ cards remaining, measured as the expected gain from this point starting from $0$.

  1. Solve the problem for a deck of $n = 1$ card.
  2. Solve the problem for a deck of $n = 2$ cards.
  3. Generalize: write a recursive formula relating $V_n$ to $V_{n-1}$, the value with one fewer card remaining.

Hints

  1. Treat each card as a decision: keep it and play on, or discard and walk away with nothing more from here. Since you can always walk away, the gain from any point on is worth at least $0$. Work backwards from the last card.
  2. Let $V_n$ be the value with $n$ cards left, measured from a fresh $0$. After a draw $x$ you take $\max(x + V_{n-1},\, 0)$ -- continue or stop -- then average over the three card values.
  3. Start from $V_0 = 0$, so $V_1 = \frac{1}{3}\sum_x \max(x, 0) = 1$. Then $V_2 = \frac{1}{3}\sum_x \max(x + 1, 0) = 5/3$, and in general $V_n = \frac{1}{3}\sum_{x \in \{-1,1,2\}} \max(x + V_{n-1}, 0)$.

Worked Solution

How to Think About It: This is an optimal-stopping problem dressed up as a card game. After each card you face one decision: keep it and carry on, or stop and take nothing more from this point. Because stopping is always available, the gain from any point forward is worth at least $0$ -- you never have to absorb a bad run. The right object is the value of "$n$ cards left, measured from a fresh $0

Loading problems...
quot;. You keep a card only when its value plus the value of the remaining game beats walking away, so the stop-or-continue choice is made after you see the card, card by card.

Quick Estimate: A single card averages $E[X] = (-1 + 1 + 2)/3 = 2/3$. If you were forced to keep every card, $n$ cards would be worth $n \cdot 2/3$ (so /3$, $4/3$, $ for $n = 1, 2, 3$). But the floor-at-0 rule lets you throw away the worst draws, which can only help, so each $V_n$ should sit somewhat ABOVE $n \cdot 2/3$ -- most so for small $n$, where the chance to dodge a $-1$ matters most. Expect $V_1 \approx 1$ and $V_2$ a bit below $. Let us pin the exact values.

Approach: Use backward induction. Let $V_n$ be the value of the game with $n$ cards remaining, measured as the expected gain from this point starting from $0$. After a draw $x$ you take the better of continuing (worth $x + V_{n-1}$) and stopping (worth $0$), then average over the three equally likely cards.

Formal Solution:

Step 1 -- The recursion. With $n$ cards left, draw $X \in \{-1, +1, +2\}$, each with probability

/3$. Having seen $x$, keeping it leaves you at $x$ plus a fresh game of $n - 1$ cards, worth $x + V_{n-1}$; discarding (stopping) is worth $0$. You take whichever is larger, so

$V_n = \frac{1}{3}\sum_{x \in \{-1, 1, 2\}} \max\!\left(x + V_{n-1},\; 0\right),\qquad V_0 = 0.$

The $\max(\cdot, 0)$ is exactly the floor-at-0 rule: a bad continuation is thrown away and replaced by the value $0$ of walking off.

Step 2 -- One card ($n = 1$). Here $V_0 = 0$, so you simply keep the card when it is positive and discard it otherwise:

$V_1 = \frac{1}{3}\Big(\max(-1, 0) + \max(1, 0) + \max(2, 0)\Big) = \frac{1}{3}(0 + 1 + 2) = 1.$

You discard the $-1$ (stop at $0$) and keep the $+1$ and $+2$.

Step 3 -- Two cards ($n = 2$). One card remains after the first draw, worth $V_1 = 1$. Compare each draw plus that continuation against stopping:

$V_2 = \frac{1}{3}\Big(\max(-1 + 1,\,0) + \max(1 + 1,\,0) + \max(2 + 1,\,0)\Big) = \frac{1}{3}(0 + 2 + 3) = \frac{5}{3}.$

Drawing a $-1$ gives $-1 + 1 = 0$, which exactly ties with stopping: you are indifferent and the term contributes $0$ either way.

Step 4 -- Three cards ($n = 3$), as a check. Now $V_2 = 5/3$:

$V_3 = \frac{1}{3}\Big(\max(-1 + \tfrac{5}{3},\,0) + \max(1 + \tfrac{5}{3},\,0) + \max(2 + \tfrac{5}{3},\,0)\Big) = \frac{1}{3}\Big(\tfrac{2}{3} + \tfrac{8}{3} + \tfrac{11}{3}\Big) = \frac{1}{3}\cdot\frac{21}{3} = \frac{7}{3}.$

So $V_3 = 7/3 \approx 2.33$, comfortably above the forced-keep baseline of

$, matching the estimate.

Answer: With the gain floored at $0$ (keep-or-discard), the value obeys

$V_n = \frac{1}{3}\sum_{x \in \{-1, 1, 2\}} \max\!\left(x + V_{n-1},\; 0\right),\qquad V_0 = 0,$

giving $V_1 = 1$, $V_2 = \dfrac{5}{3}$, and $V_3 = \dfrac{7}{3}$. The optimal policy keeps a card exactly when its value plus the remaining-game value is nonnegative, which backward induction evaluates card by card.

Intuition

This is a miniature optimal-stopping problem, the structure behind every position with embedded optionality: exercise now (take the payoff) or wait for something better. Backward induction -- start at the end, compute the continuation value, and roll backwards -- is the universal tool. The interview signal is recognizing that the option to stop (the floor at $0$) gives the game positive value even though some draws are negative, and that the continuation value $V_{n-1}$ acts as a dynamic keep-or-discard threshold on the current draw.

The deeper lesson is option value. Even though a card averages /3$, the game is worth MORE than $n \cdot 2/3$ for small $n$ because discarding the worst draws removes downside at no cost -- the same reason an American option dominates its European twin, since early exercise (here, stopping) is an extra source of value. As $n$ grows, the positive drift dominates and $V_n$ approaches $n \cdot 2/3$ from above.

Open the full interactive solver →