2

We draw from a standard 52 card deck, drawing a red means we get 1 dollar, drawing a black means we are fined 1 dollar. What is the expected payoff / optimal stopping point?

So far I'm trying to reason out the expected pay off of a smaller deck. For a deck of size 4, the expected payoff should be $2/3

RRBB: +2 RBBR: +0 RBRB: +1 BRBR: +0 BRRB: +1 BBRR: +0

I'm trying to work out the expected pay off of a 6 card deck where there are 20 cases, I seem to keep getting 15/20 dollar expected payoff but according to my textbook the right answer should be 17/20. Could anyone help me out with this part, and then expanded to the case of a 52 card deck?

BlankQQ
  • 61
  • I don't believe there is a closed, analytic formula for this but numerical analysis shouldn't be too bad. Just do backwards induction keeping track of the value of stopping. – lulu Jan 09 '19 at 18:08
  • For the 6 card deck, if the first two cards are red, continuing has expected payoff (R:+1, BR:+0, BBR:-1, BBBR:-2) = -2/4. Stopping after 2 cards if they are both red yields the textbook answer of 17/20. – Daniel Mathias Jan 09 '19 at 19:24
  • For your four card game you have to define the stopping rule. The only one that matters is whether you stop after red on the first card. Your table seems to say no, but it breaks even to stop after the first red card. You lose the $+1$ for $RBRB$ but gain $1$ for $RBBR$. – Ross Millikan Jan 09 '19 at 20:49

2 Answers2

1

I made a spreadsheet for the payoff from a deck of $R$ red cards and $B$ black cards. The basic formula is $$f(R,B)=\max \left(0,\frac {R(f(R-1,B)+1)+B(f(R,B-1)-1)}{R+B}\right)$$ because if you draw a red card, which happens with probability $\frac R{R+B}$, you are at state $(R-1,B)$ with $1$ in hand. I reproduced the $f(2,2)=\frac 23$ and $f(3,3)=0.85$ as checks. The $\max$ function is because you can stop and take $0$. I find $f(26,26)\approx 3.37276$ and if you start by drawing only red cards you should draw six of them before you stop.

Below is the left side of the sheet. The number of red cards is down the left, the number of black cards across the top. The entries are the expected value of starting with a deck like that. A $0$ entry means you should not draw.

enter image description here

Ross Millikan
  • 374,822
  • I double-checked your results. Program output agrees with everything in your spreadsheet image, but reports $f(26,26)\approx2.624476$ – Daniel Mathias Jan 10 '19 at 02:08
0

At each point in the game, you have the option to stop (and leave with what you have won), or continue and risk winning more or less. Since you don't know anything about the order of the cards in the deck, your decision depends only on two things: $k$, the number of cards remaining in the deck ($k \ge 1$ for a meaningfull choice) and the number of $r$ of red cards among them ($0 \le r \le k$), wich you of course can determine from what has come before.

This number totally determines your current winnings (if you started with $2n$ cards, $n$ black and $n$ red, it is $(n-r) - (n-(k-r))=k-2r$). So your overall win is your current winnings + what you win/loose in the remaining cards. So again, what you decide to do in each step is the what is better, stopping now or risking more cards.

If we denote by $b(k,r)$ the expected remaining winnings under the best strategy, we get a resursive formula (as lulu implies in the comments).

We start with $$b(1,0)=0, \quad b(1,1)=1$$

because if the one remaining cards is not red, you of course stop, and if it is red, you continue and get $1.

For any $k+1$ cards remaining, we have to decide if stopping (expteced win: $0$) is better than continuing.

If we continue one step, we get a red card with probability $\frac{r}{k+1}$, in that case our remaining winnings are $1+b(k,r-1)$, where the $1$ comes from the win in this move and the $b(k,r-1)$ as the best from the the remaining situation of $k$ cards with $r-1$ reds in them.

OTOH, the probability of getting a black card is $\frac{k+1-r}{k+1}$, and our remaining winnings are $-1+b(k,r)$.

Overall, we get that the expected remaining winnings when we continue is

$$b^*(k+1,r) = \frac{r}{k+1}(1+b(k,r-1)) + \frac{k+1-r}{k+1}(-1+b(k,r)) =$$ $$ \frac{2r-(k+1)}{k+1} + \frac{r}{k+1}b(k,r-1) + \frac{k+1-r}{k+1}b(k,r)$$

Of course, when this is negative, we don't continue but stop, so we finally get

$$b(k+1,r)=\max(b^*(k+1,r),0)$$

Note that the recursion doesn't really work for $r=0$ (because $b(k,r-1)$ does not exist), but in this case the initial probability factor in front of it is 0, so it doesn't matter.

So what you need to do, is to recursively calculate $b(k,r)$ first for $k=2$ and all relevant $r$, then $k=3$, etc. This is doable by hand for the first $k$, then you probably better write some computer code (Excel might be enough).

It's not clear if there is an easy formula to find for each $k$ what the lowest $r$ will be to continue, but the recursion works and has qudratic time complexity, so should pose no problem for a computer and finding $b(52,26)$.

Ingix
  • 14,494