Intransitive Dice

About a month ago, Tim Gowers described a fun potential new polymath project. Here is the basic setup:

Say D_1,D_2,D_3 are n-sided dice, i.e. each takes values in \{1,2,..n\}. We say that D_1 beats D_2 if Pr[D1 > D2] > 1/2D_1,D_2,D_3 are intransitive if D_1 beats D_2, D_2 beats D_3 and D_3 beats D_1.

It is somewhat counterintuitive that this can happen and I’ve used this paradox while introducing probability to undergraduates. Now the question:

D_1, D_2, D_3 are randomly chosen. If D_1 beats D_2, D_2 beats D_3, what is the likelihood that D_1 beats D_3? Experiments suggest that the probability tends to 1/2. The goal of the polymath project is to prove this.
The original intransitive dice were invented by Brad Efron (in the Statistics department here at Stanford) and the phenomenon was first noted by Martin Gardner in 1970, but this probability question was discussed only recently, in a paper from 2013.

Since suggesting the problem, the intransitive dice project has quickly gathered steam and is now onto to its 5th post. (If you haven’t followed a polymath project before, each post discusses the current state and has several comments where people collaboratively make progress on the questions being studied. This particular project is one that theoretical computer scientists could easily contribute to and it’s not too late to jump in! At this point, it looks like they are looking for a local central limit theorem for a random walk on \mathbb{Z}^2 with precise bounds on error terms.

Many years ago, I spent some time on the polymath project on the Erdos Discrepancy Problem. It can be exciting, but it is a huge time sink if you get seriously involved. One of the most fun things about participating is getting a glimpse of how different people think and what mental shortcuts they use — this is the sort of stuff you rarely get out of reading papers.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: