In response to my recent post about Monty Hall problems, DJP send me a link to Cover's Game^(*). (Courtesy of Harvard CS department CS220r: Cryptography taught by Professor Michael Rabin. For the 2005 course, it is found as an extra credit question on Problem Set 5.)

The game goes like this. A person gives you a challenge. He tells you the following:

1. He has a probability distribution in mind over the integers. Let's call it p. But he is not telling you what p is. (Probability distribution over the integers means that p is a function of integers i, 0≤p(i)≤1, and that summing p(i) over all integers i would result in 1.)
2. He will pick two numbers at random according to his probability distribution p. It is guaranteed that the two numbers will be different (if they are the same, he will discard one of them and pick again, until he gets a different number). Call them {x,y}.
3. He will then flick a true coin (with equal probability of landing heads or tails). If heads, he will tell you the value of the larger of the two numbers. Otherwise he will tell you the value of the smaller of the two numbers. Of course, this is done in secret so you don't know whether the coin landed heads or tails.

Your goal is, after he tells you a number, guess whether the number is the larger one or the smaller one.

Every time the game is played, he will pick a new probability distribution, so you cannot gain information from playing the games multiple times.

---

It is easy to see that a naïve random guess will have a winning probability of 1/2, because of the outcome of the true coin. It is, however, possible to achieve a winning probability of 1/2 + ε for some ε > 0 that depends on the probability distribution p. The question is, how?

---

The solution: pick a probability distribution q yourself, with the property that 0<q(i)<1. The strict inequality guarantees that every number has a non-zero chance. According to that distribution, pick some random number z. And play the game as follows:

If the number he tells you is greater than or equal to z, then tell him that the number is the higher one. Otherwise tell him the number is the smaller one.

How does this help? Here I give a heuristic (a.k.a. not very rigorous) argument to demonstrate the power of the solution.

Suppose, without loss of generality, that z = 0. Then a priori, we know that one of the following three can happen

1. both x,y are non-negative.
2. both x,y are negative.
3. one of x,y is negative, while the other is not.

Let s = ∑_i<0p(i) (which is some number we don't know). Then case one happens with probability (1-s)², case two happens with probability s², and case three happens with probability 2s(1-s).

We notice that in case three, our strategy would guarantee us a win. In cases one and two, however, our winning percentage is as good as randomly guessing, which is 1/2 because of the true coin.

So in the end, we have a total winning probability of

1/2 + s(s-1)

If s is not zero, and if s is not one, then we have a winning probability strictly larger than 1/2. But of course, it is possible that the initial probability distribution p is so skewed that s = 0. What do we do?

That is why we pick a probability distribution q to start with. Given that q covers the integers, the distributions p and q cannot be disjoint, so there exists at least 1 number that you could pick that would give you a winning probability greater than a half. Averaging over the distribution q we get a smaller, yet still non-zero, improvement over the random guessing.

Update: DJP sends in his solution. Let f(i) be a monotonic map from the integers to the real interval [0,1]. Say "High" with probability f(a) and "Low" with probability (1-f(a)) after the challenger reveals his number a.

My solution is only a special case of DJP's, with f(i) = 0 for all negative i and f(i) = 1 for all non-negative i. The justification is more or less the same, and is left as an exercise to the reader.

---

Note on the name "Cover's Game" (Aug 20, 2006 9pm): spurred on by DJP, I did some research into why the game is so called. Apparently it is named after Thomas Cover, professor of Electrical Engineering and Statistics at Stanford, who introduced the game in relation to his idea of "Universal Portfolios". The idea is basically that we have an investor, faced with a large selection of stocks. With limited knowledge of the stocks, we want to choose an investment algorithm that gives the best returns (in the minimax sense...). To learn more about this, cf:

• Cover, Thomas M, "Universal Portfolios", Math. Finance 1 (1991) no. 1, p 1-29
• Cover, Thomas M and Ordentlich, Erik, "Universal portfolios with side information", IEEE Trans. Inform. Theory 42 (1996), no. 2, p 348-363
• Vovk, V and Watkins C, "Universal Portfolio Selection" in Proceedings of the eleventh annual conference on Computational learning theory, p 12-23; Madison, Wisconsin, United States