A Nifty Bar Bet

These days in foundations of quantum theory, there's a lot of interest in so-called "pseudo-telepathic games." Quantum systems can be correlated in ways that don't make much sense classically, and the correlations have some apparently spooky consequences. We can describe guessing games that pit teams with quantum resources against teams who only have classical resources. The quantum teams are virtually certain to do better than the classical teams. It appears that the members of the quantum teams are somehow able to communicate telepathically, even though there actually isn't any way to use the quantum resources to send messages -- hence the name pseudo-telepathy.

The quantum games are fuel for another post. What I want to do here is describe a purely classical game that has something of the feel of a quantum pseudo-telepathic game, but where there's a surprising and pretty strategy for doing much better by classical means than you'd expect. The game isn't my invention (I think it's due to Sandu Popescu, but I need to check that) but it's very nifty.

Suppose you and your friend are given a challenge. Each of you will flip a fair coin 20 times. But you're separated and you aren't allowed to communicate. Each of you records each flip, and each time you flip, you try to predict what your friend got. For example: on flip #7, you get Heads. You predict that your friend got Tails. Your friend, meanwhile, records her flip #7 and makes her own prediction about you. The two of you succeed on a round if each of you predicts the other's outcome correctly.

How often would you expect to succeed? Suppose that neither you nor your friend is telepathic. Each time you flip, you guess what happened to your friend's coin. On each flip, your chance of guessing correctly is 1/2, as is your friend's. Since neither your coin nor your guess has any influence on her, the chance that you're both right is 1/2 x 1/2 = 1/4. Put another way, there are four equally likely guesses about the pair of results, but only one of them can be right.

Suppose that you and your friend are paired against another team. The winner of the contest is the team with the largest number of successful rounds. You play 100 rounds. Your team succeeds on about 25. The other team succeeds about 50 times.

Are they cheating? Are they telepathic? No need for any of that. There's a simple strategy that's guaranteed to give them twice as many successes in the long run. Here's a break in the page to let you see if you can figure out how.








Call the other team members Alice and Bob. On each round, Alice predicts that Bob got what she got; Bob does exactly the same thing. This raises the chance of success on each round from 1/4 to 1/2. How so?

Think about the cases where you and your friend each flip Heads. If you're guessing randomly, then among those cases, we expect to see each of the following predictions equally often:

You predict H, she predicts H
You predict H, she predicts T
You predict T, she predicts H
You predict T, she predicts T.

If both of you got Heads, then only one out of four of these joint guesses is correct. The same story goes for the other cases: you get Heads, she gets Tails, and so on.

Now consider Alice and Bob. There are four possible outcomes for their actual flip, and in each case, the actual outcome fixes the prediction:

Outcome Prediction
Alice: H, Bob: H ------Alice: "Bob got H", Bob: "Alice got H"
Alice: H, Bob: T ------Alice: "Bob got H", Bob: "Alice got T"
Alice: T, Bob: H ------Alice: "Bob got T", Bob: "Alice got H"
Alice: T, Bob: T ------Alice: "Bob got T", Bob: "Alice got T"

The cases in bold are the ones where Alice and Bob are both right. As you can see, it happens half the time. The strategy is guaranteed to be right every time Alice and Bob get the same outcome, and guaranteed to be wrong every time they get different outcomes. But "same outcome" and "different outcomes" are equally likely.

That's the trick. There's a strategy, but no cheating. It's surprising, and yet it's straightforward.

Those with only moderate curiosity can stop there. But for the more phwonkish (philosophically wonkish), we can say a bit more.

First, you can easily see that another strategy works just as well: guess that your partner got the opposite of what you got. You're guaranteed to be right when the results are opposite, and guaranteed to be wrong otherwise. If you were trying to avoid suspicion in a bar, you might have a pre-arranged deal for mixing the two strategies: go "same" on even-numbered rounds and "different" on the rest, for example. If you're playing enough rounds, you can even mix things up with a few random guesses. To make it simple, suppose that you go "same" on odd-numbered rounds and guess randomly on the rest. In 100 rounds, you'd expect to succeed on about 25 out of the fifty where you used the "guess the same" strategy and on about 12 to 13 of the other rounds. You'd still expect to succeed on about 37 rounds, while your opponents, unless they're smart, are likely to succeed on only 25. More relaxed strategies like this are harder to spot, and will still make it very likely that you'll outscore your opponents.

It's also interesting that there's a nearby game that you can guarantee not to lose (though you might draw.) Suppose that you "succeed" on a round when you and your partner are both wrong. Then if your opponents play randomly, they'll "succeed" 3/4 of the time. But suppose you always predict that your partner got what you get, and she always predicts that you don't get what she gets. If you actually both get heads. you'll predict her result correctly, but she'll get yours wrong. If you get head and she gets tails, you'll get her result wrong even though she gets yours right. And so on. You'll never both be right.

Finally, the idea here can be generalized. Suppose that you and your partner are each rolling a fair die. Then if you guess randomly, you'll both make a correct prediction only 1 time in 36. But if you each predict that your partner got what you got, then you'll be right every time the results really are the same. That will happen, on average, 1 time out of 6. Playing against a team of random guessers, you would have a big advantage over a large number of rounds.

Whether it would be smart to walk into a bar and look for suckers is another matter, of course. What's intriguing is that our combinatoric and probabilistic intuitions aren't really very good. Even very simple situations can provide us with delightful surprises.