How large can $\mathbf{P}[X_1 + X_2 + X_3 < 2 X_4]$ get?

Question

Let $\mu$ be a probability measure on $[0,\infty)$ and $X_1, \dots, X_4 \sim \mu$ independent. Then what can be said about the probability that $X_1 + X_2 + X_3 < 2 X_4$?

More precisely, what is the value of $$\tag{1}\sup_\mu \mathbf{P}[X_1 + X_2 + X_3 < 2 X_4] \quad ?$$ Here's what I know:

• Numerically, taking $\mu$ to be a Gamma distribution at parameter $\alpha \approx 0.5$ gives a value of $\approx 0.3080$ (clearly independently of scale). This is the largest value I've found among the distributions I've tried.
• In the other direction, a symmetrization argument gives an upper bound of $\frac{1}{2}$ on (1). Indeed putting each of the four variables on the right-hand side gives four versions of the inequality $X_1 + X_2 + X_3 < 2 X_4$, all with the same probability. At most two of these can be satisfied jointly (since if three of them held jointly, then adding them produces a contradiction). Then the upper bound of $\frac{1}{2}$ follows by exchangeability: if four symmetric events are such that at most two can happen jointly, then the probability of each is at most $\frac{1}{2}$. (Think of the induced distribution on $\{0,1\}^4$, which must be supported on sequences with at most two $1$'s.)
• There are several similar problems which I've been able to solve: $$\sup_\mu \mathbf{P}[X_1 + X_2 < X_3] = \frac{1}{3}, \qquad \sup_\mu \mathbf{P}[X_1 + X_2 + X_3 < X_4 + X_5] = \frac{2}{5}.$$ In both of these cases, the supremum is approached by a sequence of distributions that are uniform on a large finite set with exponential spacing, so that $+$ effectively becomes $\max$. But such distributions do not approach the supremum in (1).

Answer 1

I believe the probability is at least $\approx0.343$.

Let $\mu_n$ be a probability measure giving $q_n = P_n[ X_1 + X_2 + X_3 < 2X_4]$.

Consider now $(Y_i)_{i\le 4}$ Bernoulli$(p)$. The $Y_i$'s produce the desired inequality with an inclusive $\le$ with probability \begin{align} I+II+III &= P[ \text{binomial}(3, p) \le 1] P[Y_4=1] \\&\quad+ P[ \text{binomial}(3, p) = 2] P[Y_4=1] \\&\quad+ (1-p)^4. \end{align} But the problem requires a strict inequality, for which the second and third terms are lost. We can boost this binomial scheme by using $X_1,X_2,X_3,X_4$ from $\mu_n$, independently $Y_i\sim{}$Bernoulli$(p)$ as above, and set $$Z_i = t X_i + Y_i.$$ for some $t>0$ very small. Assuming that the support of $\mu_n$ is bounded, we can always choose $t>0$ small enough so that the first term is unchanged, while the second term and third terms become strict inequality with independent probability $q_n$: $$ q_{n+1} = P[Z_1+Z_2+Z_3 < 2Z_4] = P[ \text{binomial}(3, p) \le 1] P[Y_4=1] + q_n\Big( P[ \text{binomial}(3, p) = 2] P[Y_4=1] + (1-p)^4\Big). $$ This defines two polynomial $f(p)$ and $g(p)$ of order $4$ in $p\in[0,1]$ such that $$ q_{n+1} = f(p) + q_n g(p). $$ Consider the fixed-point $q_\infty$ defined by $$ q_{\infty} = f(p) + q_{\infty} g(p). $$ We can reach a large $q_\infty$ by maximizing $$ M = \max_{p\in[0,1]} \frac{f(p)}{(1-g(p))_+}. $$ If I am not mistaken, $f(p)= ((1-p)^3 + 3(1-p)^2p )p$ while $g(p) = 3p^2(1-p)p + (1-p)^4$.

The maximum is reached at $p^* \approx 0.404$ giving $M\approx 0.343$.

We now set $p=p^*$ for this maximizer, and perform this procedure, starting from some discrete distribution $q$ (e.g., Bernoulli($p^*$)). Since $g(p^*)\in(0,1)$, the sequence $q_n$ converges to $M\approx 0.343$.

Edit: using Will's explicit formula with $t=0.1$, with $n=30$ terms confirm a probability of around $0.343$:

🖧[14]: import numpy as np
  ...: 
  ...: p = 0.404
  ...: t = 0.1
  ...: powers = np.arange(30)
  ...: ts = (t ** powers)[None, None, :]
  ...: 
  ...: bs = np.random.binomial(1, p, size=(100000, 4, 30))
  ...: ys = np.sum(ts * bs, axis=-1)
  ...: (np.sum(ys[:, :-1], axis=1) <  2 * ys[:, -1]).mean()
🖧[14]: 0.34353

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