Question

You are being tested for psychic powers. Suppose that you do not have psychic powers. A standard deck of cards is shuffled, and the cards are dealt face down one by one. Just after each card is dealt, you name any card (as your prediction). Let X be the number of cards you predict correctly. (See Diaconis (1978) for much more about the statistics of testing for psychic powers.) (a) Suppose that you get no feedback about your predictions. Show that no matter what strategy you follow, the expected value of X stays the same; find this value. (On the other hand, the variance may be very different for different strategies. For example, saying “Ace of Spades” every time gives variance 0.) Hint: Indicator r.v.s. (b) Now suppose that you get partial feedback: after each prediction, you are told immediately whether or not it is right (but without the card being revealed). Suppose you use the following strategy: keep saying a specific card’s name (e.g., “Ace of Spades”) until you hear that you are correct. Then keep saying a different card’s name (e.g., “Two of Spades”) until you hear that you are correct (if ever). Continue in this way, naming the same card over and over again until you are correct and then switching to a new card, until the deck runs out. Find the expected value of X, and show that it is very close to e − 1. Hint: Indicator r.v.s. (c) Now suppose that you get complete feedback: just after each prediction, the card is revealed. Call a strategy “stupid” if it allows, e.g., saying “Ace of Spades” as a guess after the Ace of Spades has already been revealed. Show that any non-stupid strategy gives the same expected value for X; find this value. Hint: Indicator r.v.s.

Answer 1

The indicator variable is, as you suspected, for the event that a given card is guessed correctly. I'll call it Xi

for convenience:

For i=1,…,52

, let

Xi={10if card i is guessed correctlyotherwise

Then, using linearity of expectation,

E(X)=E(∑i=152Xi)=∑i=152E(Xi)=∑i=152P(Xi=1).

We seek P(Xi=1)

now. If we denote by Y (N) a correct (incorrect) guess for any particular card then the event "Xi=1" can be represented by the set of all possible strings of length i

of Ys and Ns ending in Y.

Take such a string and consider its substrings of maximally consecutive Ns and the following Y. For example, YNNYNNNNYYNY has 5

such substrings (because it has 5 Ys) of lengths 1,3,5,1,2

. We can calculate the probability of this outcome, given the rules of the game, to be:

152⋅5051⋅4950⋅149⋅4950⋅4849⋅4748⋅4647⋅146⋅149⋅4748⋅147=152⋅151⋅150⋅149⋅148

Hopefully, it's not hard to convince yourself of the pattern here that the probability of any given Y-N string is (52−k)!52! where k

is the number of Ys in the string.

Now, of all Y-N strings of length i

ending in Y, there are (i−1k−1) strings with exactly k Ys since we need to choose k−1 positions from i−1 possibilities for all Ys but the last. And since this k can range from 1 to i

, we have,

P(Xi=1)=∑k=1i(i−1k−1)(52−k)!52!.

So,

E(X)====∑i=152[∑k=1i(i−1k−1)(52−k)!52!]∑k=152[(52−k)!52!∑i=k52(i−1k−1)](swapping the order of summation)∑k=152[(52−k)!52!(52k)](using identity ∑r=pq(rp)=(q+1p+1))∑k=1521k!

Note now the Taylor expansion: ex=1+x1!+x22!+x33!+⋯

.

So, e−1=11!+12!+13!+⋯=∑k=1∞1k!

.

We can see E(X)

is a partial sum of this series and is extremely close to e−1