Highest Card

From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.

What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?

(fivethirtyeight)

Solution

Without changing anything important, let’s restate the generalized situation as your being dealt a certain number $T$ of cards, one at a time, from a deck of $S$ cards. You can “hold” just once, and you win if the card you hold is higher than the cards dealt before or after it.

At every decision point (i.e., when you have a card higher than any others that have been dealt and need to decide whether to hold), whatever values $S$ and $T$ have, the important facts you know are that you have been dealt a given card $C$, that there are $D$ cards left to be dealt, $L$ cards lower than this one still in the deck (where $L$ is $C-1$ minus the number of cards already dealt), and $N$ cards total still in the deck. Since $L$ and $N$ are simple functions of the variables $C$ and $D$ (and the constants $S$ and $T$), it’s those latter two variables that your decision depends on entirely. Nonetheless, we will also it will also be useful in our calculations to keep track of the highest card $H$ so far seen (including $C$) as we define $P(C,D,H)$, which labels the probability that you will ultimately win if you get $C$ with $D$ cards still to be dealt and $H$ the highest so far.

If $C$ itself is the highest card so far, the probability of winning by holding it is the chance that it is higher than the $D$ cards left to be dealt, which in turn is the chance $L/N$ that it’s higher than the first of them, times the chance $(L-1)/(N-1)$ that it’s also higher than the second, and so on until the chance $(L-(D-1))/(N-(D-1))$ that it is higher than the last. Thus the probability that the current card is the highest is:

This has to be compared with the probability that you will win if you discard this card and play optimally afterwards; you will of course choose the option with the higher probability of winning. We can compute this value $P_{\mbox{Discard}}(C,D,H)$ recurrently, based on averaging the chances $P(C’,D-1,H’)$ of winning given all the possible cards $C’$ in the next round, when there will be $D-1$ cards still to be dealt. Where $K$ is the number of cards remaining lower than $H$ (which is $H$ minus the number, $T-D$, of cards already dealt—or 0 if that’s negative), and relying on the fact that the precise values of those cards doesn’t matter:

And our recurrence is as follows:

And for $D\geq 1$, if $C \lt H$:

And if $C=H$:

In the case of a deck of $100$ cards with $10$ to be dealt, you will make up to $9$ decisions. Here are the thresholds below which you should discard each of the first nine cards dealt, even if it’s the highest so far:

Numerically averaging the values of $P(C,9,C)$ for all possible first cards $C$ shows that the strategy wins about $62.2\%$ of the time.

[Note: this solution replaces one that was shown to be “alternatively correct” by a helpful commenter!]

Code (Python):

DeckSize = 100
TotalDeals = 10

# Probability of winning if, not having held yet, we get card C with D 
# cards remaining to be dealt and H the highest card so far dealt 
#(including C): P[(C,D,H)]
P_Win = {}

# The true/false value of whether it's best to hold rather than discard
# in that situation: Hold[(C,D,H)]
Hold = {}

def GetP_Win(Card,StillToBeDealt,HighestSoFar):
	global P_Win,Hold,DeckSize,TotalDeals

	if (Card,StillToBeDealt,HighestSoFar) in P_Win:
		# already figured this one
		return P_Win[(Card,StillToBeDealt,HighestSoFar)]

	HaveBeenDealt = TotalDeals - StillToBeDealt
	# Assume we'll discard; change later if holding is better:
	Hold[(Card,StillToBeDealt,HighestSoFar)] = 0

	if StillToBeDealt == 0:
		# Card is the final card.
		if Card == HighestSoFar:
			P_Win[(Card,StillToBeDealt,HighestSoFar)] = 1
			return 1
		else:
			P_Win[(Card,StillToBeDealt,HighestSoFar)] = 0
			return 0

	RemainingSubHighest = max(HighestSoFar-(HaveBeenDealt-1),0)
	Remaining = DeckSize-HaveBeenDealt

	# Calculate probability of victory if we discard.
	# Probability is the average of probabilities in the next deal
	P_Discard = (1/Remaining) * (\
		RemainingSubHighest*GetP_Win(0,StillToBeDealt-1,HighestSoFar) + \
		sum([GetP_Win(C,StillToBeDealt-1,C) for C in range(HighestSoFar+1,DeckSize)]) \
		)
	# Calculate probability of victory if we hold.
	P_Hold = 1
	for i in range(StillToBeDealt):
		P_Hold *= (RemainingSubHighest-i)/(Remaining-i)
	if not Card == HighestSoFar or P_Discard > P_Hold:
		P_Win[(Card,StillToBeDealt,HighestSoFar)] = P_Discard
	else:
		P_Win[(Card,StillToBeDealt,HighestSoFar)] = P_Hold
		Hold[(Card,StillToBeDealt,HighestSoFar)] = 1
	return P_Win[(Card,StillToBeDealt,HighestSoFar)]

# Main Program

accum_prob = 0

for Card in range(DeckSize):
	accum_prob += GetP_Win(Card,TotalDeals-1,Card)

print("Overall probability of victory:",accum_prob/DeckSize)
print("Thresholds (card dealt : threshold to hold):")
for i in range(1,TotalDeals):
	for c in range(DeckSize):
		if Hold[(c,i,c)] == 1:
			# Remember that our cards start at 0
			print(i,":",c+1)
			break