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

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|cite|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

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|cite|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

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.