Apologies, it’s on my to-do list but unfortunately so are a lot of other unfinished papers …

]]>Wonderful, I am very much looking forward.

]]>I’ve been so busy on other projects that I haven’t had time to touch this one. But I’m coming to think that we need to let go and put roughly the existing draft (tidied up a little) on the arXiv so that if anybody else wants to do some of the follow-up problems then they can do so.

An alternative, if anyone is interested, would be for me to start a new post with a serious discussion of some of these follow-up problems. I would be particularly interested to disprove rigorously the strong conjecture that the “beats” tournament is quasirandom. I think it’s a doable problem.

Perhaps the best option would be to do both — put a draft on the arXiv and try to get a discussion going of the follow-up problem.

]]>Also such sets have been designed that â€śfor any three players, there is a fourth that beats all of themâ€ť. Yet â€śthe optimal graph is unknown for the 5 player game and aboveâ€ť http://www.mathpuzzle.com/MAA/39-Tournament%20Dice/mathgames_07_11_05.html

Interestingly–can increasing complexity of dice construction for N player games be related to The P versus NP problem https://en.wikipedia.org/wiki/P_versus_NP_problem?

Can answering this question be aimed for further results?

A lot of interesting pieces came up in the last discussion, and it felt like things where starting to fit into more general pictures. On top of that, you asked some interesting questions. Unfortunately I got busy with other things, and now would need to really sit down and immerse myself to build up some intuition again. I would like to return to this. Your last question is even something that could just be played with numerically to explore with it.

Finding the “parameter” that gives a total order for the improper dice feels within reach. Especially since this parameter must collapse to the same value (or nearly same value) for the proper dice. There is hope that this may even clarify what is going on with the loss of intransitivity with the “rescaled” dice as well.

Your “dream” idea of figuring out a rough simple structure for the intransitive dice (like a circular parameter, or multiple parameters for some higher dimension closed surface) is very alluring. If there is no total order, and it isn’t a random tournament, it just begs to at least try looking for that structure.

To pull out the general structure of the tournament I thought it might help to somehow separate out the piece that allows deviations from perfect balance of beating/losing to dice, thus leaving behind a cleaner/simpler structure. I started playing with it a bit, and have the following in some of my notes:

For the multiset or sequence dice, because of the presence of the involution (let’s denote it n(A) for die A), we can separate any die into a “symmetric” and “asymmetric” piece:

A = (n(A)+A)/2 + (n(A)-A)/2

Counting over all dice, the symmetric part will beat exactly as many dice as it loses to. The asymmetric part will tie all asymmetric parts. So the only thing that can lead to a die deviating from beating exactly as many dice as it loses to, is its asymmetric part compared to the distribution of the symmetric parts of all dice.

The symmetric part has a permutation freedom which satisfies the constraints that the asym part does not. I was hoping that following this could lead to a better view of the general landscape that gives us our tournament. I thought maybe your dream scenario would fit in where we could roughly separate out a “many permutations” structure, and also a kind of “radial” parameter that would ruin the intransitivity if it weren’t for all dice being so “close” to the center on average. So the “radial” parameter would come from the asym part of the die. And ideally this “closeness” concept would coincide nicely with why the strong conjecture fails, and the “radial” parameter would roughly give the positive correlation.

This felt like an interesting possibility for the tournament landscape, but I couldn’t hit upon the right questions to ask or definitions to use to test and explore further.

I regret to say, I never did any tests of your last idea regarding the number of i where a_i > b_i.

Maybe it would be worthwhile to have another post summarizing the remaining questions and how they may fit together with our current understanding. Then gauge how much interest remains in this project. If interest doesn’t return, it would be sad to see the pieces left incomplete, but I guess the open questions could be left as such in the paper to inspire further work.

]]>Good question. I’m definitely intending to turn the write-up I posted on this blog into an article, but I have been too busy to do it recently, especially as there are a couple of questions I would very much like us to answer before we do so. But maybe it would be better to post the results we have so far as an arXiv preprint and then add to that preprint if we obtain the further results I’d like to obtain. (I’m referring particularly to the result, which I think is within reach, that the more general conjecture that the “beats” tournament is quasirandom is false.)

Does anyone else who participated have a view about what we should do?

]]>An initial thought is that if A and B are typical dice, then and grow approximately like , so unless and are close (which usually means as a fraction of ), if , then and are both less than and . This means that usually if then , in which case the pairs and cancel out. So it makes some sense to focus on the “exceptional” pairs for which this cancellation does not happen.

Suppose, then, that and let us think about what needs to happen if we are to obtain both the inequalities and . A simple remark is that , since we know that (as I am writing the sequence elements in non-decreasing order). It therefore suffices to have the inequality . If we now fix , we see that the number of that satisfy this condition is “the time it takes to catch up with .

We can model the growth of and continuously in our minds, and we now see that if the gradient of is small after , then we get a big contribution to the number of pairs with , which is very helpful to . Conversely, if the gradient is large, we get only a small contribution.

This thought can be used to construct pairs of dice with the same sum where one beats the other quite easily. Take for example the dice

and

.

Most of the time, the graph of A sits just above the graph of B, but just occasionally B makes a big jump just before A does. This means that the graph of B has a tendency to be flat just after a point where A is bigger, whereas the graph of A has a tendency to be steep just after a (rare) point where B is bigger. So we expect A to win easily, and indeed it does: there are 144 pairs, and the numbers of beaten by the go

,

which adds up to 84, which is significantly bigger than 72.

These considerations suggest that there could be a significant correlation between which die wins and the number of such that , though I would be surprised if there was agreement with probability .

]]>Following on from the last paragraph of the previous comment, I now think it would be very nice to get a heuristic understanding (at least) of that rescaled-uniform model. A natural question is the following. Let be a random die chosen according to that model. Let be the average value of before the rescaling. Does correlate with the proportion of dice beaten by ?

We might expect the answer to be yes for the following reason: if is less than 1/2, then after rescaling, the values below 1/2 are slightly “squashed”, whereas the values above 1/2 are slightly “stretched”. But as P. Peng suggests above, a face does not get extra credit for beating another face by a large margin, so in some sense large values are a “waste of resources”. So one might expect (but this argument is so vague as not to be very reliable) at least a weak positive correlation between and the strength of the die. This is something else that would be interesting to test experimentally.

The dream for this model would still be to find a simple statistic that predicts which die wins. Such a statistic couldn’t take values in a totally ordered set (so some simple one-dimensional parameter wouldn’t do, for example), because that would imply transitivity with probability 1-o(1), which seems not to apply. But one could still hope for a map that takes each die to a point in some tournament with a very simple structure, in such a way that the direction of the edge between and predicts which of and wins. And then the problem would be reduced to understanding the tournament.

Come to think of it, that dream is one that could also be entertained for the balanced sequence model. We know that transitivity occurs with the frequency one gets in a random tournament, but we suspect that the tournament is not quasirandom. These two statements are consistent, because all we need for the transitivity statement is that almost all vertices have roughly the same out-degree as in-degree. So now we can ask what the structure of the tournament is like? Perhaps once you condition on the sum of the faces, there is some other statistic — again, I would hope for a tournament with a nice simple structure — that predicts with high accuracy which of two dice will win.

I don’t yet have a good definition of “nice simple structure”, but an example of the kind of thing I mean is a circle where there is an arrow from to if is less than half way round in a clockwise direction from and from to if is more than half way round. (If is exactly half way round, then the direction of the arrow is chosen arbitrarily.) It is unlikely that we can associate with each die in the balanced-sequence model a point in the circle in such a way that this particular tournament predicts which die wins, but perhaps some higher-dimensional (but still low-dimensional) variant works. If we could do something like this, then we would have a wonderfully precise understanding of the Mann-Whitney/Wilcoxon test for this model.

]]>Of course, the natural follow-up question if the conjecture in my previous comment is correct is whether if we condition on the improper dice taking the expected value for that statistic we get intransitivity with probability 1/4+o(1) again. If that turned out to be the case, then it would probably be a special case of a much more general principle, which would say that the following picture holds for a wide class of models.

1. For each positive integer , let be the probability that a given face of a random die from the model takes the value . Let be the cumulative distribution: that is, , which is the probability that the face takes value at most .

2. Given a die , define to be . Then, with probability , beats if and only if .

3. If we fix a value and restrict attention to dice for which (subject to some condition that ensures that the proportion of dice that satisfy this condition is not too small — for some models we might have to replace the condition by ), then the probability that a random triple of dice is transitive is 1/4+o(1).

If we could prove something like this, it would be a significant step forward in our understanding of the intransitivity phenomenon.

Having said that, there is also a suggestion in the paper that for at least one model we get intermediate behaviour, where knowing that beats and beats makes it more likely that beats , but with conditional probability bounded away from 1. The model in question is where you choose values independently and uniformly from and then rescale so that the average becomes . For a full understanding, it would be good to understand this too.

]]>I have a guess about a statistic that I think will predict the winner in the sequence model for nonstandard dice. (That is, a random die is a random sequence of positive integers that add up to .)

Let , let , and for each positive integer , let be the probability of choosing with the geometric distribution with parameter : that is, . (This is sometimes called the *shifted* geometric distribution.)

In the usual sequence model, the sum of a sequence can be equivalently defined as the number of pairs such that , which is closely related to how well the die does when it is up against the standard die. And this sum is the right statistic to choose. Note that a random face of the standard die is uniformly distributed in .

After the heuristic idea in my previous comment, it seems a rather plausible guess that the right statistic to choose for nonstandard dice is how well a die does against not the uniform distribution but the geometric distribution. So that statistic I propose is

.

Another way of thinking of this is that the sum of a sequence is (up to a factor ) the sum of the values of the cumulative distribution function at the numbers , where the distribution is uniform on . Now I want to take the sum of the values of the cumulative distribution function of the geometric distribution.

Since generating a random improper die is easy, it should be easy to test this hypothesis experimentally. If it checks out, then I’ll sit down and try to prove it.

]]>I’ve just realized that the sequence model of improper dice isn’t as hard as I thought. If we line up points with gaps between them, then there’s a one-to-one correspondence between sequences of numbers that add up to , and ways of choosing gaps (that mark the point where one number finishes and the next number starts). So the total number of improper dice is , which is reasonably close to . When the numbers are constrained to be at most , then the number of sequences is at most , but because the sum of a random sequence has standard deviation about , it’s in fact more like . A crude estimate of is . Since , this is exponentially bigger than the number of sequences in the more constrained model. So I think the answer to your last question is yes.

I think we can also say something about the typical shape of an improper die. Suppose that instead of selecting exactly gaps, we select each gap independently with probability . The distribution should be similar. But with this model, the expected gap length has a geometrical distribution with mean approximately (because is about ). So it looks to me as though at least crudely speaking an improper die is what you get when you replace the uniform distribution on by a geometric distribution with the same mean.

]]>I looked into the improper dice (mean still constrained to (n+1)/2, but values are now only constrained to be more than 0).

If you take any proper die and choose an entry greater than 1, and decrease it by one, then compared to the standard die (looking at the possible roll combinations) it will win one less and lose one more. And for any die, if you choose an entry = n, and increase it by one, it will win only one more compared to the standard die. Increasing any value beyond n+1 does not give any added benefit when comparing to the standard die. Therefore, the standard die will beat any improper die with a value greater than n. It beats any “truly” improper die if you will.

From some numerical tests on small sided dice, if we rank all the dice according to how many dice it beats – how many it loses to, the standard die is at the top or at least in the top few dice. At the bottom is the die that is all ones except a single face, as that loses to everything.

Basically, since the “beats” relationship doesn’t care how much a die wins by in a particular roll, deviating from proper dice is only “wasting” pips on a lopsided distribution of value. For this reason, the median does roughly correlate with the order of the improper dice. As does the standard deviation. I would need to look at larger dice to understand the trend better, but I’d guess currently that these will only end up being weak correlations. There is likely a better predictor.

In the proper die scenario the standard die tied everything and was in some sense at the ‘center’ of the dice. In the improper dice, the standard die is now near the top of the ranking, and the die that loses to all other dice is in a reasonable sense the ‘furthest’ from the standard die. So likely there is a measure of ‘distance’ from the standard die that strongly correlates with the ranking (and so strongly predicts if two die beat each other). I think the median would only weakly capture this at best as n gets larger.

If we look at the sequence model of improper dice, what is the probability that at least one value is greater than n? Is it possible that the standard die beats 1 – o(n) fraction of the improper dice?

]]>Ah, I’ve just looked at the original paper and it does look likely from the evidence presented there that the probability of intransitivity tends to zero for this model (though that was for multisets — it might be interesting to see if the same holds for sequences).

]]>That’s a great question and something I’d love to see the answer to. Just to clarify the question, when you say “this also appears to become transitive” do you mean that it appears to become transitive with probability or just that there is a positive correlation between the events “A beats B and B beats C” and “A beats C”? If it’s the first, it should be easier to prove, and something I’d either like to have a go at or leave as a tempting open problem in the paper. I’m not sure how to go about analysing the model itself, since it doesn’t seem to be obtainable by some simple conditioning on a sum of independent random variables. On the other hand, I’m pretty sure it (and even more so its continuous counterpart) has been studied a lot, so maybe with a look at the literature we would understand how to prove things about it. Maybe someone reading this can even suggest where to look. (Just to be clear, the distribution I’m interested in is the uniform distribution over the face of the -dimensional simplex consisting of all vectors in with non-negative coordinates that sum to 1.)

I very much doubt that the median plays an important role here, but if transitivity holds with probability it would be a very nice challenge to try to find a simple statistic that predicts which die will win.

]]>For dice where the mean is constrained but we allow values greater than n, this also appears to become transitive. In this case the mean is not a predictor, so some other property might give a summary.

Who knows, maybe the median becomes important. I’m not sure anyone has looked into that yet.

I think the mean may be fairly special here. The argument above shows that for two random dice and with means that differ by a typical amount, the means almost certainly determine which one wins. But then another order statistic will not determine which one wins unless it typically agrees with the mean. My guess (though I haven’t thought about it properly, so I may be wrong) is that there is a probability bounded away from zero that the order of the medians of two random sequences is different from the order of the means. If that guess is correct, then the medians will not predict which die wins.

]]>The reason this is interesting is that ordering of distributions based on for *samples* is the (widely-used) Mann-Whitney/Wilcoxon test. It’s already an advance to know this is typically transitive when the means are different, even under just one generating model for distributions. It would be even more helpful to know if this is just a fact about reasonable dice behaving reasonably or something special about the mean.

]]>A partial sketch of a different approach.

Consider the starting point: instead of dice represented as a vector of values, represent it as a multiplicity vector m_i = number of faces with value i. A scoring function f(A,B), which gives the number of rolls where A beats B – the number of rolls where B beats A, can be represented as a matrix equation A.F.B where F is an antisymmetric matrix. The constraints are now that m_i â‰Ą 0, the sum m_i = n, and sum i m_i = n(n+1)/2. The standard die in this representation (1,1,…,1) ties all dice due to theses constraints. Now in the realm of linear algebra, we can choose a set of changes that when starting from a valid die preserves the sum constraints, and that this set of changes spans the valid dice space. I will call this set the choice of dice “steps”. With a given choice of steps, this also provides a distance measurement: the minimum number of steps from the standard die.

With this setup, we can handle both the sequence and multiset dice model if we allow the notion of a “random die” to involve a possibly non-uniform weight on this representation.

Obviously not all weights will lead to intransitive dice. I believe an appropriate restriction would be to constrain possible weights to one such that it is symmetric to permutation of the multiplicity vector in the following way:

– any multiplicity vectors which are the same up to permutation, and meet the sum constraints, will have the same weight

We can choose steps such that the following are true:

– the set of dice one step away from the standard die have the properties:

– 0 â‰¤ m_i â‰¤ 2

– each die’s multiplicity vector is the same up to permutation

– each die beats exactly as many dice as it loses to

– all proper dice can be reached in O(n) steps

With such a choice of dice steps, and with the above constraints on the weights under consideration, the set of dice a distance 1 away from the standard die have the property:

– for any die, its probability of beating a random die is exactly equal to its probability of losing to a random die

This is a good starting point, and we can build up to any die by adding these steps together. Furthermore the scoring is linear, so knowing how the steps score against each other is sufficient. With multiple steps, due to correlations it is possible for the set of dice to no longer have every die beat exactly half the others. Since the starting point exactly has this symmetry, if the correlation is small enough combined with the weight constraint restricting the amount of asymmetry that can build up, since all dice can be reached in O(n) steps, maybe the asymmetry can’t build up “fast enough” to ruin the property we want for intransitive dice:

– If A is a random die then with probability 1 – o(1), the probability A beats a random die is equal to the probability it loses to a random die + o(1).

Maybe with a stronger constraint on the weights, one could also show that the probability A beats a random die is 1/2 + o(1), so that it also provides that the ties go to zero. But with such wild swings in the weights between sequence and multiset dice, I’m not sure what would likely be the appropriate strengthening which would also give the ties conjecture.

I believe something like this approach may have been discussed before, but part of the issue with this is the m_i â‰Ą 0 constraint. It makes it difficult as not all step combinations are valid. However, if the weight constraint above is sufficient, we can temporarily consider them all valid, and it just happens that for sequences and multiset models, the weight for these dice is 0. This approach therefore allows smoothing out the difficulties with considering all the different representations on the same footing, if indeed that weight constraint is sufficient.

Before I think about this approach any further, is there some simple argument or counter-example which shows steps with these properties + weight constraint is not sufficient?

Currently it appears to fit with our understanding:

– sequence dice model is intransitive

– multiset dice model is intransitive

– the improper dice model is mostly transitive (even though it is “balanced” in that every die has the same expectation value, it doesn’t have the nice choice of steps)

– the un-balanced sequence model (sequence model without the sum constraint) is mostly transitive (again, it doesn’t have the nice choice of steps)

– removing the weights constraint we can just choose weights to force transitivity

I’m hoping something along these lines would work as it unites a lot of the results.

]]>Hence, showing that with macroscopic probability, and are close for every should not be very hard. For a nonconditioned dice, the variables and should be approximately Gaussian with explicit covariances, so for a conditioned dice the are still jointly Gaussian. Proving it properly would require a local limit theorem to handle the double conditioning. But this time, the step distribution is known and very simple, so the proof should be easier than the previous one (or, even better, maybe a general result could be applied).

On the other hand, deducing from here that and are uniformly close does not seem obvious. We would need to show that cannot vary too much in a short interval. A possible way would be to show that is in some sense absolutely continuous with respect to a nonconditioned random walk, and then to use known results about the max of a random walk on a short interval. The absolute continuity also requires a local limit theorem, but this should not be too hard for the same reasons as above.

]]>