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.

  • $\begingroup$ Hint : The expected amount doesn't depend on the chosen strategy $\endgroup$ – Tassle Feb 25 at 16:23
  • $\begingroup$ @Tassle: I'll be your Bob if you'll be my Alice. $\endgroup$ – greybeard Feb 25 at 17:29
  • $\begingroup$ 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. $\endgroup$ – Tassle Feb 25 at 17:46
  • $\begingroup$ @asde Can you provide a source for the problem? What have you tried so far? $\endgroup$ – Throckmorton Feb 25 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.

| cite | improve this answer | |
  • $\begingroup$ Yuval Filmus thank you .I had this doubt for weeks $\endgroup$ – asde Feb 25 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.