# 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? Commented Dec 7, 2019 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 Commented Dec 8, 2019 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
Commented Dec 8, 2019 at 20:49

I did this in excel with the boundary conditions:

$$f(0,r)=0 \quad f(b,0)=b$$

And

$$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$$

The game assumes that the player always plays optimally. In this regard, if you are at a point of $$f(0,r)$$ your payoff would end up at 0 since you are currently at some negative payoff and you will ask the dealer to deal all the remaining red cards to get you to 0.

The key here is to see that you will always do what is optimal for you which is what $$f(b,r)$$ represents. In the same vein, the other boundary condition is:

$$f(b,0) = b$$

Why? Because if I come to a point where I only have black cards remaining to be dealt, I will ask the dealer to stop dealing and my payoff is whatever I am at right now.