Intransitive dice VII — aiming for further results

Gowers's Weblog 2018-03-10

While Polymath13 has (barring a mistake that we have not noticed) led to an interesting and clearly publishable result, there are some obvious follow-up questions that we would be wrong not to try to answer before finishing the project, especially as some of them seem to be either essentially solved or promisingly close to a solution. The ones I myself have focused on are the following.

Is it true that if two random elements $A$ and $B$ of $[n]^n$ are chosen, then $A$ beats $B$ with very high probability if it has a sum that is significantly larger? (Here “significantly larger” should mean larger by $f(n)$ for some function $f(n)=o(n^{3/2})$ — note that the standard deviation of the sum has order $n^{3/2}$ , so the idea is that this condition should be satisfied one way or the other with probability $1-o(1)$ ).
Is it true that the stronger conjecture, which is equivalent (given what we now know) to the statement that for almost all pairs $(A,B)$ of random dice, the event that $A$ beats a random die $C$ has almost no correlation with the event that $B$ beats $C$ , is false?
Can the proof of the result obtained so far be modified to show a similar result for the multisets model?

The status of these three questions, as I see it, is that the first is basically solved — I shall try to justify this claim later in the post, for the second there is a promising approach that will I think lead to a solution — again I shall try to back up this assertion, and while the third feels as though it shouldn’t be impossibly difficult, we have so far made very little progress on it, apart from experimental evidence that suggests that all the results should be similar to those for the balanced sequences model. [Added after finishing the post: I may possibly have made significant progress on the third question as a result of writing this post, but I haven’t checked carefully.]

The strength of a die depends strongly on the sum of its faces.

Let $A=(a_1,\dots,a_n)$ and $B=(b_1,\dots,b_n)$ be elements of $[n]^n$ chosen uniformly and independently at random. I shall now show that the average of

$|\{(i,j):a_i>b_j\}|-|\{(i,j):a_i<b_j\}|-\sum_ia_i+\sum_jb_j$

is zero, and that the probability that this quantity differs from its average by substantially more than $n\log n$ is very small. Since typically the modulus of $\sum_ia_i-\sum_jb_j$ has order $n^{3/2}$ , it follows that whether or not $A$ beats $B$ is almost always determined by which has the bigger sum.

As in the proof of the main theorem, it is convenient to define the functions

$f_A(j)=|\{i:a_i<j\}|+\frac 12|\{i:a_i=j\}|$

and

$g_A(j)=f_A(j)-j+\frac 12$ .

Then

$\sum_jf_A(b_j)=\sum_{i,j}\mathbf 1_{a_i<b_j}+\frac 12\sum_{i,j}\mathbf 1_{a_i=b_j}$ ,

from which it follows that $B$ beats $A$ if and only if $\sum_jf_A(b_j)>n^2/2$ . Note also that

$\sum_jg_A(b_j)=\sum_jf_A(b_j)-\sum_jb_j+\frac n2$ .

If we choose $A$ purely at random from $[n]^n$ , then the expectation of $f_A(j)$ is $j-1/2$ , and Chernoff’s bounds imply that the probability that there exists $j$ with $|g_A(j)|=|f_A(j)-j+1/2|\geq C\sqrt{n\log n}$ is, for suitable $C$ at most $n^{-10}$ . Let us now fix some $A$ for which there is no such $j$ , but keep $B$ as a purely random element of $[n]^n$ .

Then $\sum_jg_A(b_j)$ is a sum of $n$ independent random variables, each with maximum at most $C\sqrt{n\log n}$ . The expectation of this sum is $\sum_jg_A(j)=\sum_jf_A(j)-n^2/2$ .

But

$\sum_jf_A(j)=\sum_{i,j}\mathbf 1_{a_i<j}+\frac 12\sum_{i,j}\mathbf 1_{a_i=j}$

$=\sum_i(n-a_i)+\frac n2=n^2+\frac n2-\sum_ia_i$ ,

so the expectation of $\sum_jg_A(b_j)$ is $n(n+1)/2-\sum_ia_i$ .

By standard probabilistic estimates for sums of independent random variables, with probability at least $1-n^{-10}$ the difference between $\sum_jg_A(b_j)$ and its expectation $\sum_jf_A(j)-n^2/2$ is at most $Cn\log n$ . Writing this out, we have

$|\sum_jf_A(b_j)-\sum_jb_j+\frac n2-n(n+1)/2+\sum_ia_i|\leq Cn\log n$ ,

which works out as

$|\sum_jf_A(b_j)-\frac {n^2}2-\sum_jb_j+\sum_ia_i|\leq Cn\log n$ .

Therefore, if $\sum_ia_i>\sum_jb_j+Cn\log n$ , it follows that with high probability $\sum_jf_A(b_j)<n^2/2$ , which implies that $A$ beats $B$ , and if $\sum_jb_j>\sum_ia_i+Cn\log n$ , then with high probability $B$ beats $A$ . But one or other of these two cases almost always happens, since the standard deviations of $\sum_ia_i$ and $\sum_jb_j$ are of order $n^{3/2}$ . So almost always the die that wins is the one with the bigger sum, as claimed. And since “has a bigger sum than” is a transitive relation, we get transitivity almost all the time.

Why the strong conjecture looks false

As I mentioned, the experimental evidence seems to suggest that the strong conjecture is false. But there is also the outline of an argument that points in the same direction. I’m going to be very sketchy about it, and I don’t expect all the details to be straightforward. (In particular, it looks to me as though the argument will be harder than the argument in the previous section.)

The basic idea comes from a comment of Thomas Budzinski. It is to base a proof on the following structure.

With probability bounded away from zero, two random dice $A$ and $B$ are “close”.
If $A$ and $B$ are two fixed dice that are close to each other and $C$ is random, then the events “ $A$ beats $C$ ” and “ $B$ beats $C$ ” are positively correlated.

Here is how I would imagine going about defining “close”. First of all, note that the function $g_A$ is somewhat like a random walk that is constrained to start and end at zero. There are results that show that random walks have a positive probability of never deviating very far from the origin — at most half a standard deviation, say — so something like the following idea for proving the first step (remaining agnostic for the time being about the precise definition of “close”). We choose some fixed positive integer $k$ and let $x_1<\dots<x_k$ be integers evenly spread through the interval $\{1,2,\dots,n\}$ . Then we argue — and this should be very straightforward — that with probability bounded away from zero, the values of $f_A(x_i)$ and $f_B(x_i)$ are close to each other, where here I mean that the difference is at most some small (but fixed) fraction of a standard deviation.

If that holds, it should also be the case, since the intervals between $x_{i-1}$ and $x_i$ are short, that $f_A$ and $f_B$ are uniformly close with positive probability.

I’m not quite sure whether proving the second part would require the local central limit theorem in the paper or whether it would be an easier argument that could just use the fact that since $f_A$ and $f_B$ are close, the sums $\sum_jf_A(c_j)$ and $\sum_jf_B(c_j)$ are almost certainly close too. Thomas Budzinski sketches an argument of the first kind, and my guess is that that is indeed needed. But either way, I think it ought to be possible to prove something like this.

What about the multisets model?

We haven’t thought about this too hard, but there is a very general approach that looks to me promising. However, it depends on something happening that should be either quite easy to establish or not true, and at the moment I haven’t worked out which, and as far as I know neither has anyone else.

The difficulty is that while we still know in the multisets model that $A$ beats $B$ if and only if $\sum_jf_A(b_j)<n^2/2$ (since this depends just on the dice and not on the model that is used to generate them randomly), it is less easy to get traction on the sum because it isn’t obvious how to express it as a sum of independent random variables.

Of course, we had that difficulty with the balanced-sequences model too, but there we got round the problem by considering purely random sequences $B$ and conditioning on their sum, having established that certain events held with sufficiently high probability for the conditioning not to stop them holding with high probability.

But with the multisets model, there isn’t an obvious way to obtain the distribution over random dice $B$ by choosing $b_1,\dots,b_n$ independently (according to some distribution) and conditioning on some suitable event. (A quick thought here is that it would be enough if we could approximate the distribution of $B$ in such a way, provided the approximation was good enough. The obvious distribution to take on each $b_i$ is the marginal distribution of that $b_i$ in the multisets model, and the obvious conditioning would then be on the sum, but it is far from clear to me whether that works.)

A somewhat different approach that I have not got far with myself is to use the standard one-to-one correspondence between increasing sequences of length $n$ taken from $[n]$ and subsets of $[2n-1]$ of size $n$ . (Given such a sequence $(a_1,\dots,a_n)$ one takes the subset $\{a_1,a_2+1,\dots,a_n+n-1\}$ , and given a subset $S=\{s_1,\dots,s_n\}\subset[2n-1]$ , where the $s_i$ are written in increasing order, one takes the multiset of all values $s_i-i+1$ , with multiplicity.) Somehow a subset of $[2n-1]$ of size $n$ feels closer to a bunch of independent random variables. For example, we could model it by choosing each element with probability $n/(2n-1)$ and conditioning on the number of elements being exactly $n$ , which will happen with non-tiny probability.

Actually, now that I’m writing this, I’m coming to think that I may have accidentally got closer to a solution. The reason is that earlier I was using a holes-and-pegs approach to defining the bijection between multisets and subsets, whereas with this approach, which I had wrongly assumed was essentially the same, there is a nice correspondence between the elements of the multiset and the elements of the set. So I suddenly feel more optimistic that the approach for balanced sequences can be adapted to the multisets model.

I’ll end this post on that optimistic note: no doubt it won’t be long before I run up against some harsh reality.