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[N] = 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,

(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 which 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
E[N] = 1 + 1/2! + 1/3! + · · · + 1/n!
‰ˆ e ˆ’ 1
For all parts, express N as the sum of indicator (that is, Bernoulli) random variables.

Transcribed Image Text:

EM = n + n-1 + -dx=log n