5 Probability5.1 Event Space5.2 Known Outcomes5.3 Unknown Outcomes5.4 Joint Events and Conditional Probabilities5.5 Averages5.6 Information5.7 Properties of Information5.8 Efficient Source Coding5.9 Detail: Efficient Source Codes5.10 Detail: MortalityChapter 5ProbabilityWe have been considering a model of an information handling system in which symbols from an input areencoded into bits, which are then sent across a “channel” to a receiver and get decoded back into symbols,shown in Figure 5.1.Source EncoderCompressorChannel EncoderChannelChannel DecoderExpanderSource Decoder- - - - - - - -Input Output(Symbols) (Symbols)Figure 5.1: Communication systemIn earlier chapters of these notes we have looked at various components in this model. Now we return tothe source and model it more fully, in terms of probability distributions.The source provides a symbol or a sequence of symbols, selected from some set. We will consider onlycases with a finite number of symbols to choose from, and only cases in which the symbols are both mutuallyexclusive (only one can be chosen at a time) and exhaustive (one is actually chosen). The choice, or moregenerally each choice, constitutes an “outcome” and our objective is to trace the outcome, and the informationthat accompanies it, as the information travels from the input to the output. To do that, we need to be ableto express our knowledge about the outcome.If we know the outcome, we have a perfectly go od way of denoting the result. We can simply name thesymbol chosen, and ignore all the rest of the symbols, which were not chosen. However, if we do not yet knowthe outcome, or are uncertain to any degree, we do not yet know how to express our state of knowledge. Wewill use the mathematics of probability theory for this purpose.To illustrate this important idea, we will use examples based on the characteristics of MIT students. TheAuthor: Paul Penfield, Jr.Version 1.1.0, February 27, 2004. Copyrightc 2004 Massachusetts Institute of TechnologyURL: http://www-mtl.mit.edu/Courses/6.050/notes/chapter5.pdfstart: http://www-mtl.mit.edu/Courses/ 6.05 0/no tes/ index.htmlback: http://www-mtl.mit.edu/Courses/6.050/notes/chapter4.pdfnext: http://www-mtl.mit.edu/Courses/ 6.05 0/no tes/chapter6.pdf4041official count of students at MIT1for Fall 2003 led to the following data:Women Men TotalFreshmen 460 562 1022Undergraduates 1739 2373 4112Graduate Students 1798 4430 6228Total Students 3537 6803 10340Table 5.1: Demographic data for MIT, Fall 2003The demographic data in Table 5.1 is reproduced in Venn diagram format in Figure 5.2.Figure 5.2: A Venn diagram of MIT demographic data, with areas roughly proportional to the sizes of thesubpopulations involved.Supp ose an MIT freshman is selected (the symbol being chosen is an individual student, and the set ofpossible symbols is the 1022 freshmen), and you are not informed who it is. You wonder whether it is awoman or a man. Of course if you knew the identity of the student selected, you would know the gender.But if not, how could you characterize your knowledge? What is the likelihood, or probability, that a womanwas selected?Note that 45% of the 2003 freshman class consisted of women. This is a fact, or a statistic, but mayor may not represe nt the probability the freshman chosen is a woman. If you had reason to believe thatall freshmen were equally likely to be chosen, you might decide that the probability of it being a womanis 45%, but what if you are told that the selection is made in the corridor of McCormick Hall (a women’sdormitory)? Statistics and probabilities can both be described using probability theory (to be developednext), but they are different things.1all students: http://web.mit.edu/registrar/www/stat s/yreportfinal.html,all women: http://web.mit.edu/registrar/www/stat s/womenfinal.html5.1 Event Space 425.1 Event SpaceThe events we are concerned with are the selections of symbols from a set of possible symbols (for simplicity,only finite). We will use the term outcome to refer to the selection of a symbol (or our learning the resultof the selection). We also care about various properties of those symbols, and we need a way to estimate orcharacterize our knowledge of those properties. We will use the term event to refer not only to the selectionof an individual symbol, but also to the selection of a symbol contained in a set of symbols defined in someway. Thus in our example, the selection of a spec ific person from the set of 1022 freshmen is an event.However, when that selection is made (or when we learn about it) another event also happens, namely theselection of a woman (or a man). Another possible event is the selection of a person from California, orsomeone older than 18, or someone taller than six feet. Or an event can be defined using a combination ofsuch properties. As a result of each possible outcome, some of these events happen and others do not.After a selection of a symbol is made the various events that can possibly happen (which we will call anevent space) can be described using the mathematics of set theory, with its operations of union, intersection,complement, inclusion, and so on.The special event in which any symbol at all is selected, is certain to happen. We will call this event theuniversal event, after the name for the corresponding concept in set theory. The special “event” in w hichno symbol is selected is, for a similar reason, called the null event. The null event cannot happen becauseour description of things starts after a selection is made.Different events may or may not overlap, in the sense that two or more could happen with the sameoutcome. A collection of events which do not overlap is said to be mutually exclusive. For example, theevents that the freshman chosen is (1) from Ohio, or (2) from California, are mutually exclusive.Several events may have the property that at least one of them is sure to happen when any symbol isselected. A collection of events, one of which is sure to happen, is known as exhaustive. For example,the events that the freshman chosen is (1) younger than 25, or (2) older than 17, are exhaustive, but notmutually exclusive.A collection of events that are both mutually exclusive and e xhaustive is known as a partition of the eventspace. The partition that consists of all the individual symbols being selected will b e called the fundamentalpartition, and the selection of an individual symbol a fundamental event. In our example,