You are given a pile of 10 shuffled cards, 5 with P and 5 with N. You draw one at a time; if you get a "P" you win a dollar, and if you get an "N" you lose a dollar. You can choose to stop drawing at any point. What's the optimal strategy and expected value of the game?
I have the brute force solution of $$E_{5,5} = \max\{1/2(1+E_{4,5}) + 1/2(-1+E_{5,4}),0\}$$ and continuing recursively. Is there a clever way to generalize the final answer or strategy for $n$ cards?
The expected value has to be at least $\frac 12$ because that is the value of the following strategy. Draw the first card, if P quit (winning $1$), if N draw all the others (breaking even). You can do better. If you have drawn an equal number of cards of each type you are at $0$ and the same logic applies, so you should draw. If you are ahead the expected value of the next draw is negative, so you should quit. The correct strategy is to draw any time you are even or behind and to quit if you ever hit $+1$ or run out of cards.
The number of sequences that get you $0$ are counted by the Catalan number $C_{10}=\frac 16{10 \choose 5}=42$ The number of sequences is ${10\choose 5}=252$, so the chance you get $0$ is $\frac 16$ and the value of the game is $\frac 56$
Some preliminaries.
Let $E(p,n)$ denotes the expected value of the optimal game when in the deck are $p$ cards “P” and $n$ cards “N” left. Then $E(p,0)=p$ and $E(0,n)=0$
Further we shall assume that the deck is so well shuffled such that all sequences of cards have equal probability. Then for each $p,n\ge 1$
$$E(p,n)=\max\left\{\frac{pE(p-1,n)+nE(p,n-1)+p-n}{p+n},0\right\}.$$
Put $e(p,n)=E(p,n)(p+1)\cdots (p+n)$. Then $e(p,0)=p$, $e(0,n)=0$, and
$$e(p,n)=\max\left\{(e(p-1,n)+ne(p,n-1)+(p-n) (p+1)\cdots (p+n-1),0\right\}.$$
Consequently calculating by rows we obtain
$e(p,1)= p^2$,
$e(p,2)= p^3+p^2-2p$,
$e(p,3)= p^4+3p^3-4p^2+12p+12$, provided $p\ge 1$,
... .
