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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.