Expected number of coins

Question

Alice and bob play a game. Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob.

• Every time Bob flips a white card he gets one coin, otherwise he loses one coin. At any moment (even at the beginning), Bob is allowed to stop playing the game and keep the number of coins that he has.
• During the game-play the balance of coins that Bob has may be negative.

If Bob plays optimally, what the expected amount of coins Bob will have?

Can any body give me an idea or a hint how to solve it.

Answer 1

Let $w(a,b)$ be the expected profit with $a$ positive cards and $b$ negative cards. Then $w(0,0) = 0$ and $$ w(a,b) = \max\bigl(0, \tfrac{a}{a+b} (w(a-1,b) + 1) + \tfrac{b}{a+b} (w(a,b-1) - 1)\bigr). $$ Indeed, if we stop the game immediately, the profit is zero. Otherwise, with probability $\tfrac{a}{a+b}$, we pull out a positive card, and with probability $\tfrac{b}{a+b}$, we pull out a negative card.

Using this recurrence, it is easy to compute $w(4999,4999)$. On my laptop it took less than a second.