[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

A deck of ESP cards consists of 20 cards each of two types:

say ten stars, ten circles (normally there are five types). The deck is shuffled and the cards turned up one at a time. You, the alleged percipient, are to name the symbol on each card before it is turned up.

Suppose that you are really just guessing at the cards. If you do not get to see each card after you have made your guess, then it is easy to calculate the expected number of correct guesses, namely ten.

If, on the other hand, you are guessing with information, that is, if you see each card after your guess, then, of course, you might expect to get a higher score. This is indeed the case, but calculating the correct expectation is no longer easy.

But it is easy to do a computer simulation of this guessing with information, so we can get a good idea of the expectation by simulation. (This is similar to the way that skilled blackjack players make blackjack into a favorable game by observing the cards that have already been played. See Exercise \ref{exer 6.1.29}.)

• First, do a simulation of guessing without information, repeating the experiment at least 1000 times. Estimate the expected number of correct answers and compare your result with the theoretical expectation.
• What is the best strategy for guessing with information?
• Do a simulation of guessing with information, using the strategy in (b). Repeat the experiment at least 1000 times, and estimate the expectation in this case.
• Let [math]S[/math] be the number of stars and [math]C[/math] the number of circles in the deck. Let [math]h(S,C)[/math] be the expected winnings using the optimal guessing strategy in (b). Show that [math]h(S,C)[/math] satisfies the recursion relation
  [[math]] h(S,C) = \frac S{S + C} h(S - 1,C) + \frac C{S + C} h(S,C - 1) + \frac {\max(S,C)}{S + C}\ , [[/math]]
  and [math]h(0,0) = h(-1,0) = h(0,-1) = 0[/math]. Using this relation, write a program to compute [math]h(S,C)[/math] and find [math]h(10,10)[/math]. Compare the computed value of [math]h(10,10)[/math] with the result of your simulation in (c). For more about this exercise and Exercise \ref{exer 6.1.26} see Diaconis and Graham.

Notes