Inequality concerning sums of ordered variables

1.6k Views Asked by At

With $Y=(Y_1,\ldots,Y_{n_y})$, $n_y \geq 2$, and $Z=(Z_1,\ldots,Z_{n_z})$, $n_z \geq 2$, writing $Y_{(1)},Y_{(2)},..., Y_{(n_y)}$ the ordered values of $Y$ such that: $Y_{(1)} < Y_{(2)} < ... < Y_{(n)}$ (and the same for $Z_{(i)}$), assuming only positive values for $Y$ and $Z$, and setting the merged vector (concatenated) $(Y^\frown Z)=(Y_1,\ldots,Y_{n_y},Z_1,\ldots,Z_{n_z})$, trying to prove the following inequality:

$$\frac{ \sum _{i=1}^{n_y+n_z} i (Y^\frown Z)_{(i)}}{\sum _{i=1}^{n_y} Y_i+\sum _{i=1}^{n_z} Z_i}-\frac{ \sum _{i=1}^{n_y} i Y_{(i)}}{\sum _{i=1}^{n_y} Y_i}-\frac{\sum _{i=1}^{n_z} i Z_{(i)}}{\sum _{i=1}^{n_z} Z_i}+\frac{1}{2}\geq 0$$

$\textbf{Approach: }$ Using the rearrangement inequality (permutation group), we can derive $$\sum _{k=1}^{n_z+n_y} k (Y^\frown Z)_{(k)}\geq \sum _{j=i}^{n_y} (j+n_z) Y_{(j)}+\sum _{i=1}^{n_z} i Z_{(i)}=n_z \sum _{j=i}^{n_y} Y_{j}+\sum _{j=i}^{n_y} j Y_{(j)}+\sum _{i=1}^{n_z} i Z_{(i)}$$ $$ \sum _{k=1}^{n_z+n_y} k (Y^\frown Z)_{(k)}\geq \sum _{i=1}^{n_y} \text{iY}_{(i)}+\sum _{j=i}^{n_z} (j+n_y) Z_{(j)}=n_y \sum _{i=i}^{n_z} Z_i+\sum _{j=i}^{n_y} j Y_{(j)}+\sum _{i=1}^{n_z} i Z_{(i)}$$

I wonder if this route leads anywhere.

2

There are 2 best solutions below

0
On BEST ANSWER

Define the multiset of cardinality $n$, $\chi(\text{n})\triangleq\{ \sum _{j=1}^i \delta _j: \delta _j \geq 0,2 \leq i \leq n \}$.

For instance we have $\chi(2)=\{\delta_1,\delta_1+\delta_2\}$, $\chi(3)=\{\delta_1,\delta_1+\delta_2,\delta_1+\delta_2+\delta_3\}$, etc.

Now, with $m <n$, $m \in \mathbb{N}^+$ we select $p=_nP_m$ permutations indexed by $k=1, 2, \ldots, p$ of subsets of size $m$ in $\chi(n)$.

More precisely, we define the subset $\chi_m(n)= \chi_m(n,l), \ldots \chi_m(n,p)$ of cardinality $m$ in $\chi(n)$ and $\chi_{m}^c(n)$ its complement such that (indexing by $l$), $\forall l \leq p$, $$\chi(n)= \chi_m(n,l)\cup \chi_m^c(n,l).$$

Let $\sigma \in \mathcal{S}_n$ be any permutation $\sigma_1, \ldots, \sigma_n$ of $ \{1, 2, \ldots, n \}$.

It is a standard result (from the rearrangement inequality) that $$\sum_{i=1}^n i \chi(n)_{(i)}\geq \sum_{i=1}^n \sigma_i \chi(n)_{\sigma_i}.$$

Hence, applying to our case we can derive further inequalities across subsets:

$$\sum _{k=1}^{n} k (\chi(n))_{(k)}\geq \sum _{j=i}^{m} j \chi_m(n,l)_{(j)}+\sum _{i=1}^{m-n} (i+m) \chi_m^c(n,l)_{(i)} \geq \sum _{j=i}^{m} j \chi_m(n,l)_{(j)} +\sum _{i=1}^{m-n} (i) \chi_m^c(n,l)_{(i)}+m\sum _{i=1}^{m-n} \chi_m^c(n,l)_{i}$$ the latter is a non-ordered sum.

We calculate the LHS of the inequality: $$ I_l(m,n)=\frac{ \sum _{i=1}^{n} i \chi(n,l)_{(i)}}{\sum _{i=1}^{m} \chi_m(n,l)_i+\sum _{i=1}^{n-m} \chi_m^c(n,l)_i}-\frac{ \sum _{i=1}^{m} i \chi_m(n,l)_{(i)}}{\sum _{i=1}^{m} \chi_m(n,l)_i}-\frac{\sum _{i=1}^{n-m} i \chi_m^c(n,l)_{(i)}}{\sum _{i=1}^{n-m} \chi_m^c(n,l)_i}+\frac{1}{2}. $$

For $n=2$: $_1P_2=2$, $\chi(2)=\{\delta_1,\delta_1+\delta_2\}$ and the various subsets of cardinality 1 and their complements are: $$ \left\{\begin{array}{ccc} \left\{\delta _1\right\} &,& \left\{\delta _1+\delta _2\right\} \\ \left\{\delta _1+\delta _2\right\} &,& \left\{\delta _1\right\} \\ \end{array}\right\}$$ hence $$I_1(1,2)=I_2(1,2)= \frac{\delta _2}{4 \delta _1+2 \delta _2}\geq 0$$

(We don't need $n=3$ but we do it for verification) For $n=3$, $_2P_3=3$ , $\chi(3)=\{\delta_1,\delta_1+\delta_2,\delta_1+\delta_2+\delta_3\}$ and the various subsets where cardinality 1 and their complements (or, alternatively, the subsets of cardinality 2 and their complements) are

$$ \left\{ \begin{array}{ccc} \left\{\delta _1,\delta _1+\delta _2\right\} &,& \left\{\delta _1+\delta _2+\delta _3\right\} \\ \left\{\delta _1,\delta _1+\delta _2+\delta _3\right\} &,& \left\{\delta _1+\delta _2\right\} \\ \left\{\delta _1+\delta _2,\delta _1+\delta _2+\delta _3\right\}&, & \left\{\delta _1\right\} \\ \end{array} \right\}$$ hence

$$%\left( \begin{array}{c} I_1(2,3)=I_3(1,3)=\frac{\delta _2 \delta _3+\delta _1 \left(\delta _2+4 \delta _3\right)}{2 \left(2 \delta _1+\delta _2\right) \left(3 \delta _1+2 \delta _2+\delta _3\right)} \geq 0\\ I_2(2,3)= I_2(1,3)=\frac{\left(\delta _1+\delta _3\right) \left(\delta _2+\delta _3\right)}{2 \left(2 \delta _1+\delta _2+\delta _3\right) \left(3 \delta _1+2 \delta _2+\delta _3\right)} \geq 0\\ I_3(2,3)= I_1(1,3)=\frac{\left(2 \delta _2+\delta _3\right){}^2+\delta _1 \left(4 \delta _2+\delta _3\right)}{2 \left(2 \delta _1+2 \delta _2+\delta _3\right) \left(3 \delta _1+2 \delta _2+\delta _3\right)}\geq 0\\ \end{array} %\right) $$ Let us see how when it holds for $n$ it necessarily holds for $n+1$. I continue with the following simplification of notation: $$I=\frac{S_s}{S_1+S_2}-\frac{Ss_1}{S_1}-\frac{S_{s2}}{S_2}+\frac{1}{2}$$

for $n+1$

$$I'=\frac{S_s'}{S_1+S_2'}-\frac{Ss_1}{S_1}-\frac{S_{s2'}}{S_2'}+\frac{1}{2}$$

$Ss' = Ss+ n(S_s +\delta_{n+1})$

$S_2'=2 S_2+\delta_{n+1}$

$S_{s2} = S_{s2}+ (n-m) (S_{s2}+\delta_{n+1})$.

Reexpressing $I'$:

$$I'=\frac{(n+1) \delta _{n+1}+(n+2) S_s}{S_1+2 S_2+\delta _{n+1}}-\frac{S_{\text{s1}}}{S_1}-\frac{(n-m+1) \left(\delta _{n+1}+S_{\text{s2}}\right)+S_{\text{s2}}}{\delta _{n+1}+2 S_2}+\frac{1}{2}$$ From the inequality derived above, we have $S_s \geq S_1 +S_2+ m S_2$; we also have $\delta_{n+1}\geq 0$, as well as the integers $m>1$ and $n>m$ . Normalizing with $S_2=1$ and from these inequalities: $I'\geq I''$, with $$I''=I'\text{/.}\, \left\{S_2\to 1,S_{\text{s2}}\to 1,S_{\text{s1}}\to S_1,S_s\to m+S_1+1\right\}$$

Making $I''$ a single rational function (one single denominator which is positive), and taking the numerator I''' ($sgn(I''')=sgn(I'')$): $$ I'''=\left(10 m \delta _{n+1}-4 \delta _{n+1}\right)+\left(2 m \delta _{n+1}^2-\delta _{n+1}^2\right)+(4 m n-4) +\delta _{n+1} \left(2 m n+(2 m+1) S_1\right)+2 S_1 (m+n+1)+12 m$$ we have $I'''\geq 0$, which ends the proof.

5
On

We can show this using induction.

Step 1 (base case)- The inequality is correct for $n_y=n_z=1$. Without loss of generality, assume $Z\geq Y$. In this case, $S_{s}=Y+2Z$, $S_{s1}=S_1=Y$, $S_{s2}=S_2=Z$. Therefore, the left hand side of the inequality becomes $$ LHS=\frac{Y+2Z}{Y+Z}-\frac{Y}{Y}-\frac{Z}{Z}+\frac{1}{2}=\frac{Z}{Y+Z}-\frac{1}{2}\geq 0. $$

Step 2 (inductive step)- Assuming that the inequality is correct for any vectors Y and Z of length $n_y=k_y$ and $n_z=k_z$, implies that for $n_y=k_y+1$ and $n_z=k_z$, the inequality is correct.

Proof of step 2:

Define $Y’$ of length $k_y$ such that $Y’_{(k_y)}$=$Y_{(k_y)}+\frac{k_y+1}{k_y}Y_{(k_y+1)}$ and the rest of the entries are the same as $Y$. Note by this definition, we get: $$ S’_1=S_1+\frac{1}{k_y}Y_{(k_y+1)}\geq S_1,\\ S’_{s1}=\sum_{i=1}^{k_y}iY'_{(i)}=k_y(Y_{(k_y)}+\frac{k_y+1}{k_y}Y_{(k_y+1)})+\sum_{i=1}^{k_y-1}iY_{(i)}=\sum_{i=1}^{k_y+1}iY_{(i)}=S_{s1},\\ S'_s\leq S_s. $$

According to our assumption for vectors of length $n_y=k_y$ and $n_z=k_z$, for $Y’$ and $Z$ we have $$ \frac{S’_s}{S’_1+S_2}-\frac{S’_{s1}}{S’_1}-\frac{S_{s2}}{S_2}+\frac{1}{2} \geq 0. $$

Since $S’_1\geq S_1$, $S’_{s1}=S_{s1}$, and $S'_s\leq S_s$, we get $$ 0\leq\frac{S’_s}{S'_1+S_2}-\frac{S'_{s1}}{S'_1}-\frac{S_{s2}}{S_2}+\frac{1}{2}\\ =\frac{S’_s}{S'_1+S_2}-\frac{S_{s1}}{S'_1}-\frac{S_{s2}}{S_2}+\frac{1}{2}\\ \leq\frac{S’_s}{S_1+S_2}-\frac{S_{s1}}{S_1}-\frac{S_{s2}}{S_2}+\frac{1}{2}\\ \leq\frac{S_s}{S_1+S_2}-\frac{S_{s1}}{S_1}-\frac{S_{s2}}{S_2}+\frac{1}{2}. $$ Same procedure can be repeated for $Z$ vector. Hence, by induction, the inequality is proved.