16
$\begingroup$

For a given probability vector $p=(p_1,\dots,p_n)$ with $p_1,\dots,p_n > 0, \sum_{i=1}^n p_i=1$ and with $e:= (1, \dots, 1)$, I want to prove the following inequality: $$\small\left \|p -\frac{1}{n} e \right \|^2_2=\sum_{i=1}^n \left (p_i -\frac{1}{n} \right )^2\ge\left \|-\frac{1}{H(p)}p \log p -\frac{1}{n} e \right \|^2_2=\sum_{i=1}^n \left (\frac{-p_i \log p_i}{-\sum_{i=1}^n p_i\log p_i} -\frac{1}{n} \right )^2, \tag{1}$$ where the equality holds only if all the probabilities $p_i,i=1,\dots,n$ are equal.

For $n=2$, the difference of the left and right sides in (1) is plotted below for $(p_1,p_2)=(p,1-p)$ (source):

which shows the inequality holds for $n=2$.

I came across with this inequality in my answer to this question. I guess the above inequality holds for any $n\ge2$ (and any $l_p$ norm) based on my numerical experiments for $n=2$. For $n=3$ it also holds, which can be seen below where the difference of the left and right sides in (1) is shown for $(p_1,p_2,p_3)=(x,y,1-x-y)$ (you can see the 3D version of the plot here, which can be rotated in any direction):


The above inequality indicates that the distance of the probability vector $p\neq\frac{1}{n} e$ from the center of the standard simplex, i.e. $\frac{1}{n} e$ which has the maximum entropy among all distributions on a sample space with $n$ elements, is strictly larger than the distance of the entropy-based probability vector $\frac{-p \log p}{H(p)}$ generated based on the entropies of disjoint events occurring with probabilities $p_1,\dots,p_n$.

$\endgroup$
4
  • $\begingroup$ This question can be simplified somewhat by defining the quantity $q_i = (-p_i \log p_i) / H(p)$. Note that $q_i > 0$ and $\sum_i q_i = 1$. Then your inequality can be reduced to $\sum_i p_i^2 \geq \sum_i q_i^2$. $\endgroup$ Commented Jul 26 at 17:25
  • $\begingroup$ @JohnBarber Thanks! You may note that it reduces to $$\sum_{i=1}^n(p_i-n^{-1})^2\ge \sum_{i=1}^n(q_i-n^{-1})^2.$$ $\endgroup$
    – Amir
    Commented Jul 26 at 17:33
  • 1
    $\begingroup$ Yes. Which immediately proves the equality case, since when $p_i = 1/n$ we also have $q_i = 1/n$. $\endgroup$ Commented Jul 26 at 17:34
  • $\begingroup$ Isn't the $e$-factor missing in the sum formulations of the formula? $\endgroup$
    – ConnFus
    Commented Jul 27 at 11:28

2 Answers 2

7
$\begingroup$

A more general result can be given as follows:

$$ \sum_{i=1}^n \phi \left (\frac{\ f(a_i)}{\sum_{i=1}^n f (a_i)} \right ) \le \sum_{i=1}^n \phi \left (\frac{a_i}{\sum_{i=1}^n a_i} \right ) \tag {1} $$ where $\phi$ is an arbitrary convex function, $a_1,\dots, a_n \ge 0$ are given numbers for which $\sum_{i=1}^n a_i >0$ and $\sum_{i=1}^n f(a_i) >0$, $f: \mathbb R_{\ge 0} \to \mathbb R_{\ge 0}$ is an increasing function with $\frac{f(x)}{x}$ being decreasing on an interval including $a_1,\dots, a_n$. When $\frac{f(x)}{x}$ is strictly decreasing and $\phi$ is strictly convex, the equality holds only for $a_1=\dots=a_n$.

Examples of $f$ that can be used above are $f(x)=x^\theta, x\in \mathbb R$ for any $\theta \in (0,1)$, any increasing non-negative concave function, and $f(x)=-x\log x , x\in [0,\exp(-1)]$.

In particular, for $\phi(x)=\left |x -\frac{1}{n}\right |^\alpha$ with $\alpha \ge 1$, the above implies

$$\left \|\frac{(f (p_1),\dots,f (p_n))}{\sum_{i=1}^n f (p_i)} -\frac{1}{n} e \right \|_\alpha \le \left \|p -\frac{1}{n} e \right \|_\alpha \tag {2} $$ for $\alpha\ge 1$, $p_1,\dots,p_n \ge 0$ with $\sum_{i=1}^n p_i=1$, and any increasing function $f:I\to \mathbb R_{\ge 0}$ for which $\frac{f(x)}{x}$ is decreasing, where $I$ is the interval $[p_{(n)},p_{(1)}]$.

Considering $f(x)=-x\log x$, the above proves the inequality given in the OP when all probabilities $p_1,\dots,p_n$ are less than $\exp(-1)$ since $-x\log x$ is increasing only on the interval $[0,\exp(-1)]$. Solving the general case remains as open problem. Hope someone can help to solve it generally, which may need to use something other than majorization.

It worth noting that we have the following related result (with a key difference on the required condition for $f$), which follows from an existing result (see F4):

$$ \sum_{i=1}^n \phi \left (\frac{\ f(a_i)}{\sum_{i=1}^n f (a_i)} \right ) \ge \sum_{i=1}^n \phi \left (\frac{a_i}{\sum_{i=1}^n a_i} \right ) \tag {3} $$ where $\phi$ is an arbitrary convex function, $a_1,\dots, a_n \ge 0$ are given numbers for which $\sum_{i=1}^n a_i >0$ and $\sum_{i=1}^n f(a_i) >0$, $f: \mathbb R_{\ge 0} \to \mathbb R_{\ge 0}$ is a function with $\frac{f(x)}{x}$ being increasing on an interval including $a_1,\dots, a_n$. When $\frac{f(x)}{x}$ is strictly increasing and $\phi$ is strictly convex, the equality holds only for $a_1=\dots=a_n$.


Proof of (1)

Following the idea of using majorization suggested by @Ѕᴀᴀᴅ, a proof can be developed based on the following two facts:

F1: $x$ majorizes $y$ iff $\sum_{i=1}^n \phi(x_i) \ge \sum_{i=1}^n \phi(y_i)$ for any convex function $\phi$ (a well-known equivalent condition for majorization).

F2: Given $a_1\ge \dots \ge a_n \ge 0$ and $b_1\ge \dots \ge b_n \ge 0$ with $\frac{b_n}{a_n} \ge \dots \ge \frac{b_1}{a_1}$ where $ \sum_{i=1}^n a_i>0$ and $ \sum_{i=1}^n b_i >0$, vector $\frac{a}{\sum_{i=1}^n a_i}$ majorizes vector $\frac{b}{\sum_{i=1}^n b_i}$.

In F2, we adopt the convention $\frac{c}{0}=\infty$ for any $c\ge 0$, for the sake of simplicity.

For any given vector $u\ge 0$, if $w$ is defined as $w_i=f(u_i), i=1,\dots,n$ where $f: \mathbb R_{\ge 0} \to \mathbb R_{\ge 0}$ is an increasing function for which $\frac{f(x)}{x}$ is decreasing, then vectors $a=(u_{(1)},\dots, u_{(n)})$ and $b=(w_{(1)},\dots, w_{(n)})$ satisfy the condition of F2 as the sequence $\frac{f(u_{(i)})}{u_{(i)}}, i=1,\dots,n$ is increasing, and thus we obtain the following interesting result:

F3: If vector $u \ge 0$ and $f: \mathbb R_{\ge 0} \to \mathbb R_{\ge 0}$ is increasing with $\frac{f(x)}{x}$ being decreasing where $ \sum_{i=1}^n u_i>0$ and $ \sum_{i=1}^n f(u_i)>0$, vector $\frac{u}{\sum_{i=1}^n u_i}$ majorizes vector $\frac{(f (u_1),\dots,f (u_n))}{\sum_{i=1}^n f(u_i)}$.

A related result first appeared in page 4 of this 1967 paper [1, 2] (see also B.2. Proposition in page 188 of this book [3]) as follows:

F4: Given vector $u \ge 0$ and function $f: \mathbb R_{\ge 0} \to \mathbb R_{\ge 0}$ with $\frac{f(x)}{x}$ being increasing where $ \sum_{i=1}^n u_i>0$ and $ \sum_{i=1}^n f(u_i)>0$, vector $\frac{(f (u_1),\dots,f (u_n))}{\sum_{i=1}^n f(u_i)}$ majorizes vector $\frac{u}{\sum_{i=1}^n u_i}.$

To prove the above, again we can use F2 by setting $a=(w_{(1)},\dots, w_{(n)})$ and $b=(u_{(1)},\dots, u_{(n)})$ where $w_i=f(u_i), i=1,\dots,n$ for $u\ge 0$. In this case, we do not need to assume that is increasing because $b_1\ge \dots \ge b_n$ and $\small \frac{a_1}{b_1}\ge \dots \ge \frac{a_n}{b_n}$ together imply $a_1\ge \dots \ge a_n$.

Now one can see that the inequality (1) follows from F1 and F3, and (3) follows from F1 and F4.


Proof of F2

To be self-contained, here I provide the proof of F2, adjusted from the one given in page 3 of [1] for $a,b>0$. It is enough to show that for any $k=1,\dots,n$:

$$\small \frac{\sum_{i=1}^k a_i}{\sum_{i=1}^n a_i} \ge \frac{\sum_{i=1}^k b_i}{\sum_{i=1}^n b_i},$$

which is equivalent to

$$\small \left (\sum_{i=1}^k a_i \right) \left (\sum_{i=1}^n b_i \right)-\left (\sum_{i=1}^k b_i \right) \left (\sum_{i=1}^n a_i \right) \ge 0.$$

The above holds because the expression in the left side can be written as follows:

$$\small \left (\sum_{i=1}^k a_i \right) \left (\sum_{i=k+1}^n b_i \right)-\left (\sum_{i=1}^k b_i \right) \left (\sum_{i=k+1}^n a_i \right)=\sum_{i=1}^k \sum_{j=k+1}^n a_ia_j \left (\frac{b_j}{a_j}-\frac{b_i}{a_i} \right) \ge 0 $$

where we consider the simplifying conventions $0\times \infty=0$ and $\infty - \infty=0$.

$\endgroup$
3
  • $\begingroup$ It seems there is some gap in the derivation of F3. $b=f(a)$ does not neccessarily have the same order as $a$ since we lack something like $f$ is increasing. BTW, I don't know why the reference of [1] can't be accessed. Can you provide the title of it or any other information? $\endgroup$ Commented Aug 3 at 0:09
  • 1
    $\begingroup$ @ImbalanceDream Thanks! I just edited the results to address your point. The title of the paper is "Monotonicity of ratios of means and other applications of majorization". I also added another link to the paper from Sandford University, hope it works. In a temporary comment below, I provided a link to the paper. $\endgroup$
    – Amir
    Commented Aug 3 at 10:25
  • 1
    $\begingroup$ I read it again more calmly and it kinda makes sense to me now so upvote. $\endgroup$
    – Dabed
    Commented Aug 7 at 21:58
5
+50
$\begingroup$

I will base the proof on pretty much the same ideas as Amir in his OP, but I'll not try to work in such a high generality and will use the specifics of the setup a bit.

The general observation is that if we have a concave positive function $f$ with $f(0)=0$ such that $x+f(x)$ is increasing and $\sum_i f(p_i)=\sum_i p_i$, then $\sum_i f(p_i)^2\le \sum_i p_i^2$. Indeed, then we can find $P$ such that $f(p)\ge p, g(p)=f(p)+p\le g(P)$ for $p\le P$ and $f(p)< p, g(p)>g(P)$ for $p>P$. The equality of sums implies that $$ \sum_{i:p_i\le P}(f(p_i)-p_i)=\sum_{i:p_i> P}(p_i-f(p_i))\,, $$ so $$ \sum_{i:p_i\le P}(f(p_i)^2-p_i^2)=\sum_{i:p_i\le P}(f(p_i)-p_i)g(p_i)\le \sum_{i:p_i\le P}(f(p_i)-p_i)g(P) \\ =\sum_{i:p_i> P}(p_i-f(p_i))g(P)\le \sum_{i:p_i> P}(p_i-f(p_i))g(p_i)=\sum_{i:p_i> P}(p_i^2-f(p_i)^2) $$ and the claim follows. Note that we do not need here that $f(p)+p$ increases on an interval, just that it increases on the set of the $p_i$'s used (in that case we take $P$ to be the largest $p_i$ for which $f(p_i)\ge p_i$).

Thus, all we need to show is that if we choose $c>0$ so that $c\sum_i p_i\log\frac 1{p_i}=1$, then for $q$ and $r$ in our set of $p_i$ with $q<r$, we have $$ cq\log\frac 1q+q\le cr\log\frac 1r+r\,. $$ That inequality is linear in $c\ge 0$. It is trivially true for $c=0$. So, it suffices to check it for the largest possible under the circumstances value of $c$, which is $[q\log\frac 1q+r\log\frac 1r]^{-1}$, i.e., we need to check that $$ q\log\frac 1q+q[q\log\frac 1q+r\log\frac 1r]\le r\log\frac 1r+r[q\log\frac 1q+r\log\frac 1r]\,, $$ or $$ \frac{\log\frac 1q}{\log\frac 1r}\le \frac rq\frac{1+r-q}{1+q-r}\,. $$ Now $$ \frac{1+r-q}{1+q-r}\ge \frac{1-q}{1-r}\,, $$ which, after getting rid of the denominators and cancelling the common terms, is equivalent to $r-q\ge r^2-q^2=(r-q)(r+q)$, which holds because $r>q$ and $r+q\le 1$.

Now, after replacing the complicated fraction on the right with the simple one, the inequality becomes trivial: denoting $\bar q=1-q>1-r=\bar r$, we can rewrite it as $$ \frac{\sum_{k\ge 1}\frac 1k\bar q^k}{\sum_{k\ge 1}\frac 1k\bar r^k}\le \frac{\sum_{k\ge 1}\bar q^k}{\sum_{k\ge 1}\bar r^k} $$ and we can employ the general principle that if $A_k,B_k>0$, $A_k/B_k$ is increasing, and $w_k>0$ is a decreasing sequence of weights, then $$ \frac{\sum_{k\ge 1}w_kA_k}{\sum_{k\ge 1}w_kB_k}\le \frac{\sum_{k\ge 1}A_k}{\sum_{k\ge 1}B_k}\,, $$ provided that all series converge, etc.

The End.

$\endgroup$
6
  • $\begingroup$ Thanks again for the solution! Could you see how to extend the proof for the case where $l_2$ norm in the inequality is replaced by $l_p$ norm with arbitrary $p \ge 1$? $\endgroup$
    – Amir
    Commented Aug 6 at 5:58
  • $\begingroup$ @Amir Not immediately. However I would start with numerical check that it is true in such generality. If you do it and it passes, come back and we'll think of it :-) $\endgroup$
    – fedja
    Commented Aug 6 at 10:26
  • $\begingroup$ My numerical check shows it as stated in the OP earlier. $\endgroup$
    – Amir
    Commented Aug 6 at 11:02
  • $\begingroup$ @Amir The exact quote from the OP is based on my numerical experiments for n=2. I would go at least to $n=6$ before getting any confidence in the matter ;-). But I'll think of it when I have free time :-) $\endgroup$
    – fedja
    Commented Aug 6 at 12:55
  • $\begingroup$ In these links 1 and 2, you may see illustrations for $n=3$ :D $\endgroup$
    – Amir
    Commented Aug 6 at 13:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .