I have to prove the chain-rule for conditional entropy. I kept getting stuck on one step, so I looked up a proof and found this: \begin{align}H(Y\mid X)&= \sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log \frac {p(x)} {p(x,y)}\tag{1}\\&= -\sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log\,p(x,y) + \sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log\,p(x) \tag{2}\\ &= H(X,Y) + \sum_{x \in \mathcal X} p(x)\log\,p(x)\tag{3}\\ &= H(X,Y) - H(X)\tag{4}\end{align}

This is identical to the proof I had made on my own, but it makes a step that I didn't think was allowed. Specifically, can someone explain how you are able to move from the joint probability to the marginal probability between steps 2 and 3? It seems like I'm missing something basic and obvious, but I don't see it.


The question is phrased as whether $$ \sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log\,p(x) = \sum_{x \in \mathcal X} p(x)\log\,p(x) \quad \text{?} $$

I disapprove of using the same symbol, $p$, for two different functions. If one instead writes $p_X(x)$ with capital $X$ and lower-case $x$ in the appropriate places, one can then understand such things as the difference between $p_X(4)$ and $p_Y(4)$, and the meaning of $p_X(4)$, and things like $\Pr(X\le x)$.

We have \begin{align} & \sum_{\begin{smallmatrix} x\in\mathcal X \\ y\in\mathcal Y \end{smallmatrix}} \Pr(X=x\ \&\ Y=y) \log p(x) & & \text{where $p(x)$ is some function of $x$} \\[10pt] = {} & \sum_{x\in\mathcal X} \left( \sum_{y\in\mathcal Y} \Pr(X=x\ \&\ Y=y) \log p(x) \right) & & \text{where $p(x)$ is some function of $x$.} \end{align}

The factor $\log p(x)$ within the sum $\displaystyle\sum_{y\in\mathcal Y}$ does not depend on $y$, i.e. it does not change as $y$ runs through the list of all members of $\mathcal Y$. Therefore we can pull it out, getting this: $$ \sum_{x\in\mathcal X} \left( (\log p(x)) \sum_{y\in\mathcal Y} \Pr(X=x\ \&\ Y=y) \right) $$ Now all we need to do is show that $$ \sum_{y\in\mathcal Y} \Pr(X=x\ \&\ Y=y) = \Pr(X=x). $$ For example, if $\mathcal Y=\{y_1,y_2,y_3\}$, we would need to show that $$ \Pr(X=x\ \&\ Y=y_1) + \Pr(X=x\ \&\ Y=y_2) + \Pr(X=x\ \&\ Y=y_3) = \Pr(X=x). $$ Can you do that?


Simply because $$ \sum_{y\in\mathcal Y}p(x,y)= p(x). $$ Really, you had done all difficult work already.

  • $\begingroup$ I realize now that I did essentially that in another proof in the assignment. Just so I'm sure, there's no problem in saying: \begin{align}&=\sum_{j=1}^{m}q_j\big(-\sum_{i=1}^{n}\mathbb{P}(P=i)\log\mathbb{P}(P=i)\big)\tag{$P\independent Q$)}\\&=\big(\sum_{j=1}^{m}q_j\big)\cdot\big(-\sum_{i=1}^{n}\mathbb{P}(P=i)\log\mathbb{P}(P=i)\big)\tag{factoring}\\&=\big(1\big)\cdot\big(-\sum_{i=1}^{n}\mathbb{P}(P=i)\log\mathbb{P}(P=i)\big)\tag{By definition, all $q_j$'s sum to 1}\end{align} $\endgroup$ – Alex Feb 6 '16 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.