Expected Payoff of the Red-Black Card Game
A deck has 50 red cards and 50 black cards (100 total). You draw one card at a time without replacement. After each draw, you can choose to stop or continue. If you stop after drawing $k$ cards, your payoff is:
$$\text{Payoff} = \frac{\text{number of red cards drawn}}{k} \times \$2$$
If you never stop, you draw all 100 cards. What is the expected payoff of this game under optimal play?
Hints
- Consider the simplest non-trivial strategy: stop at $k = 1$ if the first card is red (payoff $\$2$), otherwise draw all 100 (payoff $\$1$). What does this give you?
- The ratio $R_k/k$ is NOT a martingale for sampling without replacement. Try checking: does $E[R_{k+1}/(k+1) \mid R_k] = R_k/k$? You will find it does not hold in general.
- Set up the Bellman equation $V(r,b) = \max(2(50-r)/(100-r-b),\; \text{continuation})$ and solve by backward induction from $V(0,0) = 1$.
Worked Solution
How to Think About It: You have 50 red and 50 black cards. You draw one at a time and can stop whenever you want -- your payoff is (fraction of reds drawn) times $\$2$. The tempting argument is: "the fraction of reds is always $1/2$ in expectation, so you can't beat $\$1$." That argument is wrong. It confuses $E[R_k/k]$ for a fixed draw count (which is indeed $1/2$) with $E[R_\tau/\tau]$ for an adaptive stopping time $\tau$. Since $R_k/k$ is not a martingale, you CAN beat $\$1$ by stopping at favorable moments.
Quick Estimate: Try the simplest smart strategy. Draw one card. If it is red, stop -- your fraction is $1/1 = 1$, payoff $= \$2$. If it is black, you are stuck with fraction $0/1$, so just draw all remaining 99 cards and end at $50/100$, payoff $= \$1$. Each case happens with probability $1/2$, so this gives:
$$E[\text{payoff}] = \frac{1}{2}(\$2) + \frac{1}{2}(\$1) = \$1.50$$
Already beats $\$1$. Can we do better? Yes -- if the first card is black, don't give up. Draw a second card. If it is red, your fraction is $1/2$ (payoff $\$1$) -- no gain, so keep going. If both of the first two are red, fraction $= 2/2 = 1$, payoff $= \$2$. The option to continue after a bad start and wait for a high-fraction moment pushes the value above $\$1.50$.
Approach: Backward induction over the state space $(r, b)$ = (reds remaining, blacks remaining). At each state, compare the payoff from stopping to the expected value of drawing one more card.
Formal Solution:
Let $V(r, b)$ be the game value when $r$ reds and $b$ blacks remain in the deck. Cards drawn so far: $k = 100 - r - b$. Reds drawn: $j = 50 - r$.
If you stop, you collect $2j/k$. If you draw, the next card is red with probability $r/(r+b)$:
$$V(r,b) = \max\!\left(\frac{2(50 - r)}{100 - r - b},\;\frac{r}{r+b}\,V(r-1,b) + \frac{b}{r+b}\,V(r,b-1)\right)$$
Boundary: $V(0,0) = 2 \cdot 50/100 = 1$ (drew everything). At the start ($k = 0$, no cards drawn), the payoff $0/0$ is undefined so we must draw:
$$V(50,50) = \tfrac{1}{2}\,V(49,50) + \tfrac{1}{2}\,V(50,49)$$
Running this DP over the $51 \times 51 = 2{,}601$ states gives:
$$V(50,50) \approx \$1.5849$$
The optimal policy is a state-dependent threshold: stop when the red fraction $j/k$ exceeds a cutoff $\theta(k)$ that depends on how many cards have been drawn. Early on ($k = 1, 2$), you need fraction $= 1$ (all reds) to stop. As $k$ grows, the threshold drops toward roughly $0.6$ because there is less optionality left with fewer remaining cards.
Answer: The expected payoff under optimal play is approximately $\$1.5849$. The naive claim of $\$1$ is wrong -- $R_k/k$ is not a martingale, so the optional stopping theorem does not apply. Even the dead-simple "stop if the first card is red" strategy already yields $\$1.50$.
Intuition
This problem is a beautiful trap. The natural instinct is to invoke a martingale argument: "the expected fraction of reds is always $1/2$, so you can't beat $\$1$." But $R_k/k$ is NOT a martingale for sampling without replacement. The expected value of a ratio is not the ratio of expected values (Jensen's inequality). The simple strategy of stopping immediately when the first card is red already gives $\$1.50$, proving the martingale claim wrong.
The deeper lesson is about optionality. When your payoff is a nonlinear function of random variables (here, a ratio), the ability to choose when to stop is genuinely valuable. In trading, this shows up whenever you have the right but not the obligation to act -- options, take-profit orders, timing of trade execution. The game's value of roughly $\$1.58$ exceeds the "average" outcome because you get to cherry-pick favorable moments.