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

Cross-posted at https://mathoverflow.net/q/282311/22954 on MathOverflow.

  • $\begingroup$ This looks like it can be wrangled by a convexity argument using some variant of the log function $\endgroup$ – Daron Sep 29 '17 at 13:30
  • 1
    $\begingroup$ Fedor Petrov has given a brilliant proof on MathOverflow. See mathoverflow.net/a/282344/22954 $\endgroup$ – Lwins Sep 29 '17 at 16:44
  • $\begingroup$ Please don't cross post things, especially when they're first asked. $\endgroup$ – Batman Oct 2 '17 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.