4

Suppose I have four cards: two black, two red. I draw them one by one. Every time I draw a red card, I win a dollar, and every time I draw a black card, I lose a dollar. I can choose to stop at any time I want. What is the optimal strategy for choosing when to stop, and what is its expected value?

I did this by brute force to get $2/3$, but I don't know if there is a more clever way out there.

user43123
  • 105

2 Answers2

4

Let $E(r,b)$ be the expected value of the optimal strategy with $r$ red and $b$ black cards. We have $$ E(r,b) = \max\left(0,\frac{r}{r+b}(1+E(r-1,b))+\frac{b}{r+b}(-1+E(r,b-1))\right). $$ Implementing this on a computer, I got $E(2,2) = 2/3$.

You can experiment with other values using this sage code. Perhaps you'll figure out a formula.

def E(r,b):
    if r==0: return 0
    if b==0: return r
    return max([0,r/(r+b)*(1+E(r-1,b))+b/(r+b)*(-1+E(r,b-1))])
Yuval Filmus
  • 57,157
3

You lose if you draw more black cards then red cards. The two strategies to avoid this are:

  • (1) Stop immediately when you have drawn at least more reds than blacks and
  • (2) Stop only when you have drawn two reds cards.

The expected return on (1) is $4/6$ and the expected return on (2) is $4/6$, but the first strategy has the least variance (or risk).

$$\begin{array}{|c|c|c|c|c|}\hline 1 & BBRR| & BRBR| & BRR|B & R|BBR & R|BRB & R|RBB \\ & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline 2 & BBRR| & BRBR| & BRR|B & RBBR| & RBR|B & RR|BB \\ & 0 & 0 & 1 & 0 & 1 & 2 \\ \hline \end{array}$$

Graham Kemp
  • 129,094
  • how did you compute the variance for the two strategies? – ghjk Sep 05 '18 at 03:54
  • 1
    @user177196 The usual way: $\mathsf {Var}(X)=\sum_{r=0}^2 r^2\mathsf P(R=r)-(\sum_{r=0}^2 r\mathsf P(R=r))^2$. So the variance for the first strategy is $2/36$ and for the second is $20/36$. – Graham Kemp Sep 05 '18 at 04:25
  • I am so dumb. Thank you so much, Sir!! – ghjk Sep 06 '18 at 05:57