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.

Let $p_{ij}=P(X=i,Y=j)$ be the joint distribution, $P(X=i)=p_i=\sum_j p_{ij}, P(Y=j)=q_j=\sum_i p_{ij}$ be the marginal distributions, and $p_{i|j}=\frac{p_{ij}}{q_j}$ be the conditional distribution. Then the conditional entropy is defined as $$E[h(X|Y)]=-\sum_j \sum_i p_{i|j} \ln p_{i|j} q_j $$ Show $E[h(X|Y)]\leq h(X)$ where $h(X)$ is the entropy of $X$. I'm at a lost as to even know where to begin.

share|improve this question
    
Check if this recent post #69859 is of interest... –  Sasha Oct 5 '11 at 19:23
    
They're similar, but that post deals with relative entropy and this is conditional. –  bret Oct 5 '11 at 19:45
add comment

1 Answer

First, you give an incorrect definition for $\mathbb{E}(h(X|Y))$. It should instead read as follows: $$ \mathbb{E}(h(X|Y)) = - \sum_j q_j \sum_i p_{i|j} \ln p_{i|j} $$

Define relative information $I(X, Y) = H(X) - \mathbb{E}(h(X|Y))$. Then $$I(X,Y) = - \sum_i p_i \ln(p_i) + \sum_{j,i} p_{i|j} q_j \ln p_{i|j} = - \sum_{i,j} p_{i,j} \ln(p_i) + \sum_{j,i} p_{i,j} \ln p_{i|j} $$ hence $$ I(X,Y) = \sum_{i,j} p_{i,j} \ln \frac{p_{i,j}}{p_i q_j} $$ The function $\varphi(x) = x \ln(x)$ is convex for $x>0$. Thus, using Jensen's inequality:

$$ I(X,Y) = \sum_{i,j} p_i q_j \cdot \varphi\left( \frac{p_{i,j}}{p_i q_j} \right) \ge \varphi\left( \sum_{i,j} p_i q_j \cdot \frac{p_{i,j}}{p_i q_j} \right) = \varphi(1) = 0 $$

share|improve this answer
    
It is noteworthy that in order to invoke Jensen's inequality, the coefficients must sum up to 1. This is true in this case since $\sum_{i,j} p_iq_i = \sum_i p_i \sum_j q_j = 1$. –  Sinan Taifour Nov 21 '13 at 20:40
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.