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

The entropy is defined by

$$H(X)=\sum_{i=1}^np(x_i)\log_b(p(x_i)^{-1})$$

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.

-
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

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.

-