Hacker News new | past | comments | ask | show | jobs | submit login
Nontransitive dice (wikipedia.org)
194 points by adenadel on April 29, 2017 | hide | past | favorite | 42 comments



You can purchase a set of non-transitive dice here: https://mathsgear.co.uk/products/non-transitive-grime-dice (I am not affiliated in any way with this store)

These particular ones are fun because the winning order reverses if you double the count of dice. i.e. A beats B beats C beats A, but 2 As lose to 2 Bs lose to 2 Cs lose to 2 As.

I wrote up a blog a while back that explores the various possibilities and chains using Mathematica: http://latkin.org/blog/2015/01/16/non-transitive-grime-dice-...


This reminded me of Penney's Game (https://en.wikipedia.org/wiki/Penney's_game).


Freaky! I find that result even more surprising than the intransitive dice. Thanks for posting.


You might find the result less surprising after you solve a riddle by Martin Gardner:

> A young man lives in Manhattan near a subway express station. He has two girlfriends, one in Brooklyn, one in the Bronx. To visit the girl in Brooklyn, he takes a train on the downtown side of the platform; to visit the girl in the Bronx, he takes a train on the uptown side of the same platform. Since he likes both girls equally well, he simply takes the first train that comes along. In this way, he lets chance determine whether he rides to the Bronx or to Brooklyn. The young man reaches the subway platform at a random moment each Saturday afternoon. Brooklyn and Bronx trains arrive at the station equally often—every 10 minutes. Yet for some obscure reason he finds himself spending most of his time with the girl in Brooklyn: in fact on the average he goes there 9 times out of 10. Can you think of a good reason why the odds so heavily favor Brooklyn?

The idea shows up again in the Elevator paradox, which has a delightful article on Wikipedia: https://en.wikipedia.org/wiki/Elevator_paradox


I see an immediate solution to that riddle and it matches the idea of the Wikipedia page you link. But I don't see any connection to Penney's game. Can you explain?


The operative words in the rules of both riddles are "appears first".


Yup, Penney's game is surprising because at first glance the probabilities of two sequences of the same length are unrelated. But if more than half of the sequences overlap, then one sequence will tend to arrive before the other. As the proportion of overlap tends to 100%, Player B has a 2:1 advantage over Player A: https://i.imgur.com/eKujwrK.png


Unfortunately people tend to think this game is unfair if you get to choose second all the time.


I find nontransitive dice to be a clear demonstration of the effects of premature rounding. The nontransitivity is only possible because, after each iteration, the result is rounded to a victory for one die. If the totals were summed over time, they could clearly be ranked by expected value.

You can see this result in other places, also. It's especially visible in sports, for example, or in the stock market.


Negative. Non-transitive dice work even when the expected value of each die is the same. The first example in the Wikipedia article exhibits this:

   Die A has sides 2, 2, 4, 4, 9, 9.
   Die B has sides 1, 1, 6, 6, 8, 8.
   Die C has sides 3, 3, 5, 5, 7, 7.
The expected value of each die is 5, yet A beats B, B beats C, and C beats A. Other examples in the article have sets of transitive dice where the expected value is not the same; transitivity still holds.


You two are speaking past each other. CydeWes is using EV in the "first moment" sense. Amalcon is using EV in the "expected utility" sense. E.g. consider rock-paper-scissors. The expected utility of rock is 1/2. But since rock is represented non-numerically, each event has no first moment.


I'm confused, because this reads to me like exactly what I was trying to say, but you seem to be disagreeing with me. Could you clarify?

In the game with rounding, A beats B, B beats C, C beats A. In the game without rounding, where totals are summed, they are evenly matched and it's down to chance. That's exactly the effect I was referring to.


There are many sets of non-transitive dice where the average is not the same though (I should have used one of those examples). Here's one:

   A: 4, 4, 4, 4, 0, 0 (avg: 8/3)
   B: 3, 3, 3, 3, 3, 3 (avg: 9/3)
   C: 6, 6, 2, 2, 2, 2 (avg: 10/3)
   D: 5, 5, 5, 1, 1, 1 (avg: 9/3)
There's no reason that the average values need to be the same to have non-transitive dice. To modify the original three to have the same winning properties, but radically different averages, just imagine doing this:

   Die A has sides 2, 2, 4, 4, 99, 99.
   Die B has sides 1, 1, 6, 6, 8, 8.
   Die C has sides 3, 3, 5, 5, 7, 7.
The expected value of an individual die roll doesn't play into it at all.


It doesn't play into this game because of the rounding. Again, you seem to be attempting to disagree with me, by echoing the exact same things I just said.


That's because the second person that disagrees with the same thing is expected to be more right on average.


In normal dice play expected value doesn't come into play. But if we were to do a long term sum of results (like amalcon proposed) then it expected value would come into play, and would determine the winner.

This illustrates the difference between premature rounding (normal dice play) and non premature rounding (long term summing of results).


But a long term sum of results is a completely different game. It doesn't matter what's on the face of the dice at all; all that matters is the average value per roll. It's not dice anymore! And you've defined the winning condition completely differently!

I also don't understand how normal dice play counts as "premature rounding". It's just how playing dice works -- you compare the numbers versus each other.


"But a long term sum of results is a completely different game."

That's exactly the point! A naive intuition about dice is that they have a single probabilistic long-term score. E.g. 6-sided die is 3.5. So if one dice beats another, it should be transitive (the intuition goes). It's the summation (implied by averaging over time) that leads to the naive intuition.


Maybe this description of the two games might help clarify the link.

Game 1: Player 1 chooses a dice, then player 2 chooses a dice. They both roll numbers, say a and b. Then player 2 gives player 1 (a - b) dollars.

Game 2: Player 1 chooses a dice, then player 2 chooses a dice. They both roll numbers, say a and b. Then player 2 gives player 1 (a - b > 0 ? 1 : -1) dollars.

You can kind of squint and see that game 2 is the same as game 1 just with (a - b) "rounded" to either 1 or -1.


You seem to be using "rounding" to mean "comparing the exact, unmodified results of individual rolls", which is probably the source of the confusion because that doesn't really correspond to any common definition of the word "rounding".


One way to interpret OP's 'rounding' concept is that in a round of a dice game, the winner's score is rounded up to 1, and the loser's score rounded down to 0. If, on the other hand, each turn each player got a fractional score between 0 and 1 (without 'rounding'), then that would represent a 'truer' evaluation of the dice.

The best way I can think of to allocate a fractional score to each die player is to sum all the dice rolled, and give each player their roll divided by the sum. So if players rolled 2 and 5, one player would get 2/7 and the other 5/7 - instead of rounding the scores to 0 and 1.

Note that to calculate the EV for a die under this scheme, you have to calculate it versus a particular opposing die, so it would produce a different EV for the transitive A/B/C dice in different combinations.

Perhaps that's what the OP was trying to suggest?


More or less this, except with a simpler way of allocating fractional scores: simply divide the value rolled on that die by the largest such value on any of the dice in the set (or, equivalently, round to either 0 or largest-such-value and skip the division step).


The "rounding" he's describing is the "beating" you're describing. If the game you play is just long term sums of values then expected value is all you need, and in your example they're all even.


See my other example. Most sets of non-transitive dice do not have the same expected value, and the expected value doesn't tell you which one will win. To use an extreme example, take two dice, (2 2 2 2 2 2) and (1 1 1 1 1 999). The average value of the first die is much smaller than that of the second, yet it wins 5/6ths of the time.


The non-transitivity of Rock-Scissors-Paper is easy to understand, partly because it's so simple, but mostly because you're likely never played outside the usual rules, even if adding Lizard-Spock.

Non-transitive dice screw with the 'nature' of dice that most of us expect. To get to the mathematical intuition, one may have to get past a deeply-ingrained feeling that something about these dice just isn't right. That's a big part of the fun.


I think the numeric and gambling aspect helps too. If you're used to probability, you probably start thinking about expected value automatically in these situations, but it isn't the case that the die with the highest expected value wins most of the time against a die with lower expected value. (e.g. 2,2,2,2,2,2s vs 1,1,1,1,1,100).


Seasoned gamblers count "outs" (winning outcomes), convert to "hand odds" (out:loss ratio), then weigh hand odds against "pot odds" (weigh expected profit vs investment).


Mean EV doesn't work because the dice have different variances? Trying to wrap my head around the rationale here


Variance isn't the best lens here, better to look at the distributions. It's also a discrete problem, so EV isn't as precise as looking at all the possible combinations.


Variance describes distribution...

Discreteness is another layer. What are the exact defining characteristics of this problem though? You could take two dice 1-2-3-4-5-6 and 2-3-4-5-6-7 and the typical mean EV calculation would work fine...

1-2-3-4-5-7 and 2-3-4-5-6-8 have different variances but are probably not intransitive (haven't checked the math) since they are translations of each other

I'm just thinking out loud here and trying to narrow it down...maybe someone reading wants to help me :)


Variance does describe the distribution, but not well enough, in this case. It reduces the vector of possibilities to a scalar, and hides the most important aspect, the non-transitivity. Numbers have transitive comparisons, so there's essentially no way a scalar value _could_ capture that in any straightforward way. Basically, abandon all single-value summaries. They'll do you no good in understanding this phenomenon. But the detailed analysis isn't too complicated, so it's okay.


EV of what? The faces of dice cannot be added together, except in a very formal sense.


Brought to my attention from Timothy Gowers' blog

https://gowers.wordpress.com/2017/04/28/a-potential-new-poly...


Does anyone have any board game recommendations that take advantage of this dice configuration?


Good question. It seems this non-transitive games are suited to trick people, but can you make skill-based game out of the mechanics?


This video is where I first learned of nontransitive dice:

http://www.youtube.com/watch?v=u4XNL-uo520

Grime dice! And James Grime seems like such a fun, happy, charismatic guy, I'd love to have a beer with him and play dice with him, even knowing the outcome. :)


Or if you have a 3D printer, you can print out your own.

http://www.thingiverse.com/thing:17782

I made it a while back. There's 3 sets. Efron's dice, Miwin's dice, and Grime's dice.


OMG, I just finished working through an example of this with my student, like literally minutes ago, and look what Hacker News brings me ...


Well what were the odds of that, eh?


It was a little difficult to believe that such a property (dice being transient) was possible. But a little simulation in python 2 (using the Wikipedia example) makes everything crystal:

https://gist.github.com/spapas/9b29e1dec752b85fc1d6ad660af7f...


Reminds me of political system bugs where a candidate might win only by transitivity.


Quantum Rock/Paper/Scissors :)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: