2.4.RELATIVE ENTROPY AND MUTUAL INFORMATION Proof. HXIY)-H(X)=-∑P(e,)log P()+∑Pe)ogPe) (E.)ES:v Es. =∑Pe,losP P(r) ￡Pus2 P(E,) r≤罗P(29-小 (∑PaPe-∑re,)loge ≤P(x)P()-1loge =(1-1)loge =0 Note that,however H(XY=y)may exceed H(X). Theorem(Independence bound on entro)Letedra to P(X1,X2.XN).Then H(K,X2,Xw)≤∑HX) n=1 with equality if the n are independent. Proof.By the chain rule for entropies, N 0)=空- s∑Hx) (2.13) 2.4 Relative entropy and mutual information 2.4.1 Relative entropy The relative entropy is a measure of the"istance"between two distributions. Definition 2.4.1.The relative entropy (or Kullback Leiber distance)between two pmf P(r)and Q(r)is defined as2.4. RELATIVE ENTROPY AND MUTUAL INFORMATION 15 Proof. H(X|Y ) − H(X) = − ∑ (x,y)∈Sxy P(x, y) log P(x|y) + ∑ x∈Sx P(x) log P(x) = ∑ x,y P(x, y) log P(x) P(x|y) = ∑ x,y P(x, y) log P(x)P(y) P(x, y) (by IT-inequality) ≤ ∑ x,y P(x, y) ( P(x)P(y) P(x, y) − 1 ) log e = (∑ x,y P(x)P(y) − ∑ x,y P(x, y) ) log e ≤   ∑ x∈X,y∈Y P(x)P(y) − 1   log e = (1 − 1) log e = 0 Note that, however H(X|Y = y) may exceed H(X). Theorem 2.3.5 (Independence bound on entropy). Let X1, . . . , XN be drawn according to P(X1, X2, . . . , XN ). Then H(X1, X2, . . . , XN ) ≤ ∑ N n=1 H(Xn) with equality iff the Xn are independent. Proof. By the chain rule for entropies, H(X1, X2, . . . , XN ) = ∑ N n=1 H(Xn|X1, . . . , Xn − 1) ≤ ∑ N n=1 H(Xn) (2.13) 2.4 Relative entropy and mutual information 2.4.1 Relative entropy The relative entropy is a measure of the “distance” between two distributions. Definition 2.4.1. The relative entropy (or Kullback Leiber distance) between two pmf P(x) and Q(x) is defined as D(P||Q) = ∑ x∈X P(x) log P(x) Q(x) = Ep [ log P(x) Q(x) ]