Red pays, black costs
A standard deck ( red, black) is shuffled and turned over one card at a time. Each red card pays you 1 dollar and each black card costs you 1 dollar. You may stop at any moment (including before the first card) and keep your running total.
With the best strategy, what is the expected value of the game? Give a decimal answer.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
The state of the game is the pair (red cards left, black cards left). Let be the value of the game from that state, counting only future gains.
Compare stopping (worth more) with drawing one card: where and , with and .
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. The only thing that matters at any moment is how many red and black cards remain. That gives a small dynamic program: at each state, compare stopping now with drawing one more card.
Step 1: why stopping can help. If you never stop, you end at . But the running total moves like a random walk constrained to end at , and it often goes positive along the way. The option to stop at a good moment is worth something, so the value is positive.
Step 2: the recursion. From state , stopping is worth more. Drawing gives and moves to with probability , or and moves to with probability . So where , the value of drawing, is Boundaries: with only red cards left take them all, ; with only black cards left stop, .
Step 3: compute. Filling the table from small decks up to , by hand for small cases or with a few lines of code, gives (The exact value is a fraction with a -digit denominator.)
Small case to check by hand. With one red and one black card: . Draw; if the first card is red, stop with 1 dollar; if black, draw the red one and end at .
What the optimal rule looks like. Since , you never stop while more red than black cards remain: the next card is in your favour and stopping later is always possible. You stop only once your gain is large enough compared with how black-heavy the remaining deck is, and the table tells you exactly where that line is.