2
$\begingroup$

You have a shuffled deck of 26 red and 26 black cards. You play a game by repeatedly looking at the top card and either discarding it or ending the game. At the end if the color of the next card matches that of the top card you win, otherwise you lose. What is the optimal strategy?

$\endgroup$
  • $\begingroup$ Sorry, not sure I get the rules. Say I draw a red card first and promptly end the game. In that case...what happens? We look at the next one and, if it is red I win and if it is black I lose? So...with this particular strategy, I win with probability $\frac {25}{51}$, yes? $\endgroup$ – lulu Feb 23 '18 at 22:42
  • $\begingroup$ I think Peter is definitely correct if the question is "if the color of the next card is RED (or black) you win", but in this case it's "if the color of the next card matches that of the TOP card". He might still be right, but I'm not convinced. $\endgroup$ – introspectivemathematics Feb 23 '18 at 22:47
  • $\begingroup$ @lulu, yes that is correct. The "top card" changes every time I decide to continue playing. Every time I look at the top card I can make a decision to keep playing or not. $\endgroup$ – introspectivemathematics Feb 23 '18 at 22:48
  • $\begingroup$ So...it's easy to prove that the optimal strategy has probability $≥\frac 12$. To see that, look at the strategy that ignores every draw and ends on the next to last. That one wins if the last two match and loses otherwise, a $\frac 12$ chance. I think this proves that the optimal probability is in fact $>\frac 12$ since I can improve on the strategy by checking the probability at each stage (and stopping if I ever get $>\frac 12$). $\endgroup$ – lulu Feb 23 '18 at 22:56
  • $\begingroup$ I tried one possible computer simulation strategy: $\endgroup$ – introspectivemathematics Feb 23 '18 at 23:00
3
$\begingroup$

Here is a proof that quasi's strategy is optimal for any situation.

I'm going to slightly modify that strategy to simplify the analysis. In the new strategy (which we'll call the Two-Card Strategy), you should keep playing no matter what until only two face-down cards are left. Based on the cards you've seen so far, you should be able to determine if they're the same color or different colors. Based on that:

  • If the two face-down cards are the same color, flip the next one of them over, and then stop, winning the game with probability $1$.
  • If the two face-down cards are opposite colors, stop: one of them will match the current top card and one won't, so you win with probability $\frac12$.

The only difference from quasi's strategy is that the Two-Card Strategy potentially stalls for a while if it gets into a situation where there are many cards left, all of one color. (In that case, we can win with probability $1$ before getting down to two face-down cards.) But this doesn't change the winning probability, since we win anyway in either case.

As a result, the two bottom cards of the deck are ultimately what determines the fate of this strategy.

Now consider any other strategy. If the other strategy also always waits until two face-down cards are left, it's easy to see that it can't beat the Two-Card Strategy. So suppose that the other strategy decides to stop at some point when more than two cards are left.

We'll consider each of those early stopping points one by one. If, when the other strategy decides to stop, the top card is red (without loss of generality) and there are $r$ red and $b$ black cards left, the other strategy wins with probability $\frac{r}{r+b}$. We may assume $b\ge 1$; if $b=0$, then the other strategy definitely wins in this case, but so does the Two-Card strategy, because then the bottom two cards are definitely red.

If we decided to keep going and use the Two-Card Strategy instead, then:

  • The bottom two cards are both red with probability $\frac{r(r-1)}{(r+b)(r+b-1)}$.
  • The bottom two cards are both black with probability $\frac{b(b-1)}{(r+b)(r+b-1)}$.
  • They're opposite colors with probability $\frac{2rb}{(r+b)(r+b-1)}$.

So the Two-Card Strategy wins with probability \begin{align} \frac{r(r-1) + b(b-1) + \frac12 \cdot 2rb}{(r+b)(r+b-1)} &= 1 - \frac{b}{r+b} \cdot \frac{r}{r+b-1} \\ &\ge 1 - \frac{b}{r+b} & \text{(since $b\ge 1$, $\tfrac{r}{r+b-1} \le 1$)}\\ &= \frac{r}{r+b}. \end{align} That is, whenever the other strategy decides to stop early, we would have done at least as well with the Two-Card Strategy, and therefore the Two-Card Strategy is optimal.


Also, the inequality is tight if the other strategy never stops when $\frac{r}{r+b-1} < 1$, an inequality equivalent to $b>1$. This gives us a general characterization of optimal strategies. A strategy is optimal if and only if it does both of the following:

  1. It never stops when there is more than one face-down card different in color from the top card;
  2. Just like the Two-Card Strategy, it stops when there are two face-down cards of different colors, rather than continue for a guaranteed loss.
$\endgroup$
  • $\begingroup$ Very nice!${}{}{}{}{}$ $\endgroup$ – quasi Feb 24 '18 at 17:13
  • $\begingroup$ brilliant. Thanks so much this explained everything! $\endgroup$ – introspectivemathematics Feb 24 '18 at 17:43
  • $\begingroup$ Also, I got that question from glassdoor and I was stumped so I posted here. I'm fairly good with probability but the optimal stopping strategy problems like this one still give me a lot of pause and I don't know where to start. So if you don't mind me asking a follow-up question, do you have any general advice on how to approach questions like this in an interview setting? $\endgroup$ – introspectivemathematics Feb 24 '18 at 17:45
  • $\begingroup$ @introspectivemathematics In an interview setting, your thought process matters more than your answer. (As an extreme example: if you already know the answer and say it, that doesn't help the interviewer learn much about you.) Think aloud through simple cases, make general observations that don't solve the problem (e.g. "we win if all the remaining cards are black" is a simple one here), make conjectures you can't prove and outline ways you can test them, etc. This is also, of course, good advice for how to start a problem in a non-interview setting. $\endgroup$ – Misha Lavrov Feb 24 '18 at 19:32
  • $\begingroup$ Awesome. Thanks again!! $\endgroup$ – introspectivemathematics Feb 24 '18 at 22:19
2
$\begingroup$

Without loss of generality, we can assume the initial top card is red.

Label the choices for the player as "hit" or "stop".

If the player chooses to hit, the old top card is discarded, and a new top card is dealt face up from the deck.

At any time when a choice of hit or stop is about to be made, and assuming the current top card is red, define the state of the game to be the pair $(r,b)$, where $r$ and $b$ are nonnegative integers, not both zero, representing the respective number of red cards and black cards remaining in the deck.

To simplify the analysis, when a player chooses to hit, if a black card is dealt as the new top card, change the color of the top card to red, and simultaneously toggle the colors of all the remaining cards in the deck. By symmetry, assuming the player uses an optimal strategy, this conversion doesn't affect the player's chance of winning.

Thus, for the analysis, force all top cards to be red.

Let $p(r,b)$ be the probability that the player wins the game, assuming

  • The current state is $(r,b)$.$\\[4pt]$
  • The current top card is red.$\\[4pt]$
  • The player uses an optimal strategy.

Then we have the following recursion . . . $$p(r,b)= \begin{cases} \text{if $r=0$ and $b=1$ then}\\[4pt] \qquad 0\\[4pt] \text{else if $r=0$ or $b=0$ then}\\[5pt] \qquad 1\\[2pt] \text{else}\\ \qquad \max\left( {\displaystyle{\frac{r}{r+b}}}, \; \left({\displaystyle{\frac{r}{r+b}}}\right)p(r-1,b) + \left({\displaystyle{\frac{b}{r+b}}}\right)p(b-1,r) \right) \\ \end{cases} $$ Implementing the recursion in Maple, we discover a very simple optimal strategy:

  • Stop only if $(r,b)=(1,1)$, or if one of $r,b$ is zero, and the other matches the color of the top card, otherwise hit.

Using this strategy, we get $$p(25,26)=\frac{38}{51}\approx .7450980392$$

Conjecture:$\;$The strategy specified above is optimal for any state $(r,b)$.

$\endgroup$
  • $\begingroup$ thank you so much! Couple questions: 1) I'm wondering if there is a good mathematical intuition for why that is the optimal solution, instead of just a recursion? 2) how did you get 38/51 for p(26,26) 3) maybe I"m misunderstanding p(r, b), shouldn't the beginning state be p(25,26)? $\endgroup$ – introspectivemathematics Feb 24 '18 at 16:30
  • $\begingroup$ With regard to your question $(3)$, yes, the beginning should be $p(25,26)\,-\,$ I'll fix it, but in fact $p(26,26)=p(25,26)$. $\endgroup$ – quasi Feb 24 '18 at 16:39
  • $\begingroup$ With regard to your question $(1)$, the intuition is "wait for a lock", where in gambling terminology, a lock is a game which is an automatic win (for the player who has that game). $\endgroup$ – quasi Feb 24 '18 at 16:41
  • $\begingroup$ With regard to your question $(2)$, I implemented the recursion in Maple, and kept track of all states where the max comparison of the recursion favored the hit rather than the stop. $\endgroup$ – quasi Feb 24 '18 at 16:45
  • $\begingroup$ Conjecture proven :) $\endgroup$ – Misha Lavrov Feb 24 '18 at 17:11

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.