1
$\begingroup$

We have the set $\{0,\cdots,2^K-1\}$ in binary representation, $\{00,01,10,11\}$ for $K=2$. Then each $0$ is replaced by $b_k$ and each $1$ is replaced by $1-b_k$, This gives the set $$B=\{b_1b_2,b_1(1-b_2),(1-b_1)b_2,(1-b_1)(1-b_2)\}$$ The same process is done in reverse order for the $a_k$s i.e., by replacing each $0$ by $1-a_k$ and each $1$ by $a_k$. The result is then $$A=\{(1-a_1)(1-a_2),(1-a_1)a_2,a_1(1-a_2),a_1a_2\}$$ Then, we find the absolute difference sum of these two sets: $$f(a_1,b_1,a_2,b_2)=|b_1b_2-(1-a_1)(1-a_2)|+|b_1(1-b_2)-(1-a_1)a_2|+|(1-b_1)b_2-a_1(1-a_2)|+|(1-b_1)(1-b_2)-a_1a_2|$$

Here, each $(a_k,b_k)$ satisfies $1>a_K>\cdots>a_1>0$ and $0<b_K<\cdots<b_1<1$ and $a_k+b_k<1$.

Given any set of pairs $(a_k,b_k)$ for $k\in\{1,\ldots,K\}$, the function $f$ is non-increasing in every $b_k$.

Example: $(a_1,b_1)=(0.1,0.2)$ and $(a_2,b_2)=(0.2,0.1)$. Then if we take $b_1$ as variable we expect that $f(0.1,b_1,0.2,0.1)$ is decreasing for $0<b_1<0.9$. I verified that this is true in Mathematica. If we take $b_2$ as variable we expect that $f(0.1,0.2,0.2,b_2)$ is decreasing for $0<b_2<0.8$. This is also true according to Mathematica.

I guess this should be general for any example. I dont have any idea how to prove it, however.

$\endgroup$
1
$\begingroup$

First, let us replace $a_i$ with $1-a_i$ to simplify notation. Note that we now have $b_i < a_i$. We denote $b_i^0 = b_i$ and $b_i^1 = 1-b_i$. Let $f(\vec{a}, \vec{b}) = \sum_{v\in\{0, 1\}^n}|\prod_{i=1}^nb_i^{v_i} - \prod_{i=1}^na_i^{v_i}|$. We wish to show that $\frac{\partial f}{\partial{b_i}} \leq 0$ for $i\in [n]$.

By symmetry it suffices to show that $\frac{\partial f}{\partial{b_1}} \leq 0$. The trick is to group the terms of $f$ in pairs, with each pair consisting of the $v$'s with $v_0$ either $0$ or $1$, and the remaining $v_i$'s fixed. For $w\in \{0, 1\}^{n-1}$, let $f_w = |b_1\prod_{i=2}^nb_i^{w_{i-1}} - a_1\prod_{i=2}^na_i^{w_{i-1}}| + |(1-b_1)\prod_{i=2}^nb_i^{w_{i-1}} - (1-a_1)\prod_{i=2}^na_i^{w_{i-1}}|$. Since $f = \sum_w f_w$, it suffices to show that for each $w$, that $\frac{\partial f_w}{\partial{b_1}} \leq 0$.

Fix $w$ and note that $f_w$ consists of two terms. For $\frac{\partial f_w}{\partial{b_i}}$ to be positive, we must have that the first term without the absolute value sign is positive and the second is negative. But suppose $b_1\prod_{i=2}^nb_i^{w_{i-1}} > a_1\prod_{i=2}^na_i^{w_{i-1}}$. Then since $(1-b_1)/b_1 > (1-a_1)/a_1$, we can multiply to get $(1-b_1)\prod_{i=2}^nb_i^{w_{i-1}} > (1-a_1)\prod_{i=2}^na_i^{w_{i-1}}$. Thus each $\frac{\partial f_w}{\partial{b_i}} \leq 0$ and we are done.

$\endgroup$
3
  • $\begingroup$ So this is proof by contradiction right? I have some confusion with the construction of $w$. For $n=2$, we need to have $w=0$ and $w=1$ cases. Inside multiplications we have $w_1$, which should always be $1$? It is not very clear to me. Other point is the symmetry. I think we can just flip the things like instead of $b_1(1-b_2)$ we can say $(1-b_2)b_1$, do this for all other cases and the result that we find for $b_1$ is what we also need for $b_2$, since this is true for all $b_i$, then just a single $b_i$ is sufficient. Did I get you right? $\endgroup$ May 21 '21 at 23:30
  • $\begingroup$ I am writing $w = (w_1, \ldots, w_{n-1})$. So for $n = 2$, $w_1 = 0$ and $w_1 = 1$ are the two cases. For $w_1 = 0$, we have $f_w = |b_1b_2 - a_1a_2| + |(1-b_1)b_2 - (1-a_1)a_2|$. For $w_1 = 1$, we have $f_w = |b_1(1-b_2) - a_1(1-a_2)| + |(1-b_1)(1-b_2) - (1-a_1)(1-a_2)|$. You can check that for each of these $f_w$'s the derivatives are at most $0$ using the argument I give. Regarding symmetry, the point is that we don't use anything special about $b_1$ in the above argument, so the same argument can be made for any $b_i$. $\endgroup$
    – Anand
    May 22 '21 at 18:51
  • $\begingroup$ Yes. Exactly what I said and thought. But this argument can be made by reordering the multiplicative elements of the function. The About $w$ I had understood just found not perfectly clear. Thank you for the explanation. $\endgroup$ May 23 '21 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.