Properties of Entropy

Shannon’s theory

  • Theorem: \[ H(X,Y)\leq H(X)+H(Y)\\ let\ H(X)+H(Y)-H(X,Y)\\ =\sum_{x_{i}}Pr(x_{i})lb(\frac{1}{Pr(x_{i})})+\sum_{y_{j}}Pr(y_{j})lb(\frac{1}{Pr(y_{j})}-H(X,Y))\\ =\sum_{x_{i}}lb(\frac{1}{Pr(x_{i})})\sum_{y_{j}}Pr(x_{i},y_{j})+\sum_{y_{j}}lb(\frac{1}{P(y_{j})})\sum_{x_{i}}Pr(x_{i},y_{j})-H(X,Y)\\ =\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})lb(\frac{1}{Pr(x_{i})Pr(y_{j})})-\sum_{x_{i},y_{j}}Pr(x{i},y_{j})lb(\frac{1}{Pr(x_{i},y_{j})})\\ =\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})lb(\frac{Pr(x_{i},y_{j})}{Pr(x_{i})Pr(y_{j})})\\ =-\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})lb(\frac{Pr(x_{i})Pr(y_{j})}{Pr(x_{i},y_{j})})\\ \] Since we have Jensen inequation, the formula above \[ \geq -lb(\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})\frac{Pr(x_{i})Pr(y_{j})}{Pr(x_{i},y_{j})})\\ =-lb(\sum_{x_{i},y_{j}}Pr(x_{i})Pr(y_{j}))\\ =-lb(\sum_{x_{i}}Pr(x_{i})\sum_{y_{j}}Pr(y_{j}))\\ =-lb(1)=0\\ \] To prove the theorem: \[ H(X,Y)=H(Y)+H(X|Y)\\ consider\ H(X|Y)=\sum_{y_{j}}Pr(y_{j})H(X|y_{j})\\ =\sum_{y_{j}}Pr(y_{j})(-\sum_{x_{i}}Pr(x_{i}|y_{j})lb(Pr(x_{i}|y_{j})))\\ =-\sum_{x_{i},y_{j}}Pr(y_{j})Pr(x_{i}|y_{j})lb(Pr(x_{i}|y_{j}))\\ =-\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})lb(Pr(x_{i}|y_{j}))\\ =-\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})lb(\frac{Pr(x_{i},y_{j})}{Pr(y_{j})})\\ =-\sum_{x_i,y_{j}}Pr(x_{i},y_{j})lb(Pr(x_{i},y_{j}))-(-\sum_{x_{i},y_{j}}Pr(x_{i},y_{j})lb(Pr(y_{j})))\\ =H(X,Y)-(-\sum_{y_{j}}lb(Pr(y_{j}))\sum_{x_i}Pr(x_{i},y_{j}))\\ =H(X,Y)-(-\sum_{y_{j}}Pr(y_{j})lb(Pr(y_{j})))\\ =H(X,Y)-H(Y)\\ \therefore H(X,Y)=H(Y)+H(X|Y)\\ \] To prove: \[ H(X|Y)\leq H(X)\\ \because H(X,Y)\leq H(X)+H(Y)\\ and\ H(X,Y)=H(Y)+H(X|Y)\\ \therefore H(Y)+H(X|Y)\leq H(X)+H(Y)\\ i.e. H(X|Y)\leq H(X)\\ Q.E.D.\\ \]

Key Equivocation

\[ H(C,K,P)=H(C|K,P)+H(K,P)=H(K,P)=H(K)+H(P)\\ Similiarly,\ H(C,K,P)=H(C,K)=H(K|C)+H(C)\\ \therefore H(K|C)=H(C,K)-H(C)=H(C,K,P)-H(C)=H(K)+H(P)-H(C)\\ \]