Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have random variable $X=\{x_1,\cdots,x_n\}$ with probability mass function $p$.

The entropy is defined by


where $b$ is any integer $\geq 2$.

Now suppose there is a $k$-partition $X=\bigcup_{j=1}^kX_j$, do we have the following inequality?

$$\frac{1}{n}\sum_{j=1}^k | X_j |\; H(X_j)\leq H(X)$$

i.e, the weighted mean of the entropy of these parts is less than the entropy of the whole.

share|cite|improve this question
Motivation? Are you sure you want the weight? The property is true for the unweighted mean, more specifically $H = \frac{1}{k}\sum_{j=1}^k H_j + \log k$. – leonbloy Mar 30 '14 at 12:46
@Kaa1el: How's $H(X_j)$ defined? – Ashok Mar 31 '14 at 4:23
@Ashok: $H(X_j)$ is the same as $H(X)$ except we substitute $X$ with $X_j$ and we multiply $p$ by a factor $\frac{n}{|X_j|}$. – Kaa1el Mar 31 '14 at 6:36
@leonbloy Thanks for your answer. Actually I was going to write a program depending on this. (I know essentially nothing about probability theory and information theory). Now I've found a way not using this fact in my program, so I don't need that conjecture anymore, although I hope it is true. – Kaa1el Mar 31 '14 at 6:44
what do you mean by random variable $X = \{x_1, \cdots, x_n \}$? is it a random vector? or are those possible values that $X$ takes? – Memming Mar 31 '14 at 12:37
up vote 2 down vote accepted

In general, the inequation is false.

Take for example two sets, the first one with $M\gg 1$ elements and $p(x_i)= \epsilon\ll1/M$, the second with a single value. Then the global entropy $H(X)$ is near zero, while the weighted entropy will be dominated by the entropy of the first set, which is $\log_2 M$

Say: $M=1024$, $\epsilon=10^{-6}$. Then $H(X)=0.0214...$ bits, the weighted average is $9.99...$, and the inequality is false.

What is true is the following:

$$\sum \alpha_i H(x_i) = H(X) -H({\bf \alpha}) \le H(X)$$

where the coefficients of the weighted average ${\bf \alpha} = \{\alpha_i\}$ (with $\alpha_i\ge 0$ and $\sum \alpha_i = 1$) are given by $\alpha_i = \sum_{x_j \in X_i} p(x_j)$, i.e, they are not proportional to the support size of each set but to the accumulated probability of each set.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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