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

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.

Regions in the claim

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

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539