The problem considered in this post and the problems in the two posts immediately prior to this one, here and here, were among a number of problems posed to me last semester by a client who was taking an upper division probability course at Penn State. I found these three problems particularly interesting. I hope you do too.
A deck of cards numbered 1 through is shuffled such that all possible orderings are equally like. Cards are removed from the deck sequentially until no more cards remain. At each step you make a guess as to the the value of the card removed. Three variants of the game are considered.
- Variant 1:
-
You are not given any information about the cards removed at previous step before you make a guess at the current step.
- Variant 2:
-
At each step, you are shown the card that is drawn.
- Variant 3:
-
You are told at each step if your guess is correct or not, but not the value of the card removed.
Under each of the three variants find a guessing strategy that maximizes the expected number of correct guesses and find the the maximum.
Two different methods of solution are used, one for both variants 1 and 2, and a second for variant 3.
Set 1 where is your guess for the card at step . represents your strategy. Denote the number of correct guesses under strategy by .
The first method is the standard approach used to find the expected number of success in a sequence of Bernoulli trials. In this approach a sequence of Bernoulli random variables by is introduced. Clearly, The linearity of expectation, and the expected value of Bernoulli random variable give This reduces the problem to find .
The second approach starts with a well-known result on the expectation of nonnegative discrete random variables: Let denote the number of trials needed to observe correct guesses under strategy . One has Consequently At this point the problem is reduced to finding the marginal distributions of .
The reason that two methods are employed is that in the first two variants, the information about the cards removed prior to a given step does not depend on the the outcomes of the prior steps, while in the third variant that information does depend on the outcomes of the prior steps. So if the first method were used to solve the third variant one would have to condition on the prior steps. One way to handle this would be to introduce the sequence which would be conditioned on. This would necessitate finding the marginal distributions of the random variables in this sequence, it makes sense to simply use them directly to find the expectation.
Let denote the event that your guess at step is a card that remains in the deck under strategy . Conservation of total probability gives In this variant, there is no information about the cards removed in prior steps. Hence for any strategy Further, Thus . This is substituted into to obtain for all .
In this variant, at each step you know all of the cards that remain in the deck. Thus for any strategy which selects a card that remains in the deck at each step , In this case, gives This is substituted in to yield for any strategy which selects a card at each step that remains in the deck. For any strategy that selects a card not in the deck as some step , . Hence . Therefore equation gives the maximum.
In this variant, at the first step you know your guess is a card in the deck, at each step afterward you only know which of the cards were removed form the deck at previous steps where your guess was correct, but you do not know what cards were removed from the deck at previous steps at which your guess was incorrect. As will be seen, the optimal strategy for this variant is to stick with a guess until it is correct, and once it is correct change your guess to a guess you have not yet made. Let denote such a strategy.
As discussed above the equation where is the number of steps until correct guess are made, is used here. This necessitates finding the distributions of these "negative binomial"-like random variables.
Since the first guess is always a card that remains in the deck, For , is found by a straightforward conditioning argument. The first correct guess occurs at a given step if and only if at all previous steps the guess was incorrect. Thus where the dependence of the s on the strategy has been suppressed to uncluttered the notation; This should not lead to any confusion. Under the strategy the guess at step and all previous steps is the same as the initial guess whenever no correct guesses have occurred in the previous steps, further the initial guess remains a card in the deck at all steps up to . Consequently Therefore for all , Conservation of total probability yields the following set of coupled equations for the distributions of the other s. for , and it is zero for ; . Let denote the number of trial needed to observe the first correct guess in a deck with cards. Then for On the other hand, if the correct guess occurs at step , then under strategy your guess at step will not be one of the cards you know have been removed from the deck. Thus you guess will be selected from the cards which may remain in the deck. Since cards remain in the deck following step for . Equations and are substituted into to obtain the coupled equations .
Induction on is used to prove that for that The reader is encouraged to work out a few cases to convince themselves that this ansatz is reasonable.
The base case is . One has from that Hence the base case holds. The induction hypothesis is given in . It is used long with to obtain The hockey-stick combinatorical identity gives On the other hand, it is straightforward to verify algebraically that Therefore This completes the proof of .
The hockey-stick identity is used again to obtain It follows that
To prove that is the maximum expected number of correct guess in variant 3, return to The strategy is at every step never guess a card that you know has been removed from the deck, and only change guess after a correct guess. Let denote a strategy such that after a correct guess at step your guess at step is a card that you know has already been removed from the deck at a previous step. Then Thus under
On the other hand, let be a strategy in which a guess is changed after an incorrect at step that comes after the the correct guess at step and before the next correct guess at step . With this strategy, the appropriate probability to consider is Hence .
It follows that maximizes the expected number of correct guesses.
The solution to variant 3 presented here is a brute force calculation. I would like to see a subtle probabalistic solution for this variant. If you have one, please post it in comments.