Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|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 at 12:46
    
@Kaa1el: How's $H(X_j)$ defined? –  Ashok Mar 31 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 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 at 6:44
1  
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 at 12:37
show 1 more comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.