# Choosing the vector that minimizes this sum related to the rearrangement inequality

The rearrangement inequality states that, for two sets of real numbers $x_1\leq\dots{}\leq x_n$ and $y_1\leq\dots{}\leq y_n$, the sum $\sum_{i=1}^n x_{\sigma(i)}y_i$ is minimized for the particular choice of the permutation $\sigma(i) = n-i+1$.

A simple corollary (at least when numbers are positive) is that the sum $\sum_{i=1}^n x_{\sigma(i)} \sum_{j=1}^i y_j$ is also minimized for the same choice of $\sigma$. Indeed, the series $(\sum_{j=1}^i y_j)_{i=1}^n$ is increasing.

I have the following very similar situation. I have four sets of positive real numbers:

$$x_{0,1}\geq\dots{}\geq x_{0, n_0} \qquad x_{1,1}\geq\dots{}\geq x_{1, n_1}$$ $$y_{0,1}\leq\dots{}\leq y_{0, n_0} \qquad y_{1,1}\leq\dots{}\leq y_{1, n_1}$$

Let $b$ be a binary vector of size $n_0+n_1$. Let $c_x(i)$ be the number of elements equal to $x$ in the subvector $b_{1..i}$. I wish to minimize the following sum:

$$S(b) = \sum_{i=1}^{n_0+n_1} x_{b_i, c_{b_i}(i)} \sum_{j=1}^i y_{b_j, c_{b_j}(j)}$$

In order to make things perhaps a bit clearer (the formalization makes it more complicated that it really is), here is an example:

$$n_0=1 \qquad n_1=2$$ $$x_{0,i} = 0.9^{i} \qquad x_{1,i} = 0.8^i$$ $$y_{0,i} = 4i \qquad y_{1,i} = 3i$$

A possible vector $b$ is $[1, 1, 0]$, which gives a sum of $19.86$. However, the vector $[1, 0, 1]$ gives the minimal $17.02$.

I am interested in the optimal vector $b^*$ that minimizes $S$. Some reasons led me to believe that $b^*_i = 0$ if and only if $x_{0, c_0(i)}/y_{0, c_0(i)} > x_{1, c_1(i)}/y_{1, c_1(i)}$ (and also if c_0(i) < n_0), and so far it seems to hold numerically for the data I have in my case.

I have tried to compute $S(b^*)-S(\tilde{b^*})$ for any perturbed'' $\tilde{b^*}$ in which two elements from $b^*$ are swapped (the difference should be $\leq 0$). However, nothing simplifies very well, unless the swap is between two adjacent elements, in which case the conjecture follows easily. Computing this numerically for the general case did not give me much indication either.

-
Are you sure the optimal vector is $[0,1,0]$ rather than $[1,0,1]$? Also, the conjectured optimality condition seems to fail for $n=1$, $x_0=x_1=(1)$, $y_0=(1)$, $y_1=(2)$. Did you, perchance, exchange zeros with ones somewhere? – Peter Košinár Jan 26 '14 at 11:34
Thank you, I corrected the example. Regarding your example, we have $S([0]) = 1 < S([1]) = 2$, and the conjectured condition proposes indeed $b^* = [0]$. – doc Jan 26 '14 at 18:43
Serves me well... talking about exchanging and making the mistake myself :-) The intended example was $x_0=(1)$, $x_1=(2)$, $y_0=y_1=(1)$. – Peter Košinár Jan 27 '14 at 19:04
@PeterKošinár: Yes it seems there are problems with small $n$. My intention is to work with big values of $n$, but this example is degenerated (but correct and helpful). The intuition here is that it is preferable, in order to minimize the sum, to pair big $x$'s with small $y$'s, in the same line of thought as the rearrangement inequality. In this case the sum cuts short too early for this strategy to prove useful. Perhaps the conjecture is only true for $n\to\infty$? (or perhaps is it not true at all) – doc Jan 28 '14 at 8:15
@PeterKošinár: I modified the statement slightly following our discussion and my experiments, and I think it is more correct now. – doc Jan 30 '14 at 16:26