[math-fun] Intransitive dice re-tossed
Does anyone know if there is a recent summary of all that's known about intransitive dice? Searching on MathSciNet doesn't seem to get me very far. Suppose you have a cyclically ordered sequence of n dice, each of which has s sides, and each of which beats the (cyclically) next one with the same probability p > 1/2. I believe I saw some reference that claims p <= 3/4 under all circumstances; maybe another that sharpened this to p <= sqrt(5 - 1)/2 = .618.... --Dan
I don't know anything more about intransitive dice than I did when math-fun last discussed this, in a discussion Bill Gosper kicked off in Nov. 2001. But at the time I did hunt down Marting Gardner's piece on Efron's dice, which included the quote:
It has been proved, Efron writes, that 2/3 is the greatest possible advantage that can be achieved with four dice. For three sets of numbers the maximum advantage is .618, but this cannot be obtained with dice beacause the sets must have more than six numbers. If more than four sets are used (numbers to be randomly selected within each set), the possible advantage approaches a limit of 3/4 as the number of sets increases.
So that at least answers your "I believe I saw..." question. The original Efron dice, 004444/111555/222266/333333, do attain that 2/3 bound for four dice, by the way. I did a little literature searching last time. Aside from the Dec 1970 SciAm column, there's a May 1976 Math magazine column by Richard Tenney and Caxton Foster, and there's a paper of Zalman Usiskin from 1976: "Max-min probabilities in the voting paradox." (Ann. Math. Statist. 35, 1964, pp 857--862.) This paper proves the bound of 3/4 when the number of independent random variables goes to infinity. Perhaps a reasonable way to find anything written on the subject recently is to search for articles which refer to the above... --Michael Kleber On 4/5/06, dasimov@earthlink.net <dasimov@earthlink.net> wrote:
Does anyone know if there is a recent summary of all that's known about intransitive dice?
Searching on MathSciNet doesn't seem to get me very far.
Suppose you have a cyclically ordered sequence of n dice, each of which has s sides, and each of which beats the (cyclically) next one with the same probability p > 1/2.
I believe I saw some reference that claims p <= 3/4 under all circumstances; maybe another that sharpened this to p <= sqrt(5 - 1)/2 = .618....
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Suppose you have a cyclically ordered sequence of n dice, each of which has s sides, and each of which beats the (cyclically) next one with the same probability p > 1/2.
I believe I saw some reference that claims p <= 3/4 under all circumstances; maybe another that sharpened this to p <= sqrt(5 - 1)/2 = .618....
Focusing on the combinatorics rather than the numbers: for a given set of dice, consider the directed graph with the dice as vertices and an edge a->b iff a beats b. What graphs are possible? (Is it every directed graph that never has a->b->a, at least if you allow the dice to have more than 6 faces?) [after a little googling] Any tournament (i.e., directed graph where for any a,b exactly one of a->b and b->a is present) can be realized in this way if you have enough faces. The first step is to find a set of permutations of the vertices such that a->b iff a precedes b in more than half the permutations. (There's a paper by McGarvey that proves this is always possible. I haven't read it. And another by Erdos and Moser that proves you only need O(n/logn) permutations, which will lead to O(n/logn) faces on each die. I haven't read that either.) So, let those permutations be a11 a12 a13 ... a1n a21 a22 a23 ... a2n ... ak1 ak2 ak3 ... akn (k permutations of n elements; n, remember, is the number of dice). Give the dice as many faces as there are permutations; and suppose bij is the rank of j in the i'th permutation; label the dice b11 b21 ... bk1 <-- die 1 b12 b22 ... bk2 <-- die 2 ... b1n b2n ... bkn <-- die n. Then die p beats die q iff b*p > b*q usually; i.e., if the rank of p > the rank of q in most of the permutations; i.e., if p comes after q in most of the permutations. Hmm, we have our arrows the wrong way round, but that's boring :-). So, the answer is indeed that everything is possible (well, except that I don't know about which edges you can arrange to be absent because neither of two dice beats the other) if you have as many faces as you like. There seem to be some theorems about which graphs are realizable with a given number of permutations, but nothing much like a complete answer yet. -- g
participants (3)
-
dasimov＠earthlink.net -
Gareth McCaughan -
Michael Kleber