Non-transitive Dice

Non-transitive Dice

Established: August 26, 2011

Overview

Embracing Uncertainty

Scientists have worked for decades to try to create intelligence in computers. Traditional approaches relied on hand-crafted solutions and had limited applicability. New artificial intelligence techniques developed at Microsoft and other institutions around the world are based on computers that can learn for themselves by analysing large sets of data.

The key to learning from examples is to recognise that real-world data is full of complexity, ambiguity, and uncertainty. Computers can be programmed to handle these challenges by using a branch of mathematics called probability theory. By embracing the mathematics of uncertainty, we are able to create machines that can learn from data and apply these to problems ranging from medical data analysis to the recognition of objects in images.

To learn more about Microsoft’s work in artificial intelligence, visit aka.ms/artificialintelligence

About the dice

First of all, let us examine the dice in detail. Here we have ‘flattened’ the dice to show the numbers on each of the faces.

dice_illustrationWe see that the choice of numbers is unusual. But in all other respects these are normal, fair dice. If we pick two of the dice and roll them, we can see which comes up with the higher number. We will say that the die with the higher number is the winner. Notice that each of the numbers 0, 1, 2, 3, 4, 5, and 6 appears on only one of the dice, which means that when we roll one die against another, there can never be a draw.

First, suppose you roll the orange and yellow dice. Two thirds of the time the yellow die will come up with a higher number than the orange die. We say that the probability that the yellow die will win is two thirds. If we make a large number of such rolls and keep track of which die wins, then there is a very high chance that the yellow die will win more often than the orange die.

Likewise, two thirds of the time the blue die will win against the yellow die, and two thirds of the time the green die will win against the blue die. So, yellow beats orange, blue beats yellow, and green beats blue.

It therefore seems as if the green die has the highest chance of winning and the orange die has the lowest. But now for the surprise: if you roll the green die with the orange die, then two thirds of the time it is the orange die that will win!

These are known as non-transitive dice. Transitive means that if A beats B and B beats C then A beats C. We see that these dice do not have this property. One way to visualise this is to arrange the dice in a circle, such that each die beats the previous one.

This is rather like the game of “rock, paper, scissors” in which scissors beats paper, and rock beats scissors, but paper beats rock.

A simple game

You can use this non-transitive property to play a game with a friend. Invite them to examine the dice and then to select any one of them. Without telling them the secret, you now select the next die in the sequence, and then you make, say, 9 rolls against your friend, and keep note of how many times each of you rolls the higher number. Over a sequence of 9 rolls it is very likely that you will roll a higher number more often than your friend.

How the dice work

dice_diagram-rgbLook first at the orange die, and notice that it has four copies of the number 2 and two copies of the number 6. Two-thirds of the time, when we roll the orange die it will give a 2, and one third of the time it will give a 6. Therefore, if we roll the orange die against the yellow die (which always gives a 3), the yellow die will, on average, win two-thirds of the time, and will lose one-third of the time. You can repeat this game several times, each time allowing your friend to choose their die first.

Now look at the blue die, and notice that it has four copies of the number 4, and two copies of the number 0. When we roll it against the yellow die, it will therefore give a 4 two thirds of the time, in which case it wins, and a 0 one-third of the time, in which case it loses.

Now suppose we roll the green die against the blue die. The green die has three copies of the number 1 and three copies of the number 5. To work out the probability that the green die will win we first note that there is a probability of 1/2 that the green die will give a 5, in which case it is certain to win against the blue die. Likewise, there is a probability of 1/2 that the green die will give a 1, in which case there is a probability of 1/3 that it will win. The overall probability that the green die will win is then given by multiplying the probabilities:

Finally, consider the probability of the orange die winning against the green die. There is a probability of 1/3 that the orange die will produce a 6, in which case it is certain that the orange die will win. There is similarly a probability of 2/3 that the orange die will produce a 2 in which case there is a 1/2 chance that the orange die will win. The overall probability of the orange die winning is again obtained by multiplying the probabilities:

Further information

Warren Buffett once challenged Bill Gates to a game of dice. “Buffett suggested that each of them choose one of the dice, then discard the other two. They would bet on who would roll the higher number most often. Buffett offered to let Gates pick his die first. This suggestion instantly aroused Gates’ curiosity. He asked to examine the dice, after which he demanded that Buffett choose first.” Buffett was using a set of non-transitive dice!