A deck of n cards, partial feedback strategy

Question

A deck of n cards numbered 1 through n are to be turned over one at a time. Before each card is shown you are to guess which card it will be. After making your guess, you are told whether or not your guess was correct but not which card was turned over. It turns out that the strategy that maximizes the expected number of correct guesses fixes a permutation of the n cards and then continually guesses 1 until it is correct, then correctly guesses 2 until either it is correct or all cards have been turned over, and then continuously guesses 3 and so on. Let G denote the number of correct guesses yielded by this strategy. Determine P(G=k). Hint: In order for G to be at least k what must be the order of the cards 1....k

Not even sure where to start. I thought G is a binomial random variable with n trials but can't find an expression for the probability of success.

Answer 1

Hint:

Suppose the 2 is somewhere before the 1 in the ordering. You will get exactly 1 number correct. Suppose the 2 is somewhere after the 1 in the ordering. You will get at least 2 numbers correct. Therefore, $P(G=1) = P(\text{2 is before 1 in the ordering of cards})$.

Suppose you will reach 1 before 2 in the order, but you will also reach 3 before 2. Then you will get exactly 2 numbers correct. Suppose 1 is before 2 is before 3. You will get at least 3 numbers correct. Therefore, $P(G=2) = P(\text{1 and 3 are before 2 in some order})$.

...

Let's try to calculate $P(G=k)$. To start, let's calculate the number of orders that yield $G=k$. A valid order will have the numbers $1,\ldots, k$ in order with $k+1$ before $k$. So, choose $k+1$ of the $n$ positions. Place the number $k$ in the far right position. That leaves $k$ chosen positions. Choose one and place $k+1$. The remaining $k-1$ positions are for the numbers $1,\ldots, k-1$ in order. This leaves $n-k-1$ positions for that many cards in any order. So, $$ P(G=k) = \dfrac{ k \dbinom{ n }{ k+1 } ( n-k-1 )! }{ n! } = \dfrac{ k }{ (k+1)! } $$ and this works for all values up through $k=n-1$. For $G=n$ we have $P(G=n)=\dfrac{1}{n!}$.

Answer 2

More directly using the hint you got: For $G$ to be at least $k$, the cards $1$ through $k$ must all appear in order, since if one if them comes before a smaller one it won’t be guessed. There are $k!$ equiprobable orders in which $k$ cards can be drawn.

Here’s a fun follow-up when you’ve solved this one: How many cards would you expect to guess correctly in the limit that the deck has infinitely many cards?