We play a game. I shuffle a deck of cards and start dealing them face up. After any card you can say "stop", at which point I pay you 1 dollar for every red card dealt and you pay me 1 for every black card dealt. What is your optimal strategy, and how much would you play to pay this game?
Clearly the game is worth at least 0, since you can follow the strategy 'wait until all the cards are dealt' and get paid 0.
We can conclude that at any stage of the game, we will ask for another card if the expected value of continuing to play is greater than the amount of money already won; otherwise we will say stop. Mathematically, if $r$ is the number of red cards remaining and $b$ is the number of black cards remaining, and $f_{r,b}$ is the expected value of the game at this point, then the expected value of taking another card is
$e_{r,b} = \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}$
and hence the value of the game at this point, assuming we play the optimal strategy, is
$f_{r,b} = \max ( \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}, b-r )$
with $f_{r,0} = 0$ (if there are only red cards remaining, we have a guaranteed payout of 0) and $f_{0,b} = b$ (if there are only black cards remaining we won't take any more cards).
Solving numerically gives an expected value for this game of 2.624 with 52 cards. I'm interested in what the value is for a deck of $2n$ cards, and if the optimal strategy can be expressed analytically as a function of $r$ and $b$ (ie keep taking cards until you have made $g(r,b)$ dollars, then stop).
I've tried changing coordinates to $u=b-r$, $v=b+r$, and I've tried approximating the difference equation as a PDE, but no luck with an analytical solution yet – or even any decent approximations.
Best Answer
I think the article Optimal stopping of a Brownian bridge by Ekström and Wanntorp (preprint) would give you the answer for the limiting case as $n\to\infty$.