Transcription of INTRODUCTION TO INFORMATION THEORY
1 1 INTRODUCTION TO INFORMATION THEORY {ch:intro_info}This chapter introduces some of the basic concepts of INFORMATION THEORY , as wellas the definitions and notations of probabilities that will be used throughoutthe book. The notion of entropy, which is fundamental to the whole topic ofthis book, is introduced here. We also present the main questions of informationtheory, data compression and error correction, and state Shannon s Random variablesThe main object of this book will be the behavior of large sets ofdiscreterandom variables. A discrete random variableXis completely defined1bythe set of values it can take,X, which we assume to be a finite set, and itsprobability distribution{pX(x)}x X. The valuepX(x) is the probability thatthe random variableXtakes the valuex.
2 The probability distributionpX:X [0,1] must satisfy the normalization conditionXx XpX(x) = 1.( ){proba_norm}We shall denote byP(A) the probability of aneventA X, so thatpX(x) =P(X=x). To lighten notations, when there is no ambiguity, we usep(x) todenotepX(x).Iff(X) is a real valued function of the random variableX, theexpectationvalueoff(X), which we shall also call the average off, is denoted by:Ef=Xx XpX(x)f(x).( )While our main focus will be on random variables taking values in finitespaces, we shall sometimes make use ofcontinuous random variablestakingvalues inRdor in some smooth finite-dimensional manifold. The probabilitymeasure for an infinitesimal element dxwill be denoted bydpX(x). Each timepXadmits a density (with respect to the Lebesgue measure), we shall use thenotationpX(x) for the value of this density at the pointx.
3 The total probabilityP(X A) that the variableXtakes value in some (Borel) setA Xis givenby the integral:1In probabilistic jargon (which we shall avoid hereafter), we take the probability space(X,P(X), pX) whereP(X) is the -field of the parts ofXandpX=Px XpX(x) TO INFORMATION THEORYP(X A) =Zx AdpX(x) =ZI(x A)dpX(x),( )where the second form uses theindicator functionI(s) of a logical statements,which is defined to be equal to 1 if the statementsis true, and equal to 0 ifthe statement is expectation value of a real valued functionf(x) is given by the integralonX:Ef(X) =Zf(x)dpX(x).( )Sometimes we may writeEXf(X) for specifying the variable to be integratedover. We shall often use the shorthandpdffor theprobability density func-tionpX(x).Example fair dice withMfaces hasX={1,2.}
4 ,M}andp(i) = 1/Mfor alli {1,..,M}. The average ofxisEX= (1 +..+M)/M= (M+ 1) variable: a continuous variableX Rhas a Gaussiandistribution of meanmand variance 2if its probability density isp(x) =1 2 exp [x m]22 2 .( )One hasEX=mandE(X m)2= notations of this chapter mainly deal with discrete variables. Most of theexpressions can be transposed to the case of continuous variables by replacingsumsPxby integrals and interpretingp(x) as a probability s inequality. LetXbe a random variable taking valuein a setX Randfa convex function ( a function such that x,yand [0,1]:f( x+ (1 y)) f(x) + (1 )f(y)). ThenEf(X) f(EX).( ){eq:Jensen}Supposing for simplicity thatXis a finite set with|X|=n, prove this equalityby recursion Entropy{se:entropy}TheentropyHXof a discrete random variableXwith probability distributionp(x) is defined asHX Xx Xp(x) log2p(x) =Elog2 1p(X) ,( ){S_def} Info Phys Comp Draft: November 9, 2007 -- Info Phys Comp Draft: November 9, 2007 -- ENTROPY3where we define by continuity 0 log20 = 0.
5 We shall also use the notationH(p)whenever we want to stress the dependence of the entropy upon the probabilitydistribution this Chapter we use the logarithm to the base 2, which is well adaptedto digital communication, and the entropy is then expressed inbits. In othercontexts one rather uses the natural logarithm (to basee ). It issometimes said that, in this case, entropy is measured innats. In fact, the twodefinitions differ by a global multiplicative constant, which amounts to a changeof units. When there is no ambiguity we useHinstead , the entropy gives a measure of the uncertainty of the randomvariable. It is sometimes called the missing INFORMATION : the larger the entropy,the less a priori INFORMATION one has on the value of the random variable. Thismeasure is roughly speaking the logarithm of the number of typical values thatthe variable can take, as the following examples fair coin has two values with equal probability.
6 Its entropy is1 throwingMfair coins: the number of all possible out-comes is 2M. The entropy fair dice withMfaces has entropy process. A random variableXcan take values 0,1with probabilitiesp(0) =q,p(1) = 1 q. Its entropy isHX= qlog2q (1 q) log2(1 q),( ){S_bern}it is plotted as a function ofqin This entropy vanishes whenq= 0orq= 1 because the outcome is certain, it is maximal atq= 1/2 when theuncertainty on the outcome is Bernoulli variables are ubiquitous, it is convenient to introduce thefunctionH(q) qlogq (1 q) log(1 q), for their unfair dice with four faces andp(1) = 1/2, p(2) =1/4, p(3) =p(4) = 1/8 has entropyH= 7/4, smaller than the one of thecorresponding fair dice. Info Phys Comp Draft: November 9, 2007 -- Info Phys Comp Draft: November 9, 2007 -- 4 INTRODUCTION TO INFORMATION THEORY 0 1 0 1H(q)qFig.
7 EntropyH(q) of a binary variable withp(X= 0) =q,p(X= 1) = 1 q, plotted versusq{fig_bernouilli}Exercise is built from a sequence of bases which are of four types,A,T,G,C. In natural DNA of primates, the four bases have nearly the samefrequency, and the entropy per base, if one makes the simplifying assumptionsof independence of the various bases, isH= log2(1/4) = 2. In some genus ofbacteria, one can have big differences in concentrations:p(G) =p(C) = ,p(A) =p(T) = , giving a smaller entropyH some intuitive way, the entropy of a random variable is relatedto the risk or surprise which are associated to it. In this example wediscussa simple possibility for making these notions more a gambler who bets on a sequence of bernouilli random variablesXt {0,1},t {0,1,2.}
8 }with meanEXt=p. Imagine he knows thedistribution of theXt s and, at timethe bets a fractionw(1) =pof his moneyon 1 and a fractionw(0) = (1 p) on 0. He looses whatever is put on the wrongnumber, while he doubles whatever has been put on the right one. Define theaverage doubling rate of his wealth at timetasWt=1tElog2(tYt =12w(Xt )).( )It is easy to prove that the expected doubling rateEWtis related to the entropyofXt:EWt= 1 H(p). In other words, it is easier to make money out ofpredictable notion that is directly related to entropy is theKullback-Leibler Info Phys Comp Draft: November 9, 2007 -- Info Phys Comp Draft: November 9, 2007 -- ENTROPY5(KL) divergencebetween two probability distributionsp(x) andq(x) over thesame finite spaceX. This is defined as:D(q||p) Xx Xq(x) logq(x)p(x)( )where we adopt the conventions 0 log 0 = 0, 0 log(0/0) = 0.
9 It is easy to showthat: (i)D(q||p) is convex inq(x); (ii)D(q||p) 0; (iii)D(q||p)>0 unlessq(x) p(x). The last two properties derive from the concavity of the logarithm( the fact that the function logxis convex) and Jensen s inequality ( ):ifEdenotes expectation with respect to the distributionq(x), then D(q||p) =Elog[p(x)/q(x)] logE[p(x)/q(x)] = 0. The KL divergenceD(q||p) thus lookslike a distance between the probability distributionsqandp, although it is importance of the entropy, and its use as a measure of INFORMATION ,derives from the following 0 if and only if the random variableXis certain, which means thatXtakes one value with probability Among all probability distributions on a setXwithMelements,Hismaximum when all eventsxare equiprobable, withp(x) = 1/M.
10 Theentropy is thenHX= in fact that, ifXhasMelements, then the KL divergenceD(p||p)betweenp(x) and the uniform distributionp(x) = 1/MisD(p||p) =log2M H(p). The thesis follows from the properties of the KL diver-gence mentioned IfXandYare twoindependentrandom variables, meaning thatpX,Y(x,y) =pX(x)pY(y), the total entropy of the pairX,Yis equal toHX+HY:HX,Y= Xx,yp(x,y) log2pX,Y(x,y) == Xx,ypX(x)pY(y) (log2pX(x) + log2pY(y)) =HX+HY( )5. For any pair of random variables, one has in generalHX,Y HX+HY,and this result is immediately generalizable tonvariables. (The proof can be obtained by using the positivity of the KL divergenceD(p1||p2), wherep1=pX,Yandp2=pXpY).6. Additivity for composite events. Take a finite set of eventsX, and decom-pose it intoX=X1 X2, whereX1 X2=.
