Friday, July 20, 2012

Sense and Mind

One of the staples of parapsychology is extrasensory perception—ESP.  Apparently, in the early days of ESP investigations, a standard deck of cards was used, but it had some infelicities: The cards had in some cases complex designs that some claimed would interfere with the measuring of ESP ability, and the backs could be used by charlatans to identify cards by means other than honest ESP.  Thus were born the Zener cards.

Zener cards are those specially designed ESP cards that you've no doubt seen: a circle, a plus, wavy lines, a square, and a star—five of each in a 25-card deck.

OHAI BACON.
 
Not only are they simple, straightforward designs, but when placed in the foregoing order, they also embody (in some intuitive way) the numbers one, two, three, four, and five.  Nonetheless, when they were first introduced, Zener cards had many of the same problems as did the ordinary playing cards.  The first Zener cards were made of thin enough paper that it soon became evident that some purported ESPers were simply looking through the cards.  They were subsequently made with thicker paper with opaque backs.

Another problem that arose was that some of the first ESP experiments allowed the participants to see the cards as they were guessed.  In a 25-card deck, random guessing should permit you to correctly guess one-fifth of the cards, or five of them.

However, if you are permitted to see each card after guessing, you can determine which pattern is most likely to show up on the next card.  For instance, suppose you guess that the first card is a circle.  It comes up, let us say, a square.  That one is guessed wrong, but by seeing that the first card is actually a square, you gain the knowledge that the second card is slightly less likely to be a square than any of the other patterns (since there are only four squares left, but five of each of the others).  Each succeeding card gives you even more information.  By the end, with careful counting, the last card is precisely determined; it is the only one that has only shown up four times.

If you always guess optimally, you will correctly guess almost nine cards out of the 25.  That is a level of accuracy that one would otherwise obtain with a probability of only 0.05—the level at which one is provisionally determined to possess genuine ESP.  Needless to say, such experiments were quickly barred.

Suppose, though, that you did an ESP exhibition.  You are not permitted to see the cards after each guess, but you do get to hear the response of the audience to each successive guess and card.  Even without collusion, it isn't much of a stretch to imagine that you'd be able to determine whether you guessed correctly or not.  How many will you guess correctly now, on average?  It should be clear that the number should be somewhere between five and nine, since you have more information than when you didn't get any feedback, but somewhat less information than when you saw each card.

To see some of the issues in determining the expectation, consider a much shorter deck: a five-card deck, with one of each design.  If you receive no feedback at all, you should be able to guess each card correctly with probability 1/5, or an average of one correct card in all.

On the other hand, suppose you see each card after you guess it.  The first card, you guess correctly with probability 1/5.  Having seen what card it actually is, you know which four cards remain, so you guess the second card with probability 1/4.  The third card is guessed with probability 1/3, the second card with probability 1/2, and the last card with complete certainty—probability 1.  To determine the average number of correct cards, simply add up the probabilities: 1/5 + 1/4 + 1/3 + 1/2 + 1 = 137/60; a bit more than two-and-a-quarter cards.

Now, suppose you find out only if your guess was correct.  For the first card, you have no reason to expect that any pattern is more likely than any other; therefore, without loss of generality, suppose that you guess a circle.  You will be correct with probability 1/5.

Suppose you guess correctly.  You are left with a four-card deck, each card equally likely.  Again, since you have no reason to believe any pattern is more likely to be in the second position than any other, you can guess any pattern; let us suppose you guess a plus sign.  This time, you will be correct with probability 1/4.

On the other hand, suppose your guess of a circle on the first card was incorrect.  In that case, the circle must be somewhere in the four remaining cards; it is 1/4 likely to be in the second position.  The other patterns, however, could still have been in any of the five original positions, including the first one.  You know only that it was not a circle.  Therefore, you should also guess that the second card is a circle; we are once again correct with probability 1/4.

It is with the third card that matters become more interesting.  Suppose you guessed correctly on both of the first two cards: the first was a circle, and the second was a plus sign.  You can guess any of the three remaining patterns for the third card; let us suppose that you guess the wavy lines.  You will be correct with probability 1/3.

Or, if you guessed both cards wrong—neither of the first two cards was a circle—you should guess a circle once again for the third card, which will be correct with probability 1/3 again.

Or, if you guessed right on the first card but wrong on the second—that is, if the first card was a circle, but the second card was not a plus sign—you should guess a plus sign again on the third card, which will be correct with probability 1/3 yet again.

The last case is the difference.  If you guessed wrong on the first card, but right on the second, then we know only that the second card was a circle.  The other remaining cards could have been any of the four remaining patterns with equal likelihood.  You can guess any of them, but you can do no better than a probability of 1/4 of guessing correctly.

The analyses of the fourth and fifth cards are more complex.  So the question of this post is: What is a better way of approaching the problem?  What is the average number of cards you will guess correctly?

EDIT: The second question of this post is: Suppose you have k cards, all distinct.  If you always guess optimally, and find out whether each guess was correct (but not what the card actually was), then what is the expected number of correct guesses?  Does this number approach a limit as k increases without bound?  If so, what is that limit?  The answer may surprise you. 

(If you are not given any feedback on your guess, then the expected number of correct guesses is always k × 1/k = 1.  If you get to see each card after you guess it, the expected number of correct guesses is 1 + 1/2 + 1/3 + ··· + 1/k, which goes up as the natural log of k (and is therefore unbounded).  The question above has to do with the situation where you only get feedback on whether your guess was correct or not.)

4 comments:

  1. Well, no. :) It has to be more than one. But e is definitely wound tightly into the plot.

    ReplyDelete
  2. Yes, that conclusion (it's related to e) jumps out pretty quickly from the formula for k cards.

    Let f(k,j,m,i) be the expected number of remaining correct guesses if you started with k cards, have j guesses remaining, have already guessed m correctly, and the last i guesses were incorrect.

    Let nCk represent "n choose k", that is,
    nCk = n!/((n − k)!·k!).

    If 1 ≤ j ≤ k, m ≤ k − 1, and 1 ≤ n ≤ j, let

    g(k,j,m,n) = (jCn)(k − m − n)!/(k − m − 1)!

    Then

    f(k,j,m,i) = (g(k,j,m,1) + g(k,j,m,2) + ⋯ + g(k,j,m,j))/(k − m − i)

    I believe I have a proof of this by induction on j.

    But you just want to know the value of f(k,k,0,0). In that case, set j = k, m = i = 0, so

    g(k,j,m,n)/(k − m − i)
    = g(k,k,0,n)/k
    = ((kCn)(k − n)!/(k − 1)!)/k
    = (kCn)(k − n)!/k!
    = 1/n!

    Therefore,

    f(k,k,0,0) = 1 + 1/2! + 1/3! + ⋯ + 1/k!

    I don't know if there's a simpler way to get that result. Also, what about the case where your deck contains c copies of each of the k distinct cards (as is the case with the Zener deck)?

    ReplyDelete
  3. @David: Well done, that's exactly right.

    As for your other question--what happens when their are multiple copies of each of the distinct kinds of cards--I'm not sure I see a good way to go at the problem analytically. The strategy is non-trivial. I'm open to suggestions!

    ReplyDelete