Optimal strategy to a card game

Question

There are $3$ face down cards in front of you. On the side facing the table (you cannot see this), there are labels on each of the three cards. They are $n$, $n + 1$, and $n + 2$. You are not told what $n$ is.

You get to flip a card at random. After flipping the first card, you can either stay or choose another card at random. Then, you again have the option to stay or flip the last card.

Once you flip one card, you cannot go back to the previous card's value.

How can you maximize the value of the card you choose to stop flipping on?

---

My thoughts:

You can achieve an expected value of $n + 1$ by just stopping on the first card every time.

If you flip another card and it is one less than the first one you flipped over, the last card is $n + 1$ with probability $\frac{1}{2}$ (this occurs when the first card you flipped was $n$), and the last card is $n$ with probability $\frac{1}{2}$. So, I think that the expectation of the last card given the second card you flipped is one less than the first one is equal to $n + \frac{1}{2}$.

If you flip another card and it is one more than the first one you flipped over, again, I think that the expected value of the last card is $n + \frac{1}{2}$

Anyone have an optimal strategy?

Answer 1

Here is a basic strategy that should do better than just flipping one card and staying with it:

Always flip a second card after the first. If the second card has a higher value than the first, stick with the second card, otherwise flip the third card.

Why does this better than staying with just the one first card?

Well, as you say, just flipping one card has an expected value of $n+1$

But for the other strategy:

There are 6 cases to consider, each of which is equally likely:

First card is $n$, second is $n+1$. The strategy says to stick with the second card, so outcome is $n+1$

First card is $n$, second is $n+2$. Stick with card. Outcome is $n+2$

$n+1$ followed by $n$. Strategy says to flip third card. Outcome $n+2$

$n+1$ followed by $n+2$. Stick with card: $n+2$

$n+2$ then $n$. Flip third card: outcome is $n+1$

$n+2$ then $n+1$. Flip third card: $n$

Since each of these events is equally likely, the expected outcome of this stratey is just the average of these outcomes, which is $n+\frac{4}{3}$

OK, so that's indeed a better strategy. Is it optimal? I don't know.

Answer 2

You can confirm it is optimal, in the following, somewhat tedious way. Firstly, note that there are only two decisions to make. Either you stay on the first or you leave the first and choose one of stay/leave on the second. If you stay on the first, expectation is $n+1$.

If you open the second, there are 4 things you can see. Either a difference of +1, a difference of -1, a difference of +2 or a difference of -2. If you just list out the cases, you see that there's a 2/6 chance of +1, a 2/6 chance of -1, a 1/6 chance of +2 and a 1/6 chance of -2. For instance, if you see +1 then that comes from the first being $n$ and second being $n+1$ or the first being $n+1$ and the second being $n+2$ (both of which are equally likely).

Then for each possible difference, you can compute the expected value of staying vs leaving. For instance, if we see +1 and stay, there's a 1/2 probability we have $(n+1)$ and a 1/2 probability we have $(n+2)$, giving an expectation of $(n+\frac{3}{2})$. On the other hand, if we see +1 and leave, then there's a 1/2 chance we get $n$ on the final stage (i.e. we first drew $n+1$ and then drew $n+2$) and a 1/2 chance we get $(n+2)$, leaving us with an expectation of $n+1$. So we know that if we are leaving the first and see a difference of +1, then staying with the second is better than leaving the second.

If we see -1 and leave, there's a 1/2 chance we end up with $(n+2)$ and 1/2 chance we end up with $n$, giving an expected value of $n+1$, whereas if we see -1 and stay, we have a 1/2 chance of $n$ and a half chance of $n+1$, giving $n+\frac{1}{2}$. So we know that if we see -1 then leaving the second is better. If we see +2 then clearly staying is best and we get $n+2$ with probability 1 and if we see -2 then clearly leaving is best and we get $n+1$ with probability 1.

Summing up, we have shown that assuming we leave the first card, then the optimal strategy is as follows: if we see +1 then stay, if we see -1 then leave, if we see +2 then stay and if we see -1 then leave.

Then by the calculation in Bram28's comment, we see that the expectation of leaving the first and then following the choices described above leads to an expectation of $n+\frac{4}{3}$, which is better than staying with the first card. So the optimized strategy after leaving the first card is better than sticking with the first card and hence the overall optimal strategy.