1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is $H$?$\ $ $\endgroup$ – Ian Coley Mar 14 '14 at 4:56
  • $\begingroup$ I'm guessing it's the entropy of a discrete random variable. $\endgroup$ – Philip Hoskins Mar 14 '14 at 4:57
  • $\begingroup$ Yes. It is entropy. I will edit it. $\endgroup$ – LSZ Mar 14 '14 at 4:58
  • $\begingroup$ 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. $\endgroup$ – Philip Hoskins Mar 14 '14 at 5:13
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – LSZ Mar 14 '14 at 6:51
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nice illustration. $\endgroup$ – LSZ Apr 3 '14 at 4:10
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.