Red Card Stopping Game: Puzzle and Step-by-Step Solution
Probability
Hard
Reported at Jane Street, SIG, Citadel, Hudson River Trading
The puzzle
A shuffled deck of 52 cards, 26 red and 26 black, is turned over one card at a time. At any point before the last card you may say 'stop'. You win if the next card turned over is red. If you never say stop, you are betting on the last card. Is there a strategy that wins more than half the time?
Short answer: No. Every stopping strategy wins with probability exactly 1/2.
Step 1: Why it feels like you can win
It looks as if you should wait until more black cards than red have been turned over and then stop, because the remaining deck is then rich in red. Sometimes that happens and the odds of the next card are better than 1/2.
But you are not guaranteed that moment will come. If you wait for it and it never arrives, you are forced to the end of the deck in exactly the situations where the remaining cards are poor in red. The good and bad cases balance perfectly.
Step 2: The martingale argument
Let R be the number of red cards left and N the number of cards left. If you stop now, your chance of winning is R / N. After the next card is turned, the new proportion is (R - 1) / (N - 1) with probability R / N and R / (N - 1) with probability (N - R) / N.
Its expected value is [R(R - 1) + (N - R)R] / [N(N - 1)] = R(N - 1) / [N(N - 1)] = R / N. So the proportion of red cards remaining is a martingale: on average it does not move. By the optional stopping theorem, whatever rule you use to stop, the expected proportion at your stopping time equals the starting value, 26 / 52 = 1/2. Your win probability is exactly that expected proportion.
Step 3: The one-line proof
There is a slicker argument. Whenever you say stop, you win if the next card is red. Change the rule so that you win if the last card of the deck is red instead. Given everything you have seen, the next card and the last card are equally likely to be any of the remaining cards, so the two rules have the same win probability at every moment.
But under the changed rule your strategy is irrelevant: the last card of a shuffled deck is red with probability 1/2. So every strategy wins with probability 1/2.
Step 4: Why trading firms ask it
It is a disguised statement that you cannot make money from a fair game by choosing when to bet. That is the same reason no stopping rule turns a martingale price into free profit, and interviewers want to see you recognise the structure rather than hunt for a clever trigger.
Why interviewers ask it
Offer the intuitive objection, then kill it with the last-card argument. Naming the martingale and optional stopping shows you can generalise the result.
Knowing the proof is half of it. Work Red Card Stopping Game interactively, then take it under a clock with the rest of the Outcry simulators.