I've come across an intriguing card game where a deck is used with cards numbered from $1$ to $N$.
The game proceeds as follows: the dealer draws cards one by one from the deck and shows the number on each card. At any point in the game, even before the first card is shown, a player can say "stop". If the number on the next card drawn is a prime number, the player wins; if it's not, the player loses. The cards in the deck are shuffled randomly, so there's no way to predict the order of the cards.
I'm trying to determine the best strategy for this game to maximise the chances of winning. Also, how would you calculate the probability of winning with this strategy for a given number of cards, $N$, in the deck?
Some clarifications:
- The number 1 is not considered a prime.
- You can see and remember the cards that have been drawn out, which can inform your strategy.
- Knowing the number $N$, you can identify all the prime numbers within that range beforehand.
- If all cards are drawn and you haven't said "stop" before the last one (even if it's not), you lose.
Additionally, the author of the problem mentioned that there should be a strategy that optimizes the probability of winning.
Best Answer
More generally, suppose that there are $n$ cards total in the deck, where that $k$ of the cards are considered to be good, while the remaining $n-k$ cards are bad. The goal is the same; the deck is shuffled, and as the cards are flipped from the deck, you have the option to call "stop" at any time. You win as long as the next card dealt is good. What is the optimal strategy?
Furthermore, let us modify the rules to say that, when there is only one card left, you must call stop. A player who does not call stop before the last card automatically loses, so this modification makes no difference to an optimal player.
It turns out that every strategy is the optimal strategy.
Therefore, to answer your question, the probability of winning is the number of primes in $\{1,\dots,N\}$, divided by $N$.
Proof 1: Clever insight
Consider this modification of the game. Suppose that, when you call stop, instead of winning when the next card dealt is good, you win if the bottom card of the deck is good. This is a silly game, because it does not matter when you call "stop." You will always win if and only if the bottom card is good. For the modified game, the probability of winning is $k/n$.
However, this game has the exact same probability for winning as the original. The point is that, after calling "stop", both the next card and the last cards have the same same random chance of being good, because of the symmetry of the shuffled deck. Therefore, it follows the original game has the same probability of winning.
Proof 2: Induction
We prove, by induction on $n$, that for all $k\in \{0,1,\dots,n\}$, the probability of winning is $k/n$ for all strategies in an $n$-card deck with $k$ good cards.
The base case of $n=1$ is obvious. Assuming that the statement is true for $n$, where $n\ge 1$, we prove it for $n+1$ as follows: $$ \begin{align} P(\text{win}) &=P(\text{win}\mid \text{first card is good})P(\text{first card good}) \\&\quad +P(\text{win}\mid \text{first card is bad})P(\text{first card bad}) \\&=\frac{k-1}{n-1}\cdot \frac{k}{n}+\frac{k}{n-1}\cdot \frac{n-k}{n}=\frac{k}n. \end{align}$$ This completes the proof by induction.
Proof 3: Martingale
For each $k\in \{0,1,\dots,n-1\}$, let $X_k$ be the proportion of good cards among the unseen cards after $k$ cards have been seen. So, $X_0=k/n$, and $X_1$ is either equal to $k/(n-1)$ or $(k-1)/(n-1)$.
Imagine the player is following a particular strategy. Let $T$ be the turn number that the player calls stop, under that strategy. The proportion of good cards at the time of the stop call is $X_T$, so $X_T$ is the probability the player wins (conditional on $T$). We just need to evaluate $\mathbb E[X_T]$, which is the unconditional probability of the strategy winning.
The sequence $X_0,X_1,\dots,X_{n-1}$ is a martingale, with respect to the natural filtration. To prove this, we must show that $\mathbb E[X_{k+1}\mid X_k]=X_k$ for all $k$. Indeed, given $X_k$, there are two possibilities; either you next draw a good card with probability $X_k$, in which case $X_{k+1}$ decreases to $\frac{(n-k)X_k-1}{n-k-1}$, or you draw a bad card with probability $(1-X_k)$, in which case $X_{k+1}$ increase to $\frac{(n-k)X_k}{n-k-1}$. Therefore, $$ \mathbb E[X_{k+1}\mid X_k]= X_k\cdot \frac{(n-k)X_k-1}{n-k-1}+\left(1-{X_k}\right)\frac{(n-k)X_k}{n-k-1}={X_k}. $$ Since the sequence is a martingale, and since $T$ is bounded, we can use the optional stopping theorem to conclude that $\mathbb E[X_T]=\mathbb E[X_0]=k/n$. Therefore, every strategy has a probability of success of $k/n$.