# Dynamic Programming: Dynamic Card Game

I'm reading an interview book called A Practical Guide to Quantitative Finance Interview and I have some doubts about the solution provided by the book, so I really appreciate your advice if my doubt is correct or not.

Question description (from Chap 5 Stochastic Process and Stochastic Calculus/5.3 Dynamic Programming/Dynamic Card Game):

A casino offers a card game with the standard 52 cards (26 red, 26 black). The cards are thoroughly shuffled and the dealer draws cards one by one. (Drawn cards are not returned to the deck). You can ask the dealer to stop at any time you like. For each red card drawn, you win 1 dollar; for each black card drawn, you lose 1 dollar. What is the optimal stopping rule in terms of maximizing expected payoff and how much are you willing to pay for this game?

Solution: Let $$(b,r)$$ represent the number of back and red cards left in the deck, respectively. By symmetry, we have:

$$RedCardsDrawn-Black Cards Drawn = Black Cards Left - Red Cards Left$$

At each $$(b,r)$$, we face the decision whether to stop or keep on playing. If we ask the dealer to stop at $$(b,r)$$, the payoff is $$b-r$$. If we keep on playing, there is $$b/(b+r)$$ probability that the next card will be black-in which case the state change to $$(b-1,r)$$-and $$r/(b+r)$$ probability that the next card will be red-in which case the state changes to $$(b,r-1)$$. We stop if and only if the expected payoff of drawing more cards is less than $$b-r$$. That also gives us the system equation:

$$E[f(b,r)]= max(b-r,(b/(b+r))*E[f(b-1,r)]+(r/(b+r))*E[f(b,r-1)])$$

Using the boundary condition:

$$f(0,r)=0$$

My doubt: I think the above boundary condition should be $$f(0,r)=-r$$ instead because:$$RedCardsDrawn-Black Cards Drawn = Black Cards Left - Red Cards Left = 0-r$$ I'm wondering if my understanding is correct?

• May I know which question is it from the book? – Idonknow Dec 7 '19 at 15:53
• @Idonknow, sorry for didn't provide the info. It is from Chap 5 Stochastic Process and Stochastic Calculus/5.3 Dynamic Programming/Dynamic Card Game – M00000001 Dec 8 '19 at 17:15
• is f(0,r) not equal to zero because 26 black cards have already been drawn costing 26 dollars and (26-r) red cards have been drawn recovering that many dollars, and therefore by continuing to play the game and recovering r dollars for each new card turn you will end up at zero? – Attack68 Dec 8 '19 at 20:49

$$f(0,r)=0 \quad f(b,0)=b$$
$$f(x,y) = \max \left (x-y,\; \frac{x}{x+y}f(x-1,y) + \frac{y}{x+y}(x,y-1) \right)$$
The answer I got was $$f(26,26) = 2.498$$