The Coin Toss Paradox

You are here

Alice and Bob are two fictional characters who love to play games with a mathematical bent. Here, for example, is one game they play: They toss coins and figure their odds of winning. What are their chances, for example, if Bob tosses a coin and Alice has to guess which side is up, and then Alice flips a coin and Bob has to guess, and they play as a team, so that both must be correct to win?

Prof. Irit Dinur
“There are many variations on this game,” says Prof. Irit Dinur of the Weizmann Institute's Computer Science and Applied Mathematics Department. “The different versions and their mathematical solutions give us insight into how information is shared in the real world, in computing, in different branches of mathematics and even in the world of quantum mechanics and quantum communication.” Dinur and her colleagues recently used one variation on this game to reveal how it might be played under “quantum” rules.These rules are very relevant to those who hope to use the strange properties of quantum mechanics to construct new ways of using information – for example in quantum communication, a technology that is already under development today.

In the coin-toss game, says Dinur, one might think that after both had flipped and guessed they would have a 25% chance of winning the game, since each had a 50% chance of guessing correctly. But there is a clever strategy that Bob and Alice can use: If each guesses that the other has flipped exactly the same as their own coin flip, they raise their odds to 50%.  

Now imagine Bob and Alice continue playing the game – they must guess correctly every time to win. Are there more clever tricks they can use to increase their chances of winning? The answer, sadly, is no. As they continue to flip coins, their odds decrease round by round: Mathematical calculations reveal that in all cases, as the game is repeated, the chance of winning quickly approaches zero.  

Changing the rules

When Dinur and her colleagues changed the rules yet again, entering the world of quantum mechanics, things become more complicated.

Alice and Bob’s information was now in the shape of quantum particles; to understand the game, one must understand a few basic principles of quantum mechanics. First, there is superposition: A quantum particle can be in more than one state at a time. But when it is observed or measured, it “collapses” into a single state. So the possible information held by each superimposed particle can be much greater than “yes” or “no.”

Alice and Bob’s particles were also entangled: When two particles are entangled in a quantum setup, they can be placed at a distance from each other, but their states remain in perfect sync, so that any change in the state of one results in an instantaneous change in the state of the other.

Both of these ideas were proposed in the early 20th century, and Einstein was famously opposed to the concept of entanglement, calling it “spooky action at a distance.” A paper he coauthored in 1935 presented the “EPR paradox,” which suggested that, because information cannot travel between the particles faster than the speed of light, there must either be some hidden variables controlling the process, or else the outcome is already “known” before the measurement is performed. Today, entanglement has been proven experimentally, and Einstein’s hidden variables did not pan out. But the paradox remains: How do two particles “share information,” coordinating their states with no time lag?  
Game plans
In the entanglement game, if Alice measures her superimposed quantum bit, collapsing it into a particular state, then Bob’s entangled particle must immediately assume a corresponding state. So entangling bits of information could be seen as cheating. Would Alice and Bob win every time, the results seemingly predetermined, or would the game still be subject to other, less spooky, laws of play? In other words, how would the conditions of the EPR paradox apply to the game?

Dinur and her colleagues showed, mathematically, that a game based on entangled bits of information will eventually follow the pattern of the other games: As the rounds are repeated, the chances of winning will drop significantly. Entanglement may give them some advantage in the beginning, as Bob now has a piece of information about Alice’s knowledge. But, like the coin toss, Alice’s information will still be random: Measuring will collapse her quantum system to a particular state, but she will not be able to control or predict what that state will be. Thus while the odds for each individual round will be better, the pattern will remain the same, moving toward zero as rounds are added to the game. In other words, entanglement would only be a partial cheat, at best, and the EPR paradox is not quite the paradox it seemed.  

If quantum communication becomes a reality, Alice and Bob will be able to use it to ensure encryption – for example, to detect any interference in messages sent from one to the other. Although the technology is still far in the future, it will rely on today’s mathematics to set the rules and the limits on its operation.