Skip to main content
9 of 9
updated outdated statement
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 bounds applicable to all problems of this type, and which converges to the exact value in the limit. (Unfortunately without further tricks, the algorithm has too high complexity to be useful in practice.)


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 = 28$. 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 28$, it is thus enough to find two disjoint subsets of these $30$ inequalities which 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$. A second such subsystem is
$$X_1 + X_2 + X_5 < 2 X_3,$$ $$X_1 + X_4 + X_5 < 2 X_6,$$ $$X_2 + X_3 + X_6 < 2 X_4,$$ $$X_3 + X_4 + X_6 < 2 X_5.$$ Therefore we have $N \le 28$, and this gives an upper bound of $\frac{28}{60} = \frac{7}{15}$.

On the other hand, $N = 28$ is achieved by $$X_1 = X_2 = 0, \qquad X_3 = 4, \qquad X_4 = 5, \qquad X_5 = X_6 = 7.$$


Additional thoughts:

  1. The determination of $N$ is 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, and this is computable at least in theory.
    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 way of thinking 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.

Tobias Fritz
  • 6.4k
  • 2
  • 27
  • 52