Card game / options pricing / Brownian bridge question 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.
 A: 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$.
A: Perhaps the delightful paper, How to lose as little as possible,
by Vittorio Addona, Stan Wagon, and Herbert Wilf, is related to your question?  If not, you
lose little by scanning it.  From their Abstract:

Suppose Alice has a coin with heads probability $q$ and Bob has one with heads probability $p>q$.
Now each of them will toss their coin $n$ times, and Alice will win iff she gets more heads than Bob does. Evidently the game favors Bob, but for the given $p,q$, what is the choice of $n$ that maximizes Alice's chances of winning?

They determine the optimal strategy, and it is essentially unique, non-obvious, and requires intricate
calculation to pinpoint.  I think(?) your case is $p=q$, whereas they assume throughout that $p>q$.
Perhaps you can extract something useful from their results by letting $q \rightarrow p$?
Their recurrence relations are analogous to those you detailed.
See also this MO question: Recurrence relations whose base case is at $\infty$,
in which I raised the question of this whole class of recurrence relations.  Although for you,
$\infty = 52$.
A: This specific game seems very familiar, and I'm sure I have seen it discussed before along with a discussion of the optimal strategy, although I can't remember where. It might have been the Project Euler forums, perhaps in one of the forums restricted to those who have solved a particular problem. Using Google to search for the exact answer for $52$ cards might find it if it is in an open forum.
I believe the simulations said you should stop when there are about $k$ cards left in the deck and you are ahead by $c\sqrt k$, where $c$ did not seem to depend on $n$.
In an interesting variant, you can choose the fraction of your bankroll that you wager on whether each card is red or black. You do not need to bet only on red. It turns out that as long as you bet on the right side, and you bet your whole bankroll when you have a lock, your expected bankroll is multiplied by $\prod_{k=1}^n \frac {2k}{2k-1}$. Betting according to the Kelly criterion gives you that result with $0$ variance.
