Monday, August 3, 2009

Simulation: Oppie's dice

I found a puzzle that can be simulated easily and had what was for me a very surprising answer. The puzzle concerns Einstein's famous comment that "God does not throw dice," as explored here by John Tierney of the NY Times. The trouble starts when God shows up and explains that actually he likes throwing dice.

The problem statement is this: we are to make 3 unusual dice bearing the numbers 1..18. Oppie designs the dice, Einstein picks first, and Oppie then has his choice of the remaining two. Is it possible for Oppie to design dice such that there is no choice Einstein can make that will win (most high scores) in a long-run trial?

Since I've been reading about statistics of discrete distributions I immediately thought of the expected value E for a given die. If X is a random variable that is the result of throwing a die, then E{X}, the expected value of X and the mean of the distribution, is Σ xi p(i). So...I thought that the problem could be recast this way: is it possible to design dice such that the E{X} is equal for either the top two choices, or all the same. I figured the best that Oppie could do is break even.

Simulation immediately showed that there are lots of designs with this property.

However, there is a problem. Just because two dice each have the same E{X}, it does not follow that there is no winner and loser in the long term. The answer devised by one of Tierney's readers is to make dice that are like rock-paper-scissors, where D1 beats D2 and D2 beats D3, but D3 beats D1. One such design is:

d1:  1 6 8 10 15 17
d2: 2 4 9 11 13 18
d3: 3 5 7 12 14 16


You see that for the triplets 1..3, 4..6 and so on, d1 gets first the lowest, then the highest value, and then the middle. The E{X} for each die is the same (57/6). I wrote a simulation that shows the result, and it is at the end of the post, but we can also enumerate the problem easily. For each pair of dice, we consider each face of the first die of the pair in turn, then count the number of wins considering all the faces of the second die.

d1:  1 6 8 10 15 17
d2: 2 4 9 11 13 18
0 + 2 + 2 + 3 + 5 + 5 = 17 / 36
d2 beats d1

d2: 2 4 9 11 13 18
d3: 3 5 7 12 14 16
0 + 1 + 3 + 3 + 4 + 6 = 17 / 36
d3 beats d2

d3: 3 5 7 12 14 16
d1: 1 6 8 10 15 17
1 + 1 + 2 + 4 + 4 + 5 = 17 / 36
d1 beats d3


import random

L1 = [1, 6, 8, 10, 15, 17]
L2 = [2, 4, 9, 11, 13, 18]
L3 = [3, 5, 7, 12, 14, 16]

t = [L1,L2,L3]

for i in range(3):
for j in range(i):
d1 = t[i]
d2 = t[j]
print d1, sum(d1)
print d2, sum(d2)
N = 0
for k in range(10000):
c1 = random.choice(d1)
c2 = random.choice(d2)
if c1 > c2: N += 1
print 'd1 won', N, 'times'


[2, 4, 9, 11, 13, 18] 57
[1, 6, 8, 10, 15, 17] 57
d1 won 5270 times
[3, 5, 7, 12, 14, 16] 57
[1, 6, 8, 10, 15, 17] 57
d1 won 4780 times
[3, 5, 7, 12, 14, 16] 57
[2, 4, 9, 11, 13, 18] 57
d1 won 5292 times