1
$\begingroup$

The game is as follows (an interview question found online where you can only calculate by hand):

You have a shuffled deck of 26 red and 26 black cards. You continuously draw a random card from the deck and decide whether to draw again (without replacement) or to stop. If you decide to stop, you draw another random card from the deck and check whether both cards are of the same color, if yes you win, otherwise you lose. If there's only one card left in the deck when you are making decisions, you have to choose stop. What is the optimal strategy?

I can only find dynamic programming methods for this question which needs to write a program to help calculate. My code is here. And the output file of my code is here. As you can see from the output file (if my code is right), the strategy is keep drawing until the number of either one color that have been drawn reaches 25, and then you draw once again and then choose to stop. However, how can you get this strategy if you only calculate by hand?

$\endgroup$
  • $\begingroup$ Do you know the color of the drawn card before any decision or after you stopped? $\endgroup$ – Mostafa Ayaz Jan 22 '18 at 13:02
  • $\begingroup$ @MostafaAyaz Before. When you draw a card, you know its color immediately. $\endgroup$ – Daniel Jan 22 '18 at 13:04
1
$\begingroup$

Reasoning you could've had:

Whatever card you draw first, you have $\frac{25}{51}$ chance of drawing a second card of same color if you stop now. That's less than $\frac{1}{2}$ chance of winning at that moment.

If you keep drawing, your odds of winning can either converge to $1$ (eliminating a color) or to $1/2$ (ending up with one black one red card case). Either case is better.

If you are in a state with less than $1/2$ chances of winning, you would definitely want to draw to adopt the chances above (either reach $1$ or $1/2$ case).

But if your odds are more than $1/2$ at any particular state, this also means from this point on it is more likely that you will eliminate a color, and you still would want to draw as you are more likely to end up in the case $1$ at that moment.


Exact chances:

In conclusion, If you draw till $2$ cards are left or one color is left, and then stop, you'll maximize your odds of winning, as you observed.

There's $\frac{25}{51}$ chance of drawing all cards of same color this way (you win in this case), and $\frac{26}{51}$ chance of ending up with one black card and one red card in the deck, having $\frac{1}{2}$ chance of winning by stopping in this case and matching the drawn card to the last revealed one.

That gives you $\frac{38}{51}\approx74.5098\%$ chance of winning playing this strategy.


In general, given $c$ red and $c$ black cards in a deck, you have $\frac{3c-2}{4c-2}$ chances of winning by playing this strategy, as there's $\frac{c-1}{2c-1}$ chance of drawing an entire color before reaching two cards who are of different color.

$\endgroup$
  • $\begingroup$ You said "But if your odds are more than 1/2 at any particular state, this also means from this point on it is more likely that you will eliminate a color, and you still would want to draw as you are more likely to end up in the case 11 at that moment", but "more likely" is not enough for you to choose to draw again. For example, if you already have 85% chance to win, it's hard to say whether draw to the end is to your advantage or not because although you have less probability of reaching 2 different color in the end, this less probability may possibly reduce your overall win rate. $\endgroup$ – Daniel Feb 1 '18 at 7:42

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.