Does entropy $H(y)$ decrease as $H(x,y)$ decreases when $H(x)$ is fixed?

Can't find any proof in Shannon's 1948 paper. Can you provide one or disproof?

Thank you.

P.S.

$H(x)$(or $H(y)$) is the entropy of messages produced by the discrete source $x$(or $y$).

$H(x,y)$ is the joint entropy.

They are all entities in information theory.

• What is $H$?$\$ – Ian Coley Mar 14 '14 at 4:56
• I'm guessing it's the entropy of a discrete random variable. – Philip Hoskins Mar 14 '14 at 4:57
• Yes. It is entropy. I will edit it. – LSZ Mar 14 '14 at 4:58
• Well, in two cases it should be clear. If they are independent or if one depends completely on the other. The remaining case is when they are neither independent nor completely dependent. – Philip Hoskins Mar 14 '14 at 5:13

No it doesn't have to.

$H(X,Y) = H(X) + H(Y|X)$

To lower $H(X,Y)$ while keeping $H(X)$ fixed, you need to lower $H(Y|X)$. You can lower $H(Y|X)$ without lowering $H(Y)$ since $0 \leq H(Y|X) \leq H(Y)$ is a measure on how dependent X and Y is. If they are more dependent, there will be less entropy left in Y after you've learned X so $H(Y|X)$ is lower.

From the inequality above, you can also see that lowering $H(Y)$ would also lower $H(Y|X)$ which in turn lowers $H(X,Y)$, so lowering $H(Y)$ is one way but not the only way.

• A counter-example here. Let either $x$ or $y$ produces symbols of equal possibility, say, $\{A, B\}$ and $\{C, D\}$ respectively. In that case, $H(x)=H(y)=1$. If joint events $(A, C)$, $(A, D)$, $(B, C)$ and $(B, D)$ have equal possibility, $H(x,y)=2$. If only joint events $(A, C)$ and $(B, D)$ are sustained having equal possibility $0.5$, $H(x,y)=1$ decreases without decrease of $H(y)$. – LSZ Mar 14 '14 at 6:51

Both cases are possible.

 H(X)            [=========================]
H(Y)   [===============]                         (original)
H(X,Y) [==================================]

H(X)            [=========================]  constant
H(Y)        [=======]                        less than original
H(X,Y)      [=============================]  decreases

H(X)            [=========================]  constant
H(Y)        [=======================]        greater than original
H(X,Y)      [=============================]  decreases


The assertion would be true only if we state that the mutual information $I(X;Y)$ is kept constant.

• Nice illustration. – LSZ Apr 3 '14 at 4:10

The only way H(X,Y) can be reduced is to increase the correlation between X and Y. Since X will be judged on the basis of Y which decoder already have. There must be strong correlation so that decoder can predict the X on basis of Y.