In a Zener card test using a 25 -card pack and no replacement, what is the expected score if we try to minimise correct guesses?

Question

The Zener cards were invented by Karl Zener and used by J B Rhine in his experiments on extrasensory perception (ESP) at Duke University in the 1930s. They comprise cards of each of five types, showing a square, circle, star, cross, or wavy lines:

A standard pack contains 25 cards, five of each type.

A run consists of a subject trying to guess each card in a pack in turn. If we replace and shuffle after each guess, his expected score is 5. In another question I asked what the expected score is if we don't replace, and if instead we keep a record (or just remember) how many cards of each type have already come up. The answer turns out to be $\frac{23148348523}{2677114440}=8.65$ to 2 decimal places.

What is the expected score if we try to minimise it?

If we guess randomly for the first 21 cards we will know for certain at least one shape that does not appear in the next 4, and so we can make sure we get our last 4 choices wrong, which will give us an expected score of $\frac{21}{5}=4.2$. On average we can get lower still, because sometimes after guessing randomly for only 20 cards we will know that the remaining cards are not all different, in which case we will know at least one shape that doesn't appear in those 5 and we will get an expected score of $\frac{20}{5}=4$. So the answer is certainly less than 4.2.

Answer 1

As with the maximization problem, this admits to a recursive solution through what is effectively dynamic programming. Let the number of remaining cards of each type be ${\bf n}=(n_1, n_2, n_3, n_4, n_5)$. The probability of type $i$ coming up next is $p_i({\bf n})=n_i / \sum_j n_j$; if type $i$ comes up next, there will be ${\bf n}-{\bf e}_i$ remaining cards; and if the guess was $j$, then the change in score is $\delta_{i,j}$. So we can say that the expected score with best play satisfies $$ S({\bf n})=\min_j\left(\sum_i p_i({\bf n})\left[\delta_{i,j}+S({\bf n}-{\bf e}_i)\right]\right)=\min_j\left(p_j({\bf n}) + \sum_i p_i({\bf n})S({\bf n}-{\bf e}_i)\right) $$ if you're trying to minimize your score, and $$ T({\bf n})=\max_j\left(p_j({\bf n}) + \sum_i p_i({\bf n})T({\bf n}-{\bf e}_i)\right) $$ if you're trying to maximize it. Python code to compute the result is as follows:

def p(ns, j): return Fraction(ns[j], sum(ns))

def dS(ns):
    nn = list(ns)
    ret = Fraction(0, 1)
    for i in xrange(len(ns)):
        if ns[i] > 0:
            nn[i] -= 1
            ret += p(ns, i) * S(tuple(nn))
            nn[i] += 1
    return ret

def S(ns, cache = {}):
    if sum(ns) == 0: return 0
    if not cache.has_key(ns):
        cache[ns] = min([p(ns, j) + dS(ns) for j in xrange(len(ns))])
    return cache[ns]

Switching 'min' to 'max' yields $T$ instead. We find that $S((5,5,5,5,5))=\frac{2048941091}{892371480}\approx 2.296063,$ and $T((5,5,5,5,5))=\frac{23148348523}{2677114440}$ $\approx 8.646753.$

Answer 2

Partial answer: the answer may be around 2.30.

I do not know how to show that rigorously; that was the figure I got from a Monte Carlo experiment with a million runs. I used the following guessing technique: always guess that the next card will be of the least numerous type remaining; or if two or more types are equally least numerous, choose the type among them that is leftmost on the list (square, circle, star, cross, wavy). The largest score was 5, the smallest 0.

2.30 intuitively seems a very low expected score!

Here is an example of a pack that gives a score of 0:

(cross, wavy, wavy, cross, star, star, cross, star, square, square, square, star, wavy, cross, circle, circle, circle, circle, square, cross, wavy, wavy, square, star, circle)