Skip to main content
6 of 10
added 215 characters in body
Terry Tao
  • 114.1k
  • 33
  • 462
  • 539

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. UPDATE actually this may not be the case, see final remark.

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 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$. 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_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 from Claim 1.

UPDATE: it seems that Claim 1 may in fact fail for $(p,q)$ sufficiently close to $(0,1)$ (though it is a very close call). It may be that an even more complicated analysis would be needed to resolve this case, involving more statistics than just $p$ and $q$.

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539