Return to Answer

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 I expect to converge to the exact value in the limit. (Unfortunately the algorithm has too high complexity to be useful in practice, at least in the form that I will describe.)

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.)

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{29}{60} \approx 0.483.$$ 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 I expect to converge to the exact value in the limit. (Unfortunately the algorithm has too high complexity to be useful in practice, at least in the form that I will describe.)

Thus the remaining problem is to prove $N \le 29$. 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$.

1. I don't know if $N = 29$ is achievable. The largest number of jointly satisfiable versions I've found is $28$, which is achieved by $$\tag{2} X_1 = X_2 = X_3 = 0, \qquad X_4 = 5, \qquad X_5 = X_6 = 9.$$

2. 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.

3. 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]$.

4. 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: this distribution is given by the relative frequencies in (2).

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 I expect to converge to the exact value in the limit. (Unfortunately the algorithm has too high complexity to be useful in practice, at least in the form that I will describe.)

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.$$

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.

1. I don't know if $N = 29$ is achievable. The largest number of jointly satisfiable versions I've found is $28$, which is achieved by $$\tag{2} X_1 = X_2 = X_3 = 0, \qquad X_4 = 5, \qquad X_5 = X_6 = 9.$$

2. 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.

3. 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]$.

4. 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. TThis 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: this distribution is given by the relative frequencies in (2).

1. I don't know if $N = 29$ is achievable. The largest number of jointly satisfiable versions I've found is $28$, which is achieved by $$\tag{2} X_1 = X_2 = X_3 = 0, \qquad X_4 = 5, \qquad X_5 = X_6 = 9.$$

2. 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.

3. 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]$.

4. 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: this distribution is given by the relative frequencies in (2).