Skip to main content
3 of 10
Typo, picture, `\tag`+`\label`+`\eqref`
LSpice
  • 12.9k
  • 4
  • 45
  • 69

This appears to be the case, but I was forced to rely on an inequality on two real variables that I can verify numerically but not rigorously, namely:

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 $$ a (\log \frac{1}{p} - \log \frac{1}{q}) \leq (q-p) (h(p)+h(q)+h(1-p-q)).\tag{$*$}\label{477014_star}$$

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), so numerically the regions are indeed disjoint.

Picture of described 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 largest value of $p_i$ for $i \in E$, and let $q$ be the maximal value of $p_i$, which is attained outside of $E$. Clearly $1 \leq p \leq q \leq 1$ and $p+q \leq 1$, and also $h(p) \geq h(q)$. If $i \in E$ and $j \not \in E$, then by construction we have $p_i \leq p \leq q \leq p_j$, hence $$ \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 from Claim 1.

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539