Skip to main content
4 of 9
improved bounds, mentioned Will Sawin's proof idea
Tobias Fritz
  • 6.4k
  • 2
  • 27
  • 52

In this answer, I will derive the following improved bounds: $$0.367 \approx \frac{208}{567} \le \sup_\mu \mathbf{P}[X_1 + X_2 + X_3 < 2 X_4] \le \frac{7}{15} \approx 0.467.$$ In the remarks at the end, I will sketch how this derivation is an instance of a general algorithm producing a sequence of tight bounds applicable to all problems of this type. (Unfortunately the algorithm has too high complexity to be useful in practice, at least in the form that I will describe.)


Lower bound: Start with $\mu = \frac{1}{2} \delta_0 + \frac{1}{6} \delta_5 + \frac{1}{3} \delta_9$. Then some tedious calculations show that $$\mathbf{P}[X_1 + X_2 + X_3 < 2 X_4] = \frac{26}{81}, \qquad \mathbf{P}[X_1 + X_2 + X_3 = 2 X_4] = \frac{1}{8}.$$ Therefore applying the trick from jlewk's answer achieves $$\mathbf{P}[X_1 + X_2 + X_3 < 2 X_4] = \frac{26/81}{1-1/8} = \frac{208}{567}.$$ I have no doubt that further tweaking can still improve this value.


Upper bound: Let's consider an extension of the argument for the upper bound of $\frac{1}{2}$ given in the question. To this end, consider independent $X_1, \dots, X_6 \sim \mu$. Then their joint distribution is invariant under permutations, and in particular the probability $$\mathbf{P}[X_i + X_j + X_k < 2 X_\ell]$$ is independent of the choice of the indices as long as these are all distinct. I will refer to the $X_i + X_j + X_k < 2 X_\ell$ as "versions" of the original inequality, so there are $6 \cdot \binom{5}{3} = 60$ versions.

If $N$ denotes the maximal number of versions that can be jointly satisfied, then I claim that $\frac{N}{60}$ is an upper bound on the original problem. Indeed considering whether each inequality holds defines a distribution on $\{0,1\}^{60}$, where the probability of each sequence with more than $N$ many $1$s is zero. The claim then follows by the fact that the symmetry group acts transitively on the components of $\{0,1\}^{60}$.

Thus the remaining problem is to prove $N \le 28$, since we then get the upper bound $\frac{28}{60} = \frac{7}{15}$. To this end, it helps to assume without loss of generality that $X_1 \le \dots \le X_6$, and consider which quadruples $(i,j,k,\ell)$ can appear among the valid versions of the inequality. Let us assume $i < j < k$ without loss of generality and keep these fixed. Then $\ell > j$ is necessary, since otherwise we get $X_j \ge X_\ell$ and therefore $$X_i + X_j + X_k \ge X_i + 2 X_\ell \ge 2 X_\ell,$$ which is exactly the negation of the desired inequality. From $\ell > j$ it follows that the number of possible $\ell$'s for a given triple $(i,j,k)$ is at most $5 - j$. Enumerating thus the number of possible $\ell$ for each of the $20$ triples $(i,j,k)$ results in $30$ candidate quadruples $(i,j,k,\ell)$. In other words, we get $30$ version which are such that any jointly feasible set of versions is a subset of this one, modulo permutations of variables.

In order to conclude $N \le 29$, it is thus enough to show that these $30$ inequalities are jointly infeasible in combination with $0 \le X_1 \le \dots \le X_6$. In fact, this holds already for the subsystem $$X_1 + X_2 + X_6 < 2 X_3$$ $$X_1 + X_3 + X_6 < 2 X_4$$ $$X_3 + X_4 + X_5 < 2 X_6$$ Indeed using $X_4 \le X_5$ and adding these inequalities produces the desired contradiction by $X_1, X_2 \ge 0$.

Finally we show $N \le 28$. This is a simple extension of the previous argument, since in each case at least one additional version of the inequality must fail: if $X_1 + X_2 + X_6 < 2 X_3$ fails, then so does $X_1 + X_2 + X_6 < 2 X_4$, and similarly in the other two cases.

Although the proof of the upper bound is now concluded, it's worth noting that $N = 28$ is achieved by $$\tag{2} X_1 = X_2 = X_3 = 0, \qquad X_4 = 5, \qquad X_5 = X_6 = 9.$$ Therefore the current upper bound is the optimal bound derivable by the method used here (with 6 variables).


Additional thoughts:

  1. The determination of $N$ has been a problem in extremal combinatorics. In general, determining the maximal number of jointly satisfiable inequalities is known as the maximum feasible subsystem problem, and it is NP-hard in general. This suggests that also determining $N$ in other cases may be challenging. It feels similar to hypergraph Turán problems.

  2. It's not hard to see that the proof of the upper bound is an instance of a general method for deriving upper bounds on such probabilities based on exchangeability: for $X_1, \ldots, X_n$, consider how many versions of the inequality can be satisfied jointly. The fraction of these is then an upper bound on the desired quantity.
    I believe that these upper bounds are tight as $n \to \infty$, and Will Sawin has given a simple proof of this in the comments for the case at hand. I'd expect the method and its proof of correctness to apply generally to all analogous problems of the form $\sup_\mu \mathbf{P}[\sum_{i=1}^k a_i X_i > 0]$.

  3. The idea behind Will's proof is to construct a distribution $\mu$ from the solution of a maximal feasible subsystem as the uniform distribution on the values of the variables and to use this as a lower bound. This idea is also how I had found the $\mu = \frac{1}{2} \delta_0 + \frac{1}{6} \delta_5 + \frac{1}{3} \delta_9$ which appears in the new lower bound: this distribution is given by the relative frequencies in (2).

Tobias Fritz
  • 6.4k
  • 2
  • 27
  • 52