1

Deck of $n$ cards numbered $1$ through $n$ are turned over one at a time. Before each card is shown, you are supposed to make a guess which card it will be. Once the guess is made you are told whether the guess was correct but not which card was turned over. The strategy that maximizes the expected number of correct guess fixes a permutation of the $n$ cards. Let $G$ be the variable denoting the number of correct guesses yielded by this strategy.

  • You may as well assume the strategy is the identity permutation; then the random variable $G$ is exactly the number of fixed points of a random permutation. There is a recurrence for this in terms of derangements but I don’t think there’s a clean formula. – J.G Jun 27 '19 at 04:12
  • I'm confused why the strategy fixes a permutation. Aren't you allowed to change your guesses based on whether you were previously correct or incorrect? Otherwise, why include that information. – mathworker21 Jul 23 '19 at 16:22

1 Answers1

0

Please see Example $4.8$ of The Analysis of Sequential Experiments with Feedback to Subjects by Persi Diaconis and Ronald Graham, p. $18$

PTDS
  • 3,464