Introduction to Information Theory Information must not be confused with meaning The semantic aspects of communications are irrelevant to the engineering aspects Sh48 Information is a measure of one s freedom of choice and is measured by the logarithm of the number of choices Tossing of a coin gives two choices If the logarithm is with respect to base 2 we have unit information called a bit With doubling of choices you have an extra bit of information Thus 4 8 16 choices lead to 2 3 4 bits respectively of information In general if you have N choices the information content of the situation is log 2 N which is the number of binary digits to encode the number N The above situation can be captured by using probability Since each event is assumed to be independent the probability of the ith 1 i N event is pi 1 N All events are assumed to be equally probable and the amount of information associated with the occurrence of this event or self information is given by log pi If pi 1 then the information is zero certainty and if pi 0 it is infinity if pi equals 0 5 it is one bit corresponding to N 2 If N 4 pi 0 25 and the information is 2 bits and so on Note in the case of tossing of a coin there are two possible events head or tail If you consider the tossing of the coin to be an experiment the question is how much total information will this experiment have This can be quantified if we can describe the outcome of the experiment in some reasonable fashion Lets encode the outcome head to be represented by the bit 1 and outcome tail by the bit 0 Thus a minimal description of this experiment needs only one bit Note the experiment is the sum total of all the events If we take the self information of each event multiply this by its probability and sum it up over all the events intuitively that gives a measure of information content or average information of the experiment It just so happens that this entity is also just one bit for the tossing event since the probability of either head or tail is 0 5 and self information for each event is also 1 bit This 1 bit also expresses how uncertain we are of the outcome How do you generalize the definition Suppose we have a set of N events whose probabilities of occurrence are p1 p2 pN Can we measure how much choice is involved or how much uncertain we are of the outcome Such a measure is precisely the entropy of the experiment or source denoted as H p1 p2 pN More precisely it is called the first order entropy Higher order entropies depend on contextual information The true entropy is infinite order entropy But by popular use entropy most often refers to first order entropy unless stated otherwise Read the discussion from Sayood pp 14 16 It is reasonable to require the following properties of H 1 H should be continuous in p that is a small change in the value of pi should cause small change in the value of H 1 2 If pi 1 N then H should be a monotonic increasing function of N That is with equally likely events there is more choice or uncertainty when there are more possible events 3 If a choice is broken down into two successive choices the original H should be weighted sum of the individual values of H Thus we require H 1 2 1 3 1 6 H 1 2 1 2 1 2H 2 3 1 3 Figure taken from ShW98 Theorem 1 The only H satisfying the above assumptions is H pi log pi Proof See ShWe00 Appendix 2 or Saywood pp 18 22 The form of H is recognized as that of entropy in statistical mechanics and thermodynamics and the H is the Boltzmann s famous H theorem The entropy in case of an experiment with two possibilities with probabilities p and q 1 p is H plog p 1 p log 1 p 2 1 Figure taken from ShW98 The quantity H has several interesting properties 1 H 0 iff one of the pi is 1 and the rest are 0 Thus only when we are certain of the outcome H will vanish or become 0 2 For a given N H is maximum and equals log N when all pi s are equal that is 1 N This is the most uncertain situation The above two situations are special situations of the following theorem Theorem2 The entropy H of pi 1 i N satisfies 0 H log N Proof Points 1 and 2 above prove the left and right equality We need the following inequalities to prove the inequalities ln x x 1 ln x 1 1 x log x log e x 1 log x log e 1 1 x 2 To obtain the left inequality note p log p 0 for 0 p 1 with equality if p 1 Hence H 0 To obtain the right inequality note p i 3 i 1 so we can write log N H pi log N pi log pi i i pi log N log pi i 3 pi log Np i i pi log e 1 1 i Np i and equality holds iff pi 1 i Thus we can write N log N H k pi 1 k 1 1 0 N i i where k log 2 e is a constant Thus we have the result 0 H log N 4 3 Any change toward equalization of probabilities p1 p2 pn increases H Thus if p1 p2 and we increase p1 decreasing p2 by the same amount so that these two probabilities are nearly equal then H increases In general any averaging operation will increase H Joint Probability Suppose there are two discrete events X and Y with N possibilities for X and M possibilities for Y Let p i j be the probability of the joint occurrence of i 1 i N for X and j 1 i M for Y The entropy of the joint event is H X Y p i j log p i j 5 i X j Y which is also sometimes written as H X Y p i j log p i j 6 i j Given the joint probabilities the entropy H X and H Y can be easily obtained as H X pi log pi p i j log p i j 7 H Y p j log p j p i j log p i j 8 i i j j j i since p i p i j and p j p i j j i 4 j i Homework Assignment Show that H X H Y H X Y The uncertainty of the joint event is less than equal to the sum of individual uncertainties The equality holds when the two events are independent that is p i j p i p j Conditional Probability …