The following information theoretic inequality is needed in my work.

Let $n, m, n_1, n_2, \dots, n_k \in \mathbb{Z}^+$ such that $m < n = n_1 + n_2 + \dots + n_k$. I would like to prove that with condition $\sum_{i=1}^k \min \{n_i, m\} \geq \alpha$ we have $$ \sum_{i=1}^k \frac{n_i}{n} \log \frac{n}{n_i} \geq \frac{\alpha - m}{n - m} \log \frac{n}{m} $$ Of course we can prove it by the method of adjustment. But it would be a little lengthy. Since the proof technique has nothing to do with my work, I am coming here and asking for help about a short proof or preferably, a proof in some other's work (so that I could simply refer to it without making a proof by myself).

A short proof when $m=1$.

$\sum_{i=1}^k \min \{n_i, m\} \geq \alpha \implies k \geq \alpha$. Let $H(p_1,p_2,\dots,p_k) = -\sum_{i=1}^k p_i \log p_i$. We have that point $ (\frac{n_1}{n}, \frac{n_2}{n}, \dots, \frac{n_k}{n}) $ is a weighted arithmetic average of $(\frac{n-k+1}{n}, \frac{1}{n}, \dots, \frac{1}{n}),\ (\frac{1}{n}, \frac{n-k+1}{n}, \dots, \frac{1}{n}),\ \dots,\ (\frac{1}{n}, \frac{1}{n}, \dots, \frac{n-k+1}{n})$. So by that $H$ is concave we have $$ \sum_{i=1}^k \frac{n_i}{n} \log \frac{n}{n_i} \geq (k-1) \frac{1}{n}\log n+ \frac{n-k+1}{n}\log \frac{n}{n-k+1} \geq \frac{k-1}{n-1} \log n. $$


1 Answer 1


Assume that $n_1,\dots,n_t<m\leqslant n_{t+1},\dots,n_k$. Denote $p_i=n_i/n$, $m/n=a$; $H(p)=-p\log p$ is entropy function, and we want to prove $$\sum H(p_i)\geqslant \frac{p_1+\dots+p_t+a(k-t-1)}{1-a}\log a^{-1}.$$ Note that $H(p)$ is concave function, thus we have $H(p_i)\geqslant H(a)\cdot \frac{p_i}a$ for $i\leqslant t$ and $H(p_i)\geqslant H(a)\cdot \frac{1-p_i}{1-a}$ for $i>t$. Substituting these estimates for $H(p_i)$ to LHS and simplifying we get exactly RHS.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .