Probability vector $p$ majorizes its normalized entropy vector $\small \frac{-p\log p}{H(p)}$

Question

I guess the following inequality

$$ \sum_{i=1}^n g \left (\frac{-p_i \log p_i}{H(\boldsymbol{p})} \right ) \le \sum_{i=1}^n g (p_i)$$

holds for any continuous convex function $g$ and any probability vector $\boldsymbol{p}=(p_1,\dots,p_n)\ge 0$ with $\sum_{i=1}^np_i=1$ where $H(\boldsymbol{p})=-\sum_{i=1}^n p_i\log p_i $ denotes the Shannon entropy of the probability distrbution $\boldsymbol{p}$. This is equivalent to that the following majorization relation holds

$$ \frac{-\boldsymbol{p}\log \boldsymbol{p}}{H(\boldsymbol{p})} \prec \boldsymbol{p}.$$

I already have a proof for the case where all probabilities are less than $e^{-1}$, but the general case where one or two of the probabilities can be larger than $e^{-1}$ has remained unsolved so far. The conjecture was numerically checked for $n=2, 3, 4$.

The problem may be of a particular theoretical interest because it seems not easy to obtain it using the existing procedures of generating majorization relations, as $-x\log x$ is not monotone.

---

The problem was first asked in this MSE question, and even after offering a bounty, I had no progress in approaching a full proof or constructing a counterexample (more details, related results and questions, and my past attempts can be found in that question).

Answer 1

This appears to be the case, but I was forced to rely on a somewhat complicated inequality on two real variables that looks quite plausible numerically, though I do not have a 100% rigorous proof of it:

Claim 1. Suppose $0 \leq p \leq q \leq 1$ with $p+q \leq 1$ and $h(q) \leq h(p)$, where $h(x) := x \log \frac{1}{x}$. Let $a = 1/4$ if $q \leq 1/2$, or $a = q(1-q)$ if $q \geq 1/2$. Then at least one of $$ a (\log \frac{1}{p} - \log \frac{1}{q}) \leq (q-p) (h(p)+h(q)+h(1-p-q))\tag{$*$}\label{477014_star}$$ and $$ (1-q) \log \frac{1}{p} \leq \frac{q}{1-q} h(q).\tag{$**$}\label{starstar}$$ holds.

In the triangle where $0 \leq p \leq q \leq 1$ and $p+q \leq 1$, the following plot shows the region where $h(q) \leq h(p)$ (in green) and where \eqref{477014_star} fails (in blue), and where \eqref{starstar} holds (grey), so numerically the intersection of the green and blue regions lie in the grey region.

Now to explain why the claim gives the result. We would like to show, for a given $1 \leq k < n$, that the sum of the $k$ largest values of $\frac{h(p_i)}{H(\mathbf{p})}$ is bounded by the sum of the $k$ largest values of $p_i$.

Let $E$ denote the indices $i$ corresponding to the $k$ largest values of $h(p_i)$. We also write $\theta := \sum_{i \in E} p_i$, so that $1-\theta = \sum_{j \not \in E} p_j$.

The easy case is when the set $E$ is also the $k$ largest values of $p_i$, thus if $i$ lies in $E$ and $j$ lies outside of $E$ then $\log \frac{1}{p_j} \geq \log \frac{1}{p_i}$. Averaging, we conclude that $$ \frac{1}{1-\theta} \sum_{j \not \in E} p_j \log \frac{1}{p_j} \geq \frac{1}{\theta} \sum_{i \in E} p_i \log \frac{1}{p_i}$$ which can be rearranged to $$ \sum_{i \in E} \frac{h(p_i)}{H(\mathbf{p})} \leq \theta = \sum_{i \in E} p_i,$$ as required. Note that this includes the case you already treated in which all the $p_i$ are at most $1/e$.

Now we deal with the hard case when $E$ is not the $k$ largest indices of $p_i$. Let $p$ denote the smallest value of $p_i$ for $i \in E$, and let $q$ be the maximal value of $p_i$, which is attained outside of $E$. We will try here to estimate all relevant quantities in terms of $p$ and $q$.

Clearly $1 \leq p \leq q \leq 1$ and $p+q \leq 1$, and also $h(p) \geq h(q)$ (i.e, $(p,q)$ lies in the green region, in particular $q \geq 1/e$ now). If $i \in E$ and $j \not \in E$, then by construction we have $p_j \leq p_i$ or $p \leq p_i \leq p_j \leq q$, hence in either case $$ \log \frac{1}{p_j} \geq \log \frac{1}{p_i} - (\log \frac{1}{p} - \log \frac{1}{q}).$$

Averaging, we conclude $$ \sum_{j \not \in E} \frac{p_j}{1-\theta} \log \frac{1}{p_j} \geq \sum_{i \in E} \frac{p_i}{\theta} \log \frac{1}{p_i} - (\log \frac{1}{p} - \log \frac{1}{q})$$ which one can rearrange as $$ \sum_{i \in E} p_i \log \frac{1}{p_i} \leq \theta H(\mathbf{p}) + \theta(1-\theta) (\log \frac{1}{p} - \log \frac{1}{q}).$$ Meanwhile, the sum of the $k$ largest values of $p_i$ at least $\theta + (q-p)$, so it suffices to show that $$ \theta H(\mathbf{p}) + \theta(1-\theta) (\log \frac{1}{p} - \log \frac{1}{q}) \leq (\theta + (q-p)) H(\mathbf{p})$$ or equivalently $$ \theta(1-\theta) (\log \frac{1}{p} - \log \frac{1}{q}) \leq (q-p) H(\mathbf{p}).$$ Since the $p_i$ contain both $p$ and $q$ as attained by distinct indices, we have $$ H(\mathbf{p}) \geq p \log \frac{1}{p} + q \log \frac{1}{q} + (1-p-q) \log \frac{1}{1-p-q}.$$ Also, $\theta(1-\theta)$ is bounded by $1/4$, and for $q \geq 1/2$ it is additionally bounded by $q(1-q)$ since $\theta \leq 1-q$. The result then follows if \eqref{477014_star} holds.

To handle the remaining case we make an alternate estimate of the various quantities involved in terms of $p$ and $q$. Clearly $$ H({\mathbf p}) \geq \sum_{i \in E} h(p_i) + h(q)$$ so as the sum of the $k$ largest probabilities is certainly at least $q$, it would suffice to show that $$ \sum_{i \in E} h(p_i) \leq q (\sum_{i \in E} h(p_i) + h(q))$$ or equivalently $$ \sum_{i \in E} h(p_i) \leq \frac{q}{1-q} h(q).$$ Since $h(p_i) \leq p_i \log \frac{1}{p}$ for all $i \in E$, and $\sum_{i \in E} p_i \leq 1-q$, it thus suffices to have $$ (1-q) \log \frac{1}{p} \leq \frac{q}{1-q} h(q).$$ which is \eqref{starstar}. So the result follows from Claim 1.

EDIT: it is perhaps worth recording the somewhat convoluted process towards finding this solution. The easy case came from trying to reconstruct the OP's claim that the result held when all probabilities were less than $1/e$, in which case $h$ is increasing and so $E$ was indeed the $k$ largest values. This analysis also suggested in the hard case that things might be particularly delicate in a near-uniform situation in which $p$ and $q$ were close. So I used an ansatz $q=p+\varepsilon$ and performed some Taylor expansions in $\varepsilon$, kept only the top order terms, convinced myself that this model case was OK for $\varepsilon$ small enough by a perturbation of the easy case argument, and then applied this perturbed argument to the general case; after writing out the details and estimating terms as best as I could, I found that this worked as long as \eqref{477014_star} held (though initially I made some sign errors due to an incorrect definition of $p$, which one can locate in the edit history of interested). An initial numerical test suggested that \eqref{477014_star} was always true in the region of interest (i.e., the blue and green regions were disjoint), but a finer asymptotic analysis eventually suggested to me that in fact there was a very small intersection in the region where $(p,q)$ was close to $(0,1)$. So I then ran a different ansatz $p = \varepsilon$, $q = 1-\delta$ (with $\delta$ of the order of $\varepsilon \log 1/\varepsilon$ in order to satisfy the constraint $h(q) \leq h(p)$) and performed another Taylor approximation to drop terms, at which point I found the argument which could be extended all the way to the region \eqref{starstar}. Now it seemed numerically that the entire range of possible parameters $(p,q)$ was covered. Given the gap between the range covered (grey plus the complement of blue) and the range that was needed to be covered (green), it may be possible to simplify the argument either by being cruder in the estimates, or by finding a unifying argument that uses bounds from both cases. However it seems to me that the geometry of the problem is sufficiently complicated to the point that one cannot hope to just use standard inequalities such as Jensen's inequality alone to obtain a solution.

Answer 2

An analysis of Claim 1:

For fixed $q\ge e^{-1}$, let use denote $p$ by $x$ and define these functions:

$$f(x)=\left(1-q\right)^{2}\log\left(\frac{1}{x}\right)-q^2\log\left(\frac{1}{q}\right)$$

a decreasing concave function with the only root $r_f=e^{\frac{q^2\log q}{\left(1-q\right)^{2}}};$

$$g(x)=\max\left(q,0.5\right)\left(1-\max\left(q,0.5\right)\right)\left(\log\left(\frac{1}{x}\right)-\log\left(\frac{1}{q}\right)\right)-\left(q-x\right)\left(x\log\left(\frac{1}{x}\right)+q\log\left(\frac{1}{q}\right)+\left(1-x-q\right)\log\left(\frac{1}{1-x-q}\right)\right)$$

a function with maximum two roots (it follows from that $\frac{g(x)}{q-x}$ is a convex function): the smallest $r_g$ and largest roots $R_g$ which may not exist for all values of $q$, in that case we use $+\infty$ ($R_g=q$ for $q \ge 0.5$ and $R_g=+\infty$ otherwise; moreover, as I checked $r_g$ exists even for $q=1-10^{-10}$ by observing that $\small g\left (\frac{1-q}{2} \right )<0$);

$$h(x)=x\log\left(\frac{1}{x}\right)-q\log\left(\frac{1}{q}\right),$$

a concave function with the smallest root $r_h=e^{W_{-1}(q\log q)}$ and largest root $R_h=e^{W_{0}(q\log q)}=q$, where $W_{0}$ and $W_{-1}$ denote two branches of the Lambert $W$ function (as $e^{-1} \le q\log q<0$, the equation $x^x=q^q$ has two real solutions).

The above functions can be seen visually here, which also shows how the claim holds for any $q\ge e^{-1}$. You can see that the red area (where none of (∗) and (∗∗) holds) and green area (where all initial conditions of the claim hold) have no overlap.

Now we can derive the following equivalent condition for Claim 1:

Claim 1 is equivalent to show $$\min (r_f, r_g) < r_h \tag{1}$$ for any $q\ge e^{-1}.$

As we have $f(r_h)<0$ for $q>q_2 \approx 0.7307$ where for $q=q_2$ $r_f=r_h$, to prove (1) it remains to show

For any $e^{-1} \le q <q_2 $ $$g(r_h)<0 \tag{2}$$ where $r_h=e^{W_{-1}(q\log q)}=\frac{q\log q}{W_{-1}(q\log q)}$ and $q_2 \approx 0.7307 $ satisfies $$(1 - q_2)^2 = q_2\exp \left ((q_2^2\log q_2)\left(1-q_2\right)^{-2} \right ).$$

Note that for $e^{-1}<q< 0.5$, we have two intervals $(0, r_g)$ and $(R_g=q, r_f)$ on which none of (∗) and (∗∗) holds, but assessing the second one is not required as it clearly appears after the interval $[r_h,R_h=q]$, over which the initial conditions of the claim are satisfied.

It is worth mentioning that $\min (r_f, r_g)=r_g$ iff $q\le q_0 \approx 0.773$. In fact, for $q\le q_1\approx 0.916$, $r_g < r_h$, so we need (∗∗) only for $q> q_1$. Another observation is that $a=\frac14$ in (∗) works for all values of $q\ge e^{-1}$ excepting a very short interval that includes $(0.72,0.73)$.

---

Proving (2) seems difficult as $r_h$ is a highly complex quantity. However, for $r_h$ we have the following lower and upper bounds [2]:

$$\small r^L_h=\frac{q\ln q}{-1-\sqrt{2\left(-\ln\left(-q\ln q\right)-1\right)}-\left(-\ln\left(-q\ln q\right)-1\right)}$$ $$\small r^U_h=\frac{q\ln q}{-1-\sqrt{2\left(-\ln\left(-q\ln q\right)-1\right)}-\frac{2}{3}\left(-\ln\left(-q\ln q\right)-1\right)}.$$

Hence, instead of proving (2), to make sure that $r_g$ is smaller than $r_h$, we can prove the following sufficient condition:

To prove Claim 1, it suffices to show $$g(r^L_h)<0 \tag{3} $$ for $e^{-1} \le q <q_2 .$

The function $$\frac{g(r^L_h)}{q-r^L_h}$$ is depicted below (source) for $0<q<1$

$\hspace{3cm}$

This figure clearly shows $g(r^L_h)<0$ for $e^{-1} \le q <q_2$, where the boundaries are displayed by vertical lines. Considering that the values of function $\frac{g(r^L_h)}{q-r^L_h}$ is sufficiently smaller than $0$ in the range of interest $e^{-1} \le q <q_2$, this observation can be straightforwardly converted to a rigorous proof using interval arithmetic, which is a usual practice in such a case. Thus, (3) holds, and this implies (2) and (1), which are equivalent conditions for Claim 1, and we are done. $\tag*{$\blacksquare$}$