Leave and Let Dice

Imagine a game with six players, numbered #1 to #6, and one six-sided die. Someone rolls the die and the player who matches the number wins the game. That is, if the die rolls 1, player #1 wins; if the die rolls 2, player #2 wins; and so on. With a fair die, this is a fair game, because each player has exactly a 1/6 chance of winning. You could call it a simultaneous game, because all players are playing at once. It has one rule:

• If the die rolls n, then player #n wins.

Now try a different game with six players and one die. Player #1 rolls the die. If he gets 1, he wins the game. If not, then he leaves the game and player #2 rolls the die. If he gets 2, he wins the game. If not, then he leaves the game and player #3 rolls the die. And so on. You could call this a sequential game, because the players are playing in sequence. It has two rules:

• If player #n rolls n on the die, then he wins.
• If player #n doesn’t roll n, then player n+1 rolls the die.

Is it a fair game? No, definitely not. Player #1 has the best chance of winning. 1/6 or 16.6% of the time he rolls 1 and wins the game. 5/6 of the time, he rolls 2, 3, 4, 5 or 6 and passes the die to player #2. Now player #2 has a 1/6 chance of rolling a 2 and winning. But he has the opportunity to roll the die only 5/6 of the time, so his chance of winning the game is 1/6 * 5/6 = 5/36 = 13.8%. However, if player #2 rolls a 1, 3, 4, 5 or 6, then he loses and player #3 rolls the die. But player #3 has that opportunity only 5/6 * 5/6 = 25/36 of the time. So his chance of winning is 1/6 * 25/36 = 11.57%. And so on.

To put it another way, if the six players play 46656 = 6^6 games under the sequential rules, then on average:

• Player #1 wins 7776 games
• Player #2 wins 6480 games
• Player #3 wins 5400 games
• Player #4 wins 4500 games
• Player #5 wins 3750 games
• Player #6 wins 3125 games
• 15625 games end without a winner.

In other words, player #1 is 20% more likely to win than player #2, 44% more likely than player #3, 72.8% more likely than player #4, 107% more likely than player #5, and 148.8% more likely than player #6. Furthermore, player #2 is 20% more likely to win than player #3, 44% more likely than player #4, 72.8% more likely than player #5, and so on.

But there is a simple way to make the sequential game perfectly fair, so long as it’s played with a fair die. At least, I’ve thought of a simple way, but there might be more than one.




To make the sequential game fair, you add an extra rule:

1. If player #n rolls n on the die, he wins the game.
2. If player #n rolls a number greater than n, he loses and the die passes to player n+1.
3. If player #n rolls a number less than n, then he rolls again.

Let’s run through a possible game to see that it’s fair. Player #1 rolls first. He has a 1/6 chance of rolling a 1 and winning the game. However, 5/6 of the time he loses and passes the die to player #2. If player #2 rolls a 1, he rolls again. In other words, player #2 is effectively playing with a five-sided die, because all rolls of 1 are ignored. Therefore, he has a 1/5 chance of winning the game at that stage.

But hold on: a 1/5 chance of winning is better than a 1/6 chance, which is what player #1 had. So how is the game fair? Well, note the qualifying phrase at the end of the previous paragraph: at that stage. The game doesn’t always reach that stage, because if player #1 rolls a 1, the game is over. Player #2 rolls only if player doesn’t roll 1, which is 5/6 of the time. Therefore player #2’s chance of winning is really 1/5 * 5/6 = 5/30 = 1/6.

However, 4/5 of the time player #2 rolls a 3, 4, 5 or 6 and the die passes to player #3. If player #3 rolls a 1 or 2, he rolls again. In other words, player #3 is effectively playing with a four-sided die, because all rolls of 1 and 2 are ignored. Therefore, he has a 1/4 chance of winning the game at that stage.

A 1/4 chance of winning is better than a 1/5 chance and a 1/6 chance, but the same reasoning applies as before. Player #3 rolls the die only 5/6 * 4/5 = 20/30 = 2/3 of the time, so his chance of winning is really 1/4 * 2/3 = 2/12 = 1/6.

However, 3/4 of the time player #2 rolls a 4, 5 or 6 and the die passes to player #4. If player #4 rolls a 1, 2 or 3, he rolls again. In other words, player #4 is effectively playing with a three-sided die, because all rolls of 1, 2 and 3 are ignored. Therefore, he has a 1/3 chance of winning the game at that stage. 1/3 > 1/4 > 1/5 > 1/6, but the same reasoning applies as before. Player #4 rolls the die only 5/6 * 4/5 * 3/4 = 60/120 = 1/2 of the time, so his chance of winning is really 1/3 * 1/2 = 1/6.

And so on. If the die reaches player #5 and he gets a 1, 2, 3 or 4, then he rolls again. He is effectively rolling with a two-sided die, so his chance of winning is 1/2 * 5/6 * 4/5 * 3/4 * 2/3 = 120/720 = 1/6. If player #5 rolls a 6, he loses and the die passes to player #6. But there’s no need for player #6 to roll the die, because he’s bound to win. He rolls again if he gets a 1, 2, 3, 4 or 5, so eventually he must get a 6 and win the game. If player #5 loses, then player #6 automatically wins.

It’s obvious that this form of the game will get slower as more players drop out, because later players will be rolling again more often. To speed the game up, you can refine the rules like this:

1. If Player #1 rolls a 1, he wins the game. Otherwise…
2. If player #2 rolls a 2, he wins the game. If he rolls a 1, he rolls again. Otherwise…
3. Player #3 rolls twice and adds his scores. If the total is 3, 4 or 5, he wins the game. Otherwise…
4. Player #4 rolls once. If he gets 1 or 2, he wins the game. Otherwise…
5. Player #5 rolls once. If he gets 1, 2 or 3, he wins the game. Otherwise…
6. Player #6 wins the game.

Only player #2 might have to roll more than twice. Player #3 has to roll twice because he needs a way to get a 1/4 chance of winning. If you roll two dice, there are:

• Two ways of getting a total of 3: roll #1 is 1 and roll #2 is 2, or vice versa.
• Three ways of getting a total of 4 = 1+3, 3+1, 2+2.
• Four ways of getting 5 = 1+4, 4+1, 2+3, 3+2.

This means player #3 has 2 + 3 + 4 = 9 ways of winning. But there are thirty-six ways of rolling one die twice. Therefore player #3 has a 9/36 = 1/4 chance of winning. Here are the thirty-six ways of rolling one die twice, with asterisks marking the winning totals for player #3:

01. (1,1)
02. (1,2)*
03. (2,1)*
04. (1,3)*
05. (3,1)*
06. (1,4)*
07. (4,1)*
08. (1,5)
09. (5,1)
10. (1,6)
11. (6,1)
12. (2,2)*
13. (2,3)*
14. (3,2)*
15. (2,4)
16. (4,2)
17. (2,5)
18. (5,2)
19. (2,6)
20. (6,2)
21. (3,3)
22. (3,4)
23. (4,3)
24. (3,5)
25. (5,3)
26. (3,6)
27. (6,3)
28. (4,4)
29. (4,5)
30. (5,4)
31. (4,6)
32. (6,4)
33. (5,5)
34. (5,6)
35. (6,5)
36. (6,6)

Advertisements

Dice in the Witch House

“Who could associate mathematics with horror?”

John Buchan answered that question in “Space” (1911), long before H.P. Lovecraft wrote masterpieces like “The Call of Cthulhu” (1926) and “Dreams in the Witchhouse” (1933). But Lovecraft’s use of mathematics is central to his genius. So is his recognition of both the importance and the strangeness of mathematics. Weird fiction and maths go together very well.

But weird fiction is about the intrusion or eruption of the Other into the everyday. Maths can teach you that the everyday is already Other. In short, reality is weird — the World is a Witch House. Let’s start with a situation that isn’t obviously weird. Suppose you had three six-sided dice, A, B and C, each with different set of numbers, like this:

Die A = (1, 2, 3, 6, 6, 6)
Die B = (1, 2, 3, 4, 6, 6)
Die C = (1, 2, 3, 4, 5, 6)

If the dice are fair, i.e. each face has an equal chance of appearing, then it’s clear that, on average, die A will beat both die B and die C, while die B will beat die C. The reasoning is simple: if die A beats die B and die B beats die C, then surely die A will beat die C. It’s a transitive relationship: If Jack is taller than Jim and Jim is taller than John, then Jack is taller than John.

Now try another set of dice with different arrangements of digits:

Die A = (1, 2, 2, 5, 6, 6)
Die B = (1, 1, 4, 5, 5, 5)
Die C = (3, 3, 3, 3, 4, 6)

If you roll the dice, on average die A beats die B and die B beats die C. Clearly, then, die A will also beat die C. Or will it? In fact, it doesn’t: the dice are what is called non-transitive. Die A beats die B and die B beats die C, but die C beats die A.

But how does that work? To see a simpler example of non-transitivity, try a simpler set of random-number generators. Suppose you have a triangle with a short rod passing through its centre at right angles to the plane of the triangle. Now imagine numbering the edges of the triangles (1, 2, 3) and throwing it repeatedly so that it spins in the air before landing on a flat surface. It should be obvious that it will come to rest with one edge facing downward and that each edge has a 1/3 chance of landing like that.

In other words, you could use such a spiked triangle as a random-number generator — you could call it a “trie”, plural “trice”. Examine the set of three trice below. You’ll find that they have the same paradoxical property as the second set of six-sided dice above. Trie A beats trie B, trie B beats trie C, but trie C beats trie A:

Trie A = (1, 5, 8)
Trie B = (3, 4, 7)
Trie C = (2, 3, 9)

When you throw two of the trice, there are nine possible outcomes, because each of three edges on one trie can be matched with three possible edges on the other. The results look like this:

Trie A beats Trie B 5/9ths of the time.
Trie B beats Trie C 5/9ths of the time.
Trie C beats Trie A 5/9ths of the time.

To see how this works, here are the results throw-by-throw:

Trie A = (1, 5, 8)
Trie B = (3, 4, 7)

When Trie A rolls 1…

…and Trie B rolls 3, Trie B wins (Trie A has won 0 out of 1)
…and Trie B rolls 4, Trie B wins (0 out of 2)
…and Trie B rolls 7, Trie B wins (0 out of 3)

When Trie A rolls 5…

…and Trie B rolls 3, Trie A wins (1/4)
…and Trie B rolls 4, Trie A wins (2/5)
…and Trie B rolls 7, Trie B wins (2/6)

When Trie A rolls 8…

…and Trie B rolls 3, Trie A wins (3/7)
…and Trie B rolls 4, Trie A wins (4/8)
…and Trie B rolls 7, Trie A wins (5/9)


Trie B = (3, 4, 7)
Trie C = (2, 3, 9)

When Trie B rolls 3…

…and Trie C rolls 2, Trie B wins (Trie B has won 1 out of 1)
…and Trie C rolls 3, it’s a draw (1 out of 2)
…and Trie C rolls 9, Trie C wins (1 out of 3)

When Trie B rolls 4…

…and Trie C rolls 2, Trie B wins (2/4)
…and Trie C rolls 3, Trie B wins (3/5)
…and Trie C rolls 9, Trie C wins (3/6)

When Trie B rolls 7…

…and Trie C rolls 2, Trie B wins (4/7)
…and Trie C rolls 3, Trie B wins (5/8)
…and Trie C rolls 9, Trie C wins (5/9)


Trie C = (2, 3, 9)
Trie A = (1, 5, 8)

When Trie C rolls 2…

…and Trie A rolls 1, Trie C wins (Trie C has won 1 out of 1)
…and Trie A rolls 5, Trie A wins (1 out of 2)
…and Trie A rolls 8, Trie A wins (1 out of 3)

When Trie C rolls 3…

…and Trie A rolls 1, Trie C wins (2/4)
…and Trie A rolls 5, Trie A wins (2/5)
…and Trie A rolls 8, Trie A wins (2/6)

When Trie C rolls 9…

…and Trie A rolls 1, Trie C wins (3/7)
…and Trie A rolls 5, Trie C wins (4/8)
…and Trie A rolls 8, Trie C wins (5/9)


The same reasoning can be applied to the six-sided non-transitive dice, but there are 36 possible outcomes when two of the dice are thrown against each other, so I won’t list them.

Die A = (1, 2, 2, 5, 6, 6)
Die B = (1, 1, 4, 5, 5, 5)
Die C = (3, 3, 3, 3, 4, 6)


Elsewhere other-posted:

At the Mountains of Mathness
Simpson’s Paradox — a simple situation with a very weird outcome

Live and Let Dice

How many ways are there to die? The answer is actually five, if by “die” you mean “roll a die” and by “rolled die” you mean “Platonic polyhedron”. The Platonic polyhedra are the solid shapes in which each polygonal face and each vertex (meeting-point of the edges) are the same. There are surprisingly few. Search as long and as far as you like: you’ll find only five of them in this or any other universe. The standard cubic die is the most familiar: each of its six faces is square and each of its eight vertices is the meeting-point of three edges. The other four Platonic polyhedra are the tetrahedron, with four triangular faces and four vertices; the octahedron, with eight triangular faces and six vertices; the dodecahedron, with twelve pentagonal faces and twenty vertices; and the icosahedron, with twenty triangular faces and twelve vertices. Note the symmetries of face- and vertex-number: the dodecahedron can be created inside the icosahedron, and vice versa. Similarly, the cube, or hexahedron, can be created inside the octahedron, and vice versa. The tetrahedron is self-spawning and pairs itself. Plato wrote about these shapes in his Timaeus (c. 360 B.C.) and based a mathemystical cosmology on them, which is why they are called the Platonic polyhedra.

An animated gif of a tetrahedron

Tetrahedron


An animated gif of a hexahedron

Hexahedron

An animated gif of an octahedron

Octahedron


An animated gif of a dodecahedron

Dodecahedron

An animated gif of an icosahedron

Icosahedron

They make good dice because they have no preferred way to fall: each face has the same relationship with the other faces and the centre of gravity, so no face is likelier to land uppermost. Or downmost, in the case of the tetrahedron, which is why it is the basis of the caltrop. This is a spiked weapon, used for many centuries, that always lands with a sharp point pointing upwards, ready to wound the feet of men and horses or damage tyres and tracks. The other four Platonic polyhedra don’t have a particular role in warfare, as far as I know, but all five might have a role in jurisprudence and might raise an interesting question about probability. Suppose, in some strange Tycholatric, or fortune-worshipping, nation, that one face of each Platonic die represents death. A criminal convicted of a serious offence has to choose one of the five dice. The die is then rolled f times, or as many times as it has faces. If the death-face is rolled, the criminal is executed; if not, he is imprisoned for life.

The question is: Which die should he choose to minimize, or maximize, his chance of getting the death-face? Or doesn’t it matter? After all, for each die, the odds of rolling the death-face are 1/f and the die is rolled f times. Each face of the tetrahedron has a 1/4 chance of being chosen, but the tetrahedron is rolled only four times. For the icosahedron, it’s a much smaller 1/20 chance, but the die is rolled twenty times. Well, it does matter which die is chosen. To see which offers the best odds, you have to raise the odds of not getting the death-face to the power of f, like this:

3/4 x 3/4 x 3/4 x 3/4 = 3/4 ^4 = 27/256 = 0·316…

5/6 ^6 = 15,625 / 46,656 = 0·335…

7/8 ^8 = 5,764,801 / 16,777,216 = 0·344…

11/12 ^12 = 3,138,428,376,721 / 8,916,100,448,256 = 0·352…

19/20 ^20 = 37,589,973,457,545,958,193,355,601 / 104,857,600,000,000,000,000,000,000 = 0·358…

Those represent the odds of avoiding the death-face. Criminals who want to avoid execution should choose the icosahedron. For the odds of rolling the death-face, simply subtract the avoidance-odds from 1, like this:

1 – 3/4 ^4 = 0·684…

1 – 5/6 ^6 = 0·665…

1 – 7/8 ^8 = 0·656…

1 – 11/12 ^12 = 0·648…

1 – 19/20 ^20 = 0·642…

So criminals who prefer execution to life-imprisonment should choose the tetrahedron. If the Tycholatric nation offers freedom to every criminal who rolls the same face of the die f times, then the tetrahedron is also clearly best. The odds of rolling a single specified face f times are 1/f ^f:

1/4 x 1/4 x 1/4 x 1/4 = 1/4^4 = 1 / 256

1/6^6 = 1 / 46,656

1/8^8 = 1 / 16,777,216

1/12^12 = 1 / 8,916,100,448,256

1/20^20 = 1 / 104,857,600,000,000,000,000,000,000

But there are f faces on each polyhedron, so the odds of rolling any face f times are 1/f ^(f-1). On average, of every sixty-four (256/4) criminals who choose to roll the tetrahedron, one will roll the same face four times and be reprieved. If a hundred criminals face the death-penalty each year and all choose to roll the tetrahedron, one criminal will be reprieved roughly every eight months. But if all criminals choose to roll the icosahedron and they have been rolling since the Big Bang, just under fourteen billion years ago, it is very, very, very unlikely that any have yet been reprieved.