An inequality about entropy

145 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.