Optimal Stopping Strategy

Question

Imagine you are playing a card game. You start with a well-shuffled deck of 52 cards, containing 26 red cards and 26 black cards, stacked face down. You have a sequence of turns, 52 possible turns in total, each turn you either pull the top card and turn it over, or you quit. If you pull a red card you win €1, and if you pull a black card you lose €1. If you play all 52 turns without stopping, you are guaranteed to break even. What is the optimal stopping strategy?

Accepted Answer

Let 𝑣(𝑟,𝑏) be the expected value of the game for the player, assuming optimal play, if the remaining deck has 𝑟 red cards and 𝑏 black cards.

Then 𝑣(𝑟,𝑏) satisfies the recursion:

\begin{equation} v(r, b) = \begin{cases}
0 & 	ext{ if } r = 0 \
r & 	ext{ if } b=0 \; and\; r>0\
max(0, f(r, b))) & 	ext{ if } both\; (r,b)>0
\end{cases}  \end{equation}

where

\begin{equation} f(r,b) = (\frac{r}{r+b})(1+ v(r-1, b)) + (\frac{b}{r+b})(-1+ v(r, b-1)) \end{equation}

For this formula f(r,b), If 𝑟,𝑏>0, and the player elects to play a card, then:

 	The revealed card is red with probability $\frac{r}{r+b}$ and in that case, the player gets a score of +1, and the new value is v(r-1, b).
 	The revealed card is black with probability $\frac{b}{r+b}$ and in that case, the player gets a score of −1, and the new value is v(r, b-1).

The stopping rule is simple: Stop when v(r.b) = 0.

Implementing the recursion in Maple, the value of the game is
\begin{equation} v(26,26)= \frac{41984711742427}{15997372030584} \approx 2.62 \end{equation}
and the optimal stopping strategy is as follows:

 	If $24 \leq\ b \leq\ 26$, play while $r \geq b -5$
 	If $17 \leq\ b \leq\ 23$, play while $r \geq b -4$
 	If $11 \leq\ b \leq\ 16$, play while $r \geq b-3$
 	If $6 \leq\ b \leq\ 10$, play while $r \geq b-2$
 	If $3 \leq\ b \leq\ 5$, play while $r \geq b-1$
 	If $1 \leq\ b \leq\ 2$, play while $r \geq b$
 	If $b = 0$, play while $r > 0$

Title	Category	Subcategory	Difficulty	Status
Drawing a Blue 3	Programming	Mathematical Problems	Medium	Unlock
Empty Number of Boxes	Programming	Mathematical Problems	Medium	Unlock
Pricing Accuracy	Programming	Mathematical Problems	Medium	Unlock
Prime Number Generator	Programming	Mathematical Problems	Medium	Unlock
Roulette Table	Programming	Mathematical Problems	Medium	Unlock
Top 2000 Songs	Programming	Mathematical Problems	Medium	Unlock

The Interview Guide for Quants and Traders