Chapter 7, Problem 7.17P

A deck of n cards numbered 1 through n is thoroughly shuffled so that all possible n! orderings can be assumed to be equally likely. Suppose you are to make n guesses sequentially, where the ith one is a guess of the card in position i. Let n denote the number of correct guesses.

a. If you are not given any information about your earlier guesses, show that for any strategy, $E\left[N\right]=1$.

b. Suppose that after each guess you are shown the card that was in the position in question. What do you think is the best strategy? Show that under this strategy, $\begin{array}{l}E\left[N\right]=\frac{1}{n}+\frac{1}{n-1}+\mathrm{...}+1\\ \approx {\displaystyle {\int }_1^n\frac{1}{x}dx}=\log n\end{array}$

c. Suppose that you are told after each guess whether you are right or wrong. In this case, it can be shown that the strategy that maximizes E[N] is one that keeps on guessing the same card until you are told you are correct and then changes to a new card. For this strategy, show that $\begin{array}{l}E\left[N\right]=1+\frac{1}{2!}+\frac{1}{3!}+\mathrm{...}+\frac{1}{n!}\\ \approx e-1\end{array}$

Hint: For all parts, express

N as the sum of indicator (that is, Bernoulli) random variables.