# Expected number of coins

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.

• Hint : The expected amount doesn't depend on the chosen strategy Feb 25 '20 at 16:23
• @Tassle: I'll be your Bob if you'll be my Alice. Feb 25 '20 at 17:29
• I'd rather not, as I had a brainfart and was actually thinking of a game where you win if you stop at some point and the next card is white, loose if the next card is green. Feb 25 '20 at 17:46
• @asde Can you provide a source for the problem? What have you tried so far? Feb 25 '20 at 19:09

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.