Approximate solution
Let’s suppose that the deck has $n$ cards in it, and we are dealt $k$ cards from the deck. Every time a card is flipped, we must decide whether to keep playing or to stop. Suppose we have flipped over $m$ cards already and the largest card flipped so far has a value of $a$. Some quick observations:
- If the last card we flipped has value smaller than $a$, then we must clearly keep flipping cards, for we would definitely lose if we stopped playing now.
- Assuming the last card we flipped has the largest value ($a$), we must evaluate the probability that the remaining $k-m$ cards are each smaller than $a$ (in other words, the probability that $a$ is the winner). We should compare this probability to the probability that we will win if we continue playing. Whichever is highest will dictate the optimal course of action.
One possible decision heuristic is to stop if the probability that the current card is a winner is greater than $1/2$ and to keep playing otherwise. This turns out to be a suboptimal strategy because our chances of winning might be even less if we keep playing! In other words, it could happen that we have a 49% chance of winning if we stop now but only a 45% chance of winning if we keep playing; in such a case, we should stop now and cut our losses. That being said, this suboptimal strategy is a very good approximation to the optimal strategy (and very easy to compute!) so let’s work it out.
Each of the $m$ cards we’ve flipped over so far is distinct and less than or equal to $a$. If the current card $a$ is the winner, then the remaining $k-m$ cards must all be chosen among the $a-m$ cards that are less than or equal to $a$. This can be done in $a-m \choose k-m$ ways. In total, there are $n-m \choose k-m$ ways of choosing the remaining cards. Therefore, we should stop playing if
\[
\frac{a-m \choose k-m}{n-m \choose k-m} \ge \frac{1}{2}
\]Clearly, this will be satisfied for $a$ sufficiently large, so our optimal decision rule is a threshold rule. There is no closed-form expression for the threshold value of $a$, but it’s straightforward to compute numerically. Here is a plot of the approximate decision rule for the case $n=100$, $k=10$.
The triangular white region in the lower corner corresponds to the case $a < m$, which can't occur because $a$ must be the largest number seen so far and all numbers must be distinct.
Exact solution
To get an exact solution, we’ll use dynamic programming. Let the cards be numbered $\{1,2,\dots,n\}$ and let $k$ be the number of face-down cards at the start of the game. In general, one might expect an optimal strategy to depend on the individual values of all the cards revealed thus far. This is not the case. It turns out that the optimal strategy only depends on:
- How many cards we’ve seen so far (we’ll call this $m$)
- The highest-valued card we’ve seen so far (we’ll call this $a$)
- Whether the last card turned over is the largest so far or not.
We’ll define two functions, $V^\text{lo}_m(a)$ and $V^\text{hi}_m(a)$, to record the probability of winning the game in the case where the latest card we turned over is low or high, respectively.
Base case: Suppose $m=k$, so we have just flipped over the final card. The game automatically ends and we have no decisions to make. We win if the card we flipped over is the highest numbered card. In other words:
\[
\begin{aligned}
V^\text{lo}_k(a) &= 0 \\
V^\text{hi}_k(a) &= 1
\end{aligned}\qquad\text{for }a = 1,\dots,n
\]
Recursion: Now suppose that we’re $m$ steps into the game. Let’s start with the case of a low flipped card. Here, we’ll lose for sure if we stop the game. So we must keep playing. We’ll assume $y \in S$ is the next card we flip over. Here, $S \subseteq \{1,\dots,n\}$ is the set of cards we haven’t seen yet. Note that $|S| = n-m$ because we have flipped over $m$ cards so far. Any of these $n-m$ remaining cards could be flipped over next with equal probability. Let’s treat the cases $y < a$ and $y > a$ separately:
\begin{align}
V^\text{lo}_m(a) &= \frac{1}{n-m}\biggl( \sum_{y\in S,\,y < a} V^\text{lo}_{m+1}(a) + \sum_{y\in S,\,y > a} V^\text{hi}_{m+1}(y) \biggr) \\
&= \frac{1}{n-m}\biggl( (a-m) V^\text{lo}_{m+1}(a) + \sum_{y=a+1}^n V^\text{hi}_{m+1}(y) \biggr)
\end{align}In the last step, we use the fact that there are precisely $a-m$ terms in $V^\text{lo}$ sum, which doesn’t depend on $y$. In the $V^\text{hi}$ sum, we’re summing over all values larger than $a$, and no such values have been used yet.
For the case of a high flipped card, we can choose to either stop the game or keep playing. If we stop the game, we will win if the remaining $k-m$ cards all happen to be smaller than $a$, our current high card. There are $a-m$ cards that satisfy this property and $n-m$ cards left total, so the probability of winning is ${a-m \choose k-m}/{n-m \choose k-m}$. If we decide to keep playing instead, we get the same answer as in the low case. Therefore, our recursion is:
\[
V^\text{hi}_m(a) = \max\biggl\{ \underbrace{\frac{{a-m \choose k-m}}{{n-m \choose k-m}}}_{\text{STOP}}, \,
\underbrace{V^\text{lo}_m(a)}_{\text{PLAY}} \biggr\}\qquad\text{for }a=1,\dots,n
\]At this point, it’s not possible to proceed any further without resorting to numerical computations. The good news is that these recursions are relatively easy to tabulate numerically; we can store all relevant probabilities in two matrices $V^\text{lo},V^\text{hi} \in \mathbb{R}^{k\times n}$ and we can compute everything in $\mathcal{O}(n^2k)$.
Here is a plot of the optimal decision rule for the case $n=100$, $k=10$.
As we can see, this plot is very similar to the approximate rule. Here is a table of the threshold values for comparison:
| Cards flipped |
Approximate Threshold |
Optimal Threshold |
| 1 |
93 |
93 |
| 2 |
93 |
92 |
| 3 |
92 |
91 |
| 4 |
90 |
89 |
| 5 |
88 |
87 |
| 6 |
86 |
84 |
| 7 |
82 |
80 |
| 8 |
74 |
72 |
| 9 |
55 |
55 |
| 10 |
10 |
10 |
This means that e.g. if our ninth card is $55$ or greater, we should stop playing. Note that if we make it to the 10th turn and our final flipped card is still a contender (i.e. the largest we’ve seen so far), then that card cannot have a value less than $10$ and we automatically win.
Probability of winning
So how do we compute the actual probability of winning? We already have! If we have recursed all the way to $m=1$, then $V^\text{hi}_1(b)$ tells us the probability of winning given that the first card we flipped over was $b$ (and, of course, it was our highest card). Since all cards are equally likely first cards, we have:
$\displaystyle
\mathbb{P}(\text{winning}) = \frac{1}{n}\sum_{b=1}^n V_1^\text{hi}(b) = V_0^\text{hi}(1)
$
For the case $n=100$ and $k=10$, the probability of winning is 62.19%.
Limiting cases
We can easily compute what happens if we add more cards. Let’s fix $k=10$ and try $n=1000$.
As we can see, things don’t look that much different as we make $n$ large. We can approximate this limiting shape by taking the limit $n\to\infty$ while holding $a$ as some fixed fraction of $n$ and using our approximate strategy instead of the optimal one:
\begin{align}
\frac{a-m \choose k-m}{n-m \choose k-m}
= \prod_{j=1}^{k-m} \frac{a-m+1-j}{n-m+1-j}
\approx \prod_{j=1}^{k-m} \frac{a}{n}
= \left(\frac{a}{n}\right)^{k-m}
\end{align}Therefore the threshold (when this probability hits $1/2$) occurs when:
\[
a \approx n\,2^{-\frac{1}{k-m}}
\]We can overlay the limiting case formula with the actual one to see how well they match. Here is an example with $n=10000$ and $k=40$:
It’s a pretty good fit, with the thresholds for the optimal strategy being slightly lower than the optimal ones. Increasing $k$ is also straightforward, and simply amounts to shifting the above pictures to the right!
Note: computing the ratio of binomial coefficients can be difficult if done naively, since it involves the ratio of two very large numbers. The method I used in producing my plots was to convert the expression into a product:
\[
\frac{a-m \choose k-m}{n-m \choose k-m}
= \prod_{j=1}^{k-m} \frac{a-m+1-j}{n-m+1-j}
\]then computing each term of the product and multiplying them together.
