Inequality involving entropies: $\left \|p -\frac{1}{n} e \right \|_2\ge\left \|\frac{-p\log p}{H(p)} -\frac{1}{n} e \right \|_2$

Question

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$.

Answer 1

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$.

Answer 2

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.