Information Theoretic Inequalities - Isl.stanford.edu

DEMBO et al.: INFORMATION THEORETIC INEQUALITIESthe fact that g and 4K yield the same expectation of thequadratic form In K( ).qB. Subset Inequalities for EntropyMotivated by a desire to prove Szasz’sgeneralization ofHadamard’s inequality in Section V, we develop a newinequality on the entropy rates of random subsets ofrandom variables.Let Xi, X2, .‘. . , X,, be a set of n random variables withan arbitrary joint distribution. Let S be any subset of theindices { 1,2, * * *, n). We will use X(S) to denote thesubset of random variables with indices in S and S” todenote the complement of S with respect {1,2, * . . , n}. Forexample, if S {l, 3], then X(S) IX,, X,] and XC?‘) {X2, &,X5,. *, X,}. Recall that the entropy h(X) of arandom vector X E.R with density function f(x) ish(X) -jf(x)Inf(x) h(xi,,xi,,***,xi,).vw))ibkk S:lSI k( 1be the entropy rate per element for subsets of size kaveraged over all k-element subsets. Here, h(kn) is theaverage entropy in bits per symbol of a randomly drawnk-element subset of {Xi, X2,. * *, XJ. This quantity ismonotonically nonincreasing in k as stated in the following theorem (due to Han [27]).h(kn) Theorem 1:4-1 n h(X ,X2,.,X -l,Xi .,X )cn-1’ i *) (2)which is the desired result h’,“’ I h’,“l 1.We now prove that h(kn)I h ‘? i for all k I n, by firstconditioning on a k-element subset, then taking a uniform choice over its (k - l&element subsets. For eachk-element subset, h(kk)I hikjl, and hence, the inequalityremains true after taking the expectation over all k-element subsets chosen uniformly from the n elements.qCorollary 1: Let r 0, and define O - lceWW(O/k) .( ii 1(3)S: ISI kp&p2.* &p.(4)Proof: Starting from (2) in Theorem 1, we multiplyboth sides by r, exponentiate, and then apply the arithmetic-mean, geometric-mean inequality to obtaine(l/n)rh(X,,Xz;.,X ,, el/n .: ,(rh(X,,X2;.,X,-,,X, ,,.,Xnj/n-1)-s--1 nCe(rh(X1,Xzr.,X,-l,Xj lr.,X,)/n--1)n i lfor all r 2 0,(5)which is equivalent to 2) I s ttl. Now we use the samearguments as in Theorem 1, taking an average over allsubsets to prove the result that for all k n, sl;“) I 2 1.qh:“‘ ) . h@)n *Proof: (Following [16]). We first prove the inequalityh””n 5 h?,. We writeX,) h(X,,X,/-,X,-,) (X,,&,.**,or05.If S Ii,, i,, . . . , ik}, leth(X(S))1503.,X,) h(X,,X,,.,X,-2,X,) h(X,-,IX,,X,,.,X,-,,X,) h(X,,X,,.,x,-,,x,) h(X,-1IX1,X2,.,Xn-2),h(X,,X, .Adding these n inequalities and using the chain rule,we obtainnh(XI,X2,- ,X,Jn5 c h(X,,X,,.,Xi- ,Xi ,.,X,)iLl h(X,,&,-.,X,)The conditional entropy rate per element for a k element subset S is h(X(S)IX(S”))/k.Definition: The average conditional entropy rate perelement for all subsets of size k is the average of theprevious quantities for k-element subsets of {l, 2, * * *, n},i.e.,gp’ -lc( It 1S: ISI kfWS)Ix(S”))k.Here, g,(S) is the entropy per element of the set Sconditional on the elements of the set SC. When the sizeof the set S increases, one could expect a greater dependence between the elements of the set S, and expect adecrease in the entropy per element. This explains Theorem 1.In the case of the conditional entropy per element, as kincreases, the size of the conditioning set SC decreasesand the entropy of the set S increases since conditioningreduces entropy. In the conditional case, the increase inentropy per element due to the decrease in conditioningdominates the decrease due to additional dependencebetween the elements and hence, we have the following

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 37, NO. 6, NOVEMBER 19911504theorem that is a consequence of the general formalismdeveloped by Han [271.Theorem 2:g!“) 5 gp - * * 5 gp.Proofi The proof proceeds on lines very similar tothe proof of the theorem for the unconditional entropyper element for a random subset. We will first prove thatg@)2 gr!r, and then use this to prove the rest of themequalities.By the chain rule, the entropy of a collection of randomvariables is less than the sum of the entropies, i.e.,h(X,,X,,**-,X,) iother determinant inequality along the lines of Szasz’stheorem; however, unlike the inequalities in the previoussection, there is no normalization by the number of elements in the subset.Letip) - lc I(X(S);X(S”))s: ISI k(: 1be the average mutual information between a subset andits complement averaged over all subsets of size k. By thesymmetry of mutual information and the definition of ip),it is clear that ip) iF’.k.Theorem 3:k h(Xi).i’,“)si’;“) i-lSubtracting both sides of this inequality from nh(X,,x*3. * *, X,), we have**a it:)21.Remark: Note that the dependence between sets andtheir complements is greatest when they are of equal size.(n-l)h(X,,X,,-J,JProofi Let k I [n /2]. Consider a particular subset Sof size k. S has k subsets of size .k - 1. Let Sj denote thesubset S -{j). Then2 2 (h(X,,X2,.,X,)-h(Xi))i lk (X(s);X(s”))- k h(X,,X,;.,Xi-,,Xi ,;.,X,lXi).j s’(X(Sj);X(sf))1i l Dividing this by n(n - l), we obtainh(X,,X,,.--,X,z)j sz(x(sj)? x(sc))-z(x(sj) x(sc) xj) j s (x(sj) x(sc)) z(xj x(sc)/x(sj))n1 n h(X,,X,,.,Xi-,,Xj ,.,X,lxi)2--cn i l-I(X(Sj);X(S’))-I(X(Sj);XjlX(S’))7n-l j sh(XjIX(Sj))-h(X;IX(Sj) X(Sc))which is equivalent to gr) 2 gr!r.We now prove that gp) 2 gp!r for all k I n by firstconditioning on a k-element subset, then taking a uniform choice over its (k - l&element subsets. For eachk-element subset, gv’ g !?r and hence, the inequalityremains true after taking the ‘expectation over all k-element subsets chosen uniformly from the n elements.0-h(XjlX(S’)) h(XjIX(S’),X(Sj)) ch(XjlX(Sj))-h(XJX(S”)).jESSumming this over all subsets of size k, we obtainCkZ(X(s);X(s”))-jI s’(X(sj) X(s ))S: ISI k [C. Inequalities for Average Mutual Informationbetween Subsets CC h(XjlX(Sj))-h(XjIX(S”)).1S:ISI kjESThe previous two theorems can be used to prove thefollowing statement about mutual information.CCorollary 2: LetfP, --Reversing the order of summation, we obtainqx(s);x(s”))Lck( k 1 S:IS[ kk (X(s);X(s”))- ejf.s’(X(sj);X(sf))S: ISI k [’C1h(XilX(Sj))-h(XjlX(SC))j lS:ISI k,SsjThen,fp2 fi’“‘r. . * f Cn)- n ’Proof: This result follows from the identity1(X(S); X(S’) h(X(S)) - h(XW(X(F))and Theorems 1 and 2.0We now prove an inequality for the average mutualinformation between a subset and its complement, averaged over all subsets of size k in a set of randomvariables. This inequality will be used to prove yet an- I?j lh(XjIX(S’))cS’:I,S’l k-l,S’s j-h(XjIX((S’U aj}‘))h(XiIX( S’))cj lLS’:S’c(jJC,IS’I k-1-h( XjlX( s”))c9’: S” c[jF, -IS”1 n - kI* (6)

DEMBO etal.:INFORMATIONTHEORETICINEQUALITIES1505Since k I [n/2], k - 1 n - k. So we would expect normal counterparts, has a strong formal resemblance tothat the second sum in (6) to be less than the first sum, the Brunn M inkowski inequality, which says that thesince both sums have the same number of terms but the volume of the set sum of two sets is greater than or equalsecond sum corresponds to entropies with more condi- to the volume of the set sum of their spherical countertioning. We will prove this by using a simple symmetry parts. Both are interpreted here as convexity inequalitiesargument.for RCnyi entropies that measure the uncertainty associThe set S” with n - k elements has 21: subsets of ated with a random variable X via the pth norm of its(1size k - 1. For each such subset S’ of size k - 1, we have density (see Section III-A). A strengthened version ofYoung’s inequality about the norms of convolutions ofh(XjlX(S”)) Ih(XjlX(S’)),(7) functions, due to Beckner [3] and Brascamp and Lieb [8]since conditioning reduces entropy. Since (7) is true for is equivalent to a more general convexity inequality, witheach subset s’ c s”, it is true of the average over subsets. both the entropy power and the Brunn-Minkowski inequality being extreme points (see Section III-B).Hence,This proof of the entropy power inequality (due to Lieb[30])is different from Stam’s [38] proof, which relies uponh(XjlX(S'))*caconvexityinequality for Fisher information. NevertheS’:S’cS”,\S’I k-1less, the interpretation of the entropy power inequality asa convexity inequality for entropy allows for a new, simplerversion of Stam’s proof, presented here in SectionSumming (8) over all subsets S” of size IZ- k, we getIII-C.Ch(,“))Isoperimetric versions of the entropy power and theS”: lS”j n - kFisher information inequalities have derivations that parallel the classical derivation of the isoperimetric inequalh( xjlx(s’))city as a consequence of the Brunn-Minkowski inequalityS’: S’CS”, IS’1 k-1(see Section III-D following Costa and Cover [14] andDembo [191).(8)xjlx( C(9)h(XjlX(S')),S’: IS’I k-1sincebysymmetry,(,-,:,) (;Z:)each subsetS’ occursinsets S”.Combining (6) and (9), we getckZ(X(S);X(S”))-cZ(X(S,);X(S;))jESS: ISI k2 0.ISince each set of size k - 1 occurs n - k 1 times in thesecond sum, we havecA. Entropy Power and Brunn - Minkowski InequalitiesThe definition of the entropy power and the associatedentropy power inequality stated next are due to Shannon[37]. The entropy power inequality is instrumental inestablishing the capacity region of the Gaussian broadcastchannel ([5]) and in proving convergence in relative entropy for the central lim it theorem ([2]).Definition: The entropy power of a random vector X ER” with a density iskZ(X(S);X(S”))S: ISI k2N(X) &expCS:ISI kiESCz(x(sj);x(sf)) (n-k l)cZ(X(S’);X(S’“)).S’:IS’I k-1Dividing this equation by k(i),1we have the theoremiih(X)i.In particular, N(X) JKll’” when X K.Theorem 4 (Entropy Power Inequality): If X, Y are twoindependent random vectors with densities in R” andboth h(X) and h(Y) exist, then,N(X Y)av(X) N(Y).(10)Equality holds iff X and Y are both multivariate normalwith proportional covariances.III. THEENTROPYPOWERANDANALYTICALRELATEDINEQUALITIESThe entropy power inequality, which says that the ‘entropy of the sum of two independent random vectors is noless than the entropy of the sum of their independentIn the sequel (see Section III-C), we shall present asimplified version of Stam’s first proof of this inequality(in [381) as well as a less known proof due to Lieb [30].The next matrix inequality (Oppenheim [36], Marshalland Olkin [32, p. 4751) follows immediately from theentropy power inequality when specialized to the multivariate normal.

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 37, NO. 6, NOVEMBER 19911506Theorem 5 (Minkowski’sInequality[341): For any twononnegative definite matrices K,, K,[K, Kzll’” 2 lK ‘” IKZll’ ,with equality iff K, is proportional to K,.Proof: Let X1,X, be independent with Xi N 4K,.Noting that X, X, N K, K, and using the entropypower inequality yieldsIK, Kzll’nRemark: See Section V-A for an alternative information theoretic proof of both Theorems 5 and 8, whichavoids the entropy power inequality.The entropy power inequality has a strong formal resemblance of the Brunn-Minkowski inequality. For defining the latter, let p denote Lebesgue measure in Rn (i.e.,set volume in Rn) and A B denote the M inkowski sum(in Rn) of the (measurable) sets A and B, that isA B {x y:x A,y0}. N( X, X,)Theorem 9 (Brunn-Minkowski2 N(-X,) N( X,) lK “”,u(A B)l’n p(A)l’n (B)*‘n.0 IK211?Inequality 1241)(14)Proof: For a very simply geometric proof, see [24].An alternative proof of this inequality as an extreme pointof Young’s inequality (which is due to Brascamp andTheorem 6: For any two independent random vectors Lieb, see [71 and [91 is presented in Section III-B.X, Y such that both h(X) and h(Y) exist,The entropy power is a measure of the effective variance of a random vector while p(A l/” measures theh(X Y)rh(2 ),weffective radius of a set A. Thus, the entropy powerwhere 2, Y are two independent multivariate normal with inequality, which says that the effective variance of theproportional covariances, chosen so that h(i) h(X) and sum of two independent random vectors is no less thanh(f) h(Y).the sum of the effective variances of these vectors, is theProof: For X and Y multivariate normal, M inkowski’s dual of the Brunn-Minkowski inequality, which says thatinequality and the entropy power inequality (lo), hold the effective radius of the set sum of two sets is no lessthan the sum of the effective radii of these sets. In thiswith equality. Furthermore, X and Y are chosen so thatformal duality normal random variables are the analog ofballs (being the equality cases for the previously menN(X f) N(X) N(E) N(X) N(Y)IN(x Y),tioned inequalities), and the sum of two independentwhere the last inequality follows from (10). Thus (10) and random vectors is the analog of the M inkowski sum of(11) are equivalent.qsets. This analogy is suggestedin [14], where the existenceofa family of intermediate inequalities is conjectured.Alternatively, the entropy power inequality alsoWeshall further develop this issue here and show inamounts to the convexity of the entropy under the “coSectionIII-B that Young’s inequality is the bridge bevariance preserving transformation” fix JGiYastweentheentropy power and the Brunn-Minkowski infollows.equalities. The following family of Renyi entropies helpsin illustrating these relationships.Theorem 7: For any 0 I h I 1,Definition: The pth R&yi entropy h,(X) of a randomh(&X mY)-Ah(X)-(l-h)h(Y) O.(12) variable X with density f in R” is defined byThe following alternative statement of the entropypower inequality is given in Costa and Cover [14].Proof: For X and Y the inequality (12) holds triviallywith equality. Therefore, (12) is equivalent toh,(X) &lnE[f(X)‘“-“1 &l”(“fll,),h(fiX fiY)rh(&b f),(15)The latter inequality is merely (11) with fixfor X and flYsubstituted for Y.substituted0Remark: Theorem 7 parallels part of Lieb’s proof ofTheorem 4 (in [30]).In parallel with the above derivation of M inkowski’sinequality, the following theorem due to Ky Fan [22]results from specializing (12) to the multivariate normal.Theorem 8 (1;;: Fan D2])In IK I is concave.h,(X) ji,mohhp(X) lnp({X:0f(x) 0}),(16)andh,(X) Proofi Consider (12) for X N 4K1 and Y N 4K2. Then,is also multivariate normal with covaridTx diTYante AK, (1 - h)K,, and (12) becomeslnIAK, (l-A)K,I hln(K,] (l-A)ln]K-J.for 0 p w, p 1, where IIf (Ip [ Jf(x)p&ll/P.TheRCnyi entropies for p 0 and p 1 are defined as thelim its of h,(X) as p 0 and p - 1, respectively. It follows directly from the previous definition that!Ln, h,(X) h(X).F ‘-(1-J)Therefore, the (Shannon) entropy is identified with theRenyi entropy of index p 1, while the logarithm of theessential support of the density is identified with the(13) RCnyi entropy of index p 0.

REMBO et al.: INFORMATION THEORETIC INEQUALITIES1507A convexity inequality for Renyi entropies of indexp 0, which is the dual of (121, is the following.Theorem 11 (Young’s Inequality):then for 1 I r, p, q 2 0,If l/r 1 l/q l/p,Theorem 10: For any 0 5 A 5 1 and any two independent random vectors X, Y, {(ll.f*RIII)/(Il IlpllYiiy)) 5 (cpC*/C,y2.(20)g L;(R”)h,(AX (l-A)Y)-Ah,(X)-(1-h)h,(Y) O.(18)Here,Remarks:cp (p)l’P/a) While Theorem 7 deals with convexity under the“variance preserving transformation” fiX fiY,this theorem deals with convexity underthe “support size preserving transformation” AX (l- A)Y.b) The proof of Theorem 10 is deferred to SectionIII-B. A family of convexity inequalities for RCnyientropies is derived there as consequences ofYoung’s inequality and both Theorems 7 and 10 areobtained as extreme (limit) points. Here we deriveonly the Brunn-Minkowski inequality as a consequence of Theorem 10.Proof of Theorem 9: Choose a pair of independentrandom vectors X and Y in R” such that the support ofthe density of AX is the set A and the support of thedensity of (l- A)Y is B. Clearly, the support of thedensity of AX (1 - h)Y is the (essential) M inkowski sumA B, while (l/A)A and (l/(1 - A))B are the supportsets of the densities of X and Y, respectively. Therefore,taking (16) into account, the inequality (18) specializes forthese random vectors toIpl(l’P’,where p’ is the Holder conjugate of p (i.e., l/p l/p’ 1) and cq and c, are likewise defined. The converseinequality holds for the infimum of Ilf*gll,./ Ilfll,,llgll,whenO r,p,q l.Remark: For the multivariate normal densities f hK,and conseand g 4(1-A)K, (where A (l/p’)/(l/r’),quently 1 - A (l/q’)/(l/r’)),Young’s inequality reduces to K. Fan’s matrix Theorem 8. Actually, (20) isestablished in [8] by showing that the supremum isachieved by multivariate normal densities, where the constants in the right side of (20) are determined by applyingK. Fan’s matrix Theorem 8. For a detailed study of casesof equality in this and related inequalities see [311.The following convexity inequality for RCnyi entropies(which is the natural extension of Theorem 7) is a directconsequence of Young’s inequality.Theorem 12: For anyO r a,r#l and anyOIA 1, let p,q be such that l/p’ Al/r’ and l/q’ (l- All/r’, th en f or any two independent random vectorsX, Y with densities in R”,h,(fiX mY)-Ah,(X)-(l-A)h,(Y)In,u((A B) 2 AInp((l/A)A)rh,( ,)-Ah,( ,)-(l-A)h,( ,), (l-A)ln ((l/(l-A))B).(19)Observing that In p((l/A)A) In p(A) - n In A andIn p((l/(l - h)jB) In p(B) - iz In (1 - A , the BrunnM inkowski inequality results when rearranging the aboveinequalityfor the particularchoice of A &4 1’“/(&4 1’” /L(B ‘“ .provided that both h,(X)There is a strong formal resemblance between theconvexity inequalities (12) and (18) (where the formeryields the entropy power inequality while the latter resultsin the Brunn-Minkowski inequality). This resemblancesuggeststhe existence of a family of intermediate inequalities. Young’s inequality, which is presented in the sequel,results after few manipulations with these inequalities(see (21)). In particular, we follow Lieb’s (in [30]) andBrascamp and Lieb’s (in [9] approach in regarding andproving Theorems 7 and 10 (respectively) as lim its of (21).For that purpose let L,(P) denote the space of complex valued measurable functions on R” with Ilfll, coand let f*g(x) /f x - y)g(y) dy denote the convolutionoperation.The following sharp version of Young’s inequality isdue to Beckner [3] and Brascamp and Lieb [8].and h,(Y) exist.Here, 41 stands for the standard normal density in R’.In establishing the inequality (21) we use the well-knownscaling property of RCnyi entropieshp(aX) hp(X) nlnlal.0B. Young’s Inequality and Its Consequences(21)(22)This identity follows from the definition in (15) by achange of variable argument.Proof: Fix r and A. We plan to apply Young’s inequality for f the density of fix and g the density ofJ1-hY. Since h,(X) and h,(Y) are well defined, so areh,(fiX) -p’lnIlfll, h,(X) lnAandh,(mY) -q’ln g /, h,(Y) ln(l-A).These identities are applications of (15) and (22), and inparticular they imply that f E L,(R”) and g E L,(Rn).Further, since X and Y are assumed independent,- r’lnllf gllr h,(fiX fiY).Observe that p, q in Theorem 12 are such that l/p’ l/q’ l/r’ (so that l/r 1 l/q l/p), and l/r’ 0

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 37, NO. 6, NOVEMBEF 19911508implies 0 r,p,q 1, while l/r’ 0 implies 1 r,p,q.Therefore, Theorem 11 is applicable for f and g, resulting in- ‘1n{(llf* ll, /(ll Il,ll ll,)} - r’ ln(c,c,/c,).(23)This inequality holds with equality for f 4*, and g &-A), (i.e., X - 41, Y N r) since for any p # 0, p # 1where H(A) 4 - A In A - (1 - A)ln(l - A). Combiningthis lim it with (2.5)yieldsh,(fiX dl-Y) Ah,(X)-(1-A)h,(Y) (A).Inequality (18) is now obtained by the resealing X fixand Y - m Y(using the scaling property (22)): Thiscompletes the proof of Theorem 10.0Remarks:(24)Combining all these identities, the inequality (23) resultsin (21).0We now show that the convexity Theorems 7 and 10(i.e., the inequalities (12) and (18) respectively) are theextreme lim it points r 1 and r - 0 of the RCnyi entropyconvexity Theorem 12.Proof of Theorem 7: Fix 0 A 1, and assume thath(X) and h(Y) are well defined. Further assume that (21) holds for some r0 f 1. Then, Theorem 12 holds for anychoice of r between r0 and 1 (i.e., the entropies h,(X)and h,(Y) exist for the resulting p and q . It is easilyverified that r --) 1 with A fixed implies that p 1 andq - 1. Therefore, by the continuity of entropies (17) inthe lim it as r 1, the inequality (21) reduces to (12), thus0completing the proof of Theorem 7.Proof of Theorem 10: Again fix 0 I A I 1. Nowassume that h,(X) and h,(Y) are well defined and that(21) holds for some r0 1. Then Theorem 12 holds forany choice of r between r0 and 0 (i.e., the entropiesh,(X) and h,(Y) exist for the resulting p and q). Further, as r-0,also p l/(l-A(l-l/r)) 0and q l/(1 --cl- A)(1 - l/r) 0. Thus, in the lim it r 0, theinequality (21) reduces by (16) toh,(fiX flY)-Ah,(X)-(l-h)h,(Y)1 5 lim r i l-rAInA-rln1-1-PP (1-A)In11-q4 1’(25)where the right-hand equality is in view of (24).Note that A /(l - p) (1 - A)/(1 - q) (1 r)/(l - r)and lim ,,, (r/p) A while lim ,,, (r/q) (1 - A).Therefore,F31-lnl--i 1- rAr-Ini--1-P& (1-A)P1-qAl-pr H(A) Riolim &lnr H(A),lnp-In14 1(l-h) (l-q)rlnqa) The proof of Theorem 7 follows Lieb’s proof of theentropy power inequality (see [30]).b) In [9], Brascamp and Lieb prove the PrCkopaLiendler inequality/s:p(f( )l-Ag(

Amir Dembo, Thomas M. Cover, Fellow, IEEE, and Joy A. Thomas, Member, IEEE Invited Paper Abstract-The role of inequalities in information theory is . quence of inequalities found by Hadamard and Szasz. By turning our attention from the historically necessary inequalities to the natural set of inequalities suggested by information theory .