Distributional inequality

194 Views Asked by At

Let $a$ and $b$ be two points in the $d-$dimensional simplex $\Delta_d$. Let $c$ be the point in the $d-$dimensional simplex defined as $c_i = \frac{\sqrt{a_i b_i}}{\sum_{j=1}^d \sqrt{a_jb_j}} $ for all $i \in [d]$ is it true that:

\begin{equation} \max(\| a-c \|_1, \|b-c\|_1 ) \leq \| a-b \|_1 \end{equation}

Where $\| \cdot \|_1$ denotes the $\ell_1$ norm.

We define the $d-$dimensional simplex as the set of positive entry vectors whose entries sum to 1.

1

There are 1 best solutions below

0
On

We can prove an even stronger proposition:

Let $p$ be any point such that $\min(a_i,b_i) \leq p_i \leq \max(a_i,b_i)$ for each $1 \leq i \leq d$. Let $c = p/\sum p_i$. Then $$\|a - c\|_1 \leq \|a - b\|_1$$ By symmetry we also have $$\|b - c\|_1 \leq \|a - b\|_1$$ Hence the original statement is proved.

From the condition $$\min(a_i,b_i) \leq p_i \leq \max(a_i,b_i)$$ we have $$|a_i - p_i| + |b_i - p_i| = |a_i - b_i|$$ Now let $t = 1/\sum p_i$. $$\|a - c\|_1 = \sum |a_i - tp_i| = \sum |a_i - p_i + (1 - t)p_i| \leq \sum |a_i - p_i| + \sum |(1 - t)p_i|$$ Note that $$\sum |(1 - t)p_i| = |1 - t| \cdot \sum p_i = \frac{|1 - t|}{t} = |1/t - 1| = |\sum p_i - 1|$$ $$\sum |b_i - p_i| \geq |\sum (b_i - p_i)| = |1 - \sum p_i| = |\sum p_i - 1|$$ Therefore $$\|a - c\|_1 \leq \sum |a_i - p_i| + \sum |b_i - p_i| = \sum |a_i - b_i| = \|a - b\|_1$$ Done.