A shuffled deck of 26 red and 26 black cards is dealt face up one card at a time. Before any deal you may say stop, winning $1 if the next card is red and losing $1 if it is black. If you never stop, the last card counts. What is the value of the best stopping rule?

A shuffled deck of 26 red and 26 black cards is dealt face up one card at a time. Before any deal you may say stop, winning $1 if the next card is red and losing $1 if it is black. If you never stop, the last card counts. What is the value of the best stopping rule?

Approach: Write the payoff from stopping now in terms of the reds and blacks remaining, then check whether that quantity changes in expectation after one more card is turned.

0. With R reds and B blacks left, stopping now pays X = (R - B)/(R + B). Turning one card gives a red with probability R/(R+B), leaving (R-1-B)/(R+B-1), and a black with probability B/(R+B), leaving (R-B+1)/(R+B-1). Averaging those two returns X exactly, so X is a martingale. The optional stopping theorem then says every stopping rule has expected value equal to the starting value (26 - 26)/52 = 0. The tempting answer is a positive number from waiting until reds outnumber blacks in the remaining deck. It fails because the shuffles where that surplus never appears cost exactly what the favourable ones pay.

Follow-up: Change the deck to 26 red and 25 black. What is the value of the best stopping rule now?

Key concepts: martingale, optional stopping theorem, stopping rule.