An inequality $ k\frac{\sum_{i\neq j} x_i x_j ( (1-x_i-x_j)^{k-1}- (1-x_i)^k(1-x_j)^k)}{\sum_{i=1}^n x_i (1-(1-x_i)^k)} \leq 2$

Question

Let $x_1,\dots, x_n \geq 0$ be a sequence of numbers such that $\sum_{i=1}^n x_i = 1$. For every $k \geq 1$, I conjecture (and need to prove) that $$ \frac{\sum_{1\leq i\neq j\leq n} x_i x_j \left( (1-x_i-x_j)^{k-1}- (1-x_i)^k(1-x_j)^k\right)}{\sum_{i=1}^n x_i \left(1-(1-x_i)^k\right)} \leq \frac{C}{k} $$ where $C>0$ is some absolute constant, which I suspect can be taken to be $C=2$.

I don't really know how to handle this elegantly, or even how to handle it at all. I'd be happy with any proof, but a short one would be appreciated. It's one of these statements which seems to scream for a nice "convexity" or "symmetry" or other "beautiful rabbit out of hat" argument, but any proof at all (or counterexample -- though that'd be quite annoying) would be appreciated.

The "natural" case where all $x_i$ are either 0 or some value $1/m$ (i.e., $x_1=\dots=x_m=1/m$, and $x_{m+1}=\dots=x_n=0$) has an upper bound with a closed form $$ k\frac{(1-\frac{2}{m})^{k-1}-(1-\frac{1}{m})^{2k}}{1-(1-\frac{1}{m})^k} \leq 2 $$ which supports the conjecture. I suspect this is the worst case, but am not sure how to formally argue it.

Answer 1

If you don't care about the constant, the inequality is rather simple. For all practical purposes (i.e., up to an absolute constant factor) $1-(1-x_i)^k\asymp\min(kx_i,1)=y_i$. Also, we trivially have $\sum_i y_i\le k\sum_i x_i=k$. Now we note that $(1-x_i-x_j)^{k-1}-(1-x_i)^{k-1}(1-x_j)^{k-1}\le 0$ (just because $1-x_i-x_j\le(1-x_i)(1-x_j)$). Thus it suffices to prove that $$ \sum_{i,j}x_ix_j[1-(1-x_i)(1-x_j)](1-x_i)^{k-1}(1-x_j)^{k-1}\le \frac Ck\sum_i x_iy_i\,. $$ Now,$1-(1-x_i)(1-x_j)\le x_i+x_j$ and $x_i(1-x_i)^{k-1}\le\min(x_i,\frac 1k)=\frac 1ky_i$, so the LHS is bounded by $$ \frac 1{k^2}\sum_{i,j}(x_i+x_j)y_iy_j=\frac 2{k^2}\sum_{i,j}x_iy_iy_j \\ =\frac 2{k^2}\left[\sum_{i}x_iy_i\right]\left[\sum_{j}y_j\right]\le \frac 2{k^2}\left[\sum_{i}x_iy_i\right]k= \frac 2k\sum_{i}x_iy_i $$ and we are done.

This crude computation doesn't yield $C=2$ though. To get $C=2$ in this way, you just want to define $y_i=1-(1-x_i)^k$ (which is always $\le\min(kx_i,1)$, so the final computation is fine) and show that the inequality $kx_i(1-x_i)^{k-1}\le y_i$ still holds. This is also easy once you realize that $1-(1-x)^k=\int_0^x k(1-t)^{k-1}\,dt$ and you can now rewrite the above argument with this slick definition in the same way, but, of course, that is not how one would guess it in the first place, so I included the crude computation based on the simple idea to replace hard functions with equivalent simple ones :-)

Answer 2

• A failed attempt, which gives the $2/k$ dependence but "loses" the denominator.

We add back the diagonal terms of the double sum, and bound the numerator $N_k(x)$ as \begin{align} N_k(x) &= \sum_{1\leq i\neq j\leq n} x_i x_j \left( (1-x_i-x_j)^{k-1}- (1-x_i)^k(1-x_j)^k\right) \\ &\leq \sum_{1\leq i, j\leq n} x_i x_j \left( (1-x_i-x_j)^{k-1}- (1-x_i)^k(1-x_j)^k\right) \\ &\leq \sum_{1\leq i, j\leq n} x_i x_j \left( (1-x_i)^{k-1}(1-x_j)^{k-1}- (1-x_i)^k(1-x_j)^k\right) \\ &= \sum_{1\leq i, j\leq n} x_i x_j (1-x_i)^{k-1}(1-x_j)^{k-1} \left( x_i+x_j - x_ix_j\right) \\ &= 2\sum_{i=1}^n x_i^2 (1-x_i)^{k-1} \sum_{j=1}^n x_j(1-x_j)^{k-1} - \left(\sum_{i=1}^n x_i^2 (1-x_i)^{k-1}\right)^2 \\ &= \left(\sum_{i=1}^n x_i^2 (1-x_i)^{k-1}\right)\left(\sum_{i=1}^n x_i(2-x_i) (1-x_i)^{k-1}\right) \end{align}

We can bound the first factor as $$ \sum_{i=1}^n x_i^2 (1-x_i)^{k-1} \leq \left(\sum_{i=1}^n x_i\right) \sup_{y\in[0,1]} y (1-y)^{k-1} = 1\cdot \frac{1}{k}\left(1-\frac{1}{k}\right)^{k-1} \leq \frac{1}{k} $$

For the second, we can write $ \sum_{i=1}^n x_i(2-x_i) (1-x_i)^{k-1} \leq 2. $

Ufortunately, this does not seem to lead to a better bound, since that second term is roughly of the form $cst\cdot\sum_{i=1}^n x_i(1-x_i)^{k}$, while we would like to compare it to $cst(1-\sum_{i=1}^n x_i(1-x_i)^{k})$ (which can be much, more smaller, as we can have $\sum_{i=1}^n x_i(1-x_i)^{k} \approx 1$).

• Some evidence, based on Taylor expansions. If we just take the linear part of the Taylor expansions (which we cannot in general, of course) and ignore the rest, we get: $$\begin{align} &\frac{\sum_{i\neq j} x_i x_j \left( (1-x_i-x_j)^{k-1}- (1-x_i)^k(1-x_j)^k\right)}{\sum_{i=1}^n x_i \left(1-(1-x_i)^k\right)} \\&\stackrel{\color{red}⚠️}{\approx} \frac{\sum_{i\neq j} x_i x_j \left( (1-(k-1)(x_i+x_j)- (1-k (x_i +x_j)\right)}{\sum_{i=1}^n x_i \left(1-(1-k x_i)\right)} \\ &= \frac{\sum_{i\neq j} x_i x_j \left(x_i+x_j\right)}{k\sum_{i=1}^n x_i^2} \\ &\leq \frac{\sum_{i, j} x_i x_j \left(x_i+x_j\right)}{k\sum_{i=1}^n x_i^2} = \frac{2\sum_{i=1}^n x_i \sum_{j=1}^n x_j^2}{k\sum_{i=1}^n x_i^2} \\ &= \frac{2}{k} \end{align}$$ using $\sum_{i=1}^n x_i=1$ in the last equality.