Introduction to Probability

1 LECTURE NOTESC ourse 2000 Introduction to ProbabilityDimitri P. Bertsekas and John N. TsitsiklisProfessors of Electrical Engineering and Computer ScienceMassachusetts Institute of TechnologyCambridge, MassachusettsThese notes are copyright-protected but may be freely distributed forinstructional nonprofit Sample Space and Probability .. Sets .. Probabilistic Models .. Conditional Probability .. Independence .. Total Probability Theorem and Bayes Rule .. Counting.. Summary and Discussion ..2. Discrete Random Variables.. Basic Concepts .. Probability Mass Functions.. Functions of Random Variables .. Expectation, Mean, and Variance .. Joint PMFs of Multiple Random Variables .. Conditioning .. Independence .. Summary and Discussion.

2 3. General Random Variables.. Continuous Random Variables and PDFs .. Cumulative Distribution Functions .. Normal Random Variables .. Conditioning on an Event .. Multiple Continuous Random Variables .. Derived Distributions .. Summary and Discussion ..4. Further Topics on Random Variables and Expectations .. Transforms .. Sums of Independent Random Variables - Convolutions .. Conditional Expectation as a Random Variable .. Sum of a Random Number of Independent Random Variables.. Covariance and Correlation.. Least Squares Estimation .. The Bivariate Normal Distribution ..5. The Bernoulli and Poisson Processes .. The Bernoulli Process .. The Poisson Process ..6. Markov Chains .. Discrete-Time Markov Chains .. Classification of States.

3 Steady-State Behavior .. Absorption Probabilities and Expected Time to Absorption .. More General Markov Chains ..7. Limit Theorems .. Some Useful Inequalities .. The Weak Law of Large Numbers .. Convergence in Probability .. The Central Limit Theorem .. The Strong Law of Large Numbers ..PrefaceThese class notes are the currently used textbook for Probabilistic SystemsAnalysis, an introductory Probability course at the Massachusetts Institute ofTechnology. The text of the notes is quite polished and complete, but the prob-lems are less course is attended by a large number of undergraduate and graduatestudents with diverse backgrounds. Acccordingly, we have tried to strike a bal-ance between simplicity in exposition and sophistication in analytical of the more mathematically rigorous analysis has been just sketched orintuitively explained in the text, so that complex proofs do not stand in the wayof an otherwise simple exposition.

4 At the same time, some of this analysis andthe necessary mathematical results are developed (at the level of advanced calcu-lus) in theoretical problems, which are included at the end of the correspondingchapter. The theoretical problems (marked by *) constitute an important com-ponent of the text, and ensure that the mathematically oriented reader will findhere a smooth development without major give solutions to all the problems, aiming to enhance the utility ofthe notes for self-study. We have additional problems, suitable for homeworkassignment (with solutions), which we make available to intent is to gradually improve and eventually publish the notes as atextbook, and your comments will be appreciatedDimitri P. N. Space Probabilistic Conditional Total Probability Theorem and Bayes Summary and Space and ProbabilityChap.

5 1 Probability is a very useful concept, but can be interpreted in a number ofways. As an illustration, consider the is admitted to the hospital and a potentially life-saving drug isadministered. The following dialog takes place between the nurse and aconcerned : Nurse, what is the Probability that the drug will work?NURSE: I hope it works, we ll know : Yes, but what is the Probability that it will?NURSE: Each case is different, we have to : But let s see, out of a hundred patients that are treated undersimilar conditions, how many times would you expect it to work?NURSE (somewhat annoyed): I told you, every person is different, for someit works, for some it doesn (insisting): Then tell me, if you had to bet whether it will workor not, which side of the bet would you take?

6 NURSE (cheering up for a moment): I d bet it will (somewhat relieved): OK, now, would you be willing to losetwodollars if it doesn t work, and gain one dollar if it does?NURSE (exasperated): What a sick thought! You are wasting my time!In this conversation, the relative attempts to use the concept of Probability todiscuss anuncertainsituation. The nurse s initial response indicates that themeaning of Probability is not uniformly shared or understood, and the relativetries to make it more concrete. The first approach is to define Probability interms offrequency of occurrence,asapercentage of successes in a moderatelylarge number of similar situations. Such an interpretation is often natural. Forexample, when we say that a perfectly manufactured coin lands on heads withprobability 50%, we typically mean roughly half of the time.

7 But the nursemay not be entirely wrong in refusing to discuss in such terms. What if thiswasanexperimental drug that was administered for the very first time in thishospital or in the nurse s experience?While there are many situations involving uncertainty in which the fre-quency interpretation is appropriate, there are other situations in which it isnot. Consider, for example, a scholar who asserts that the Iliad and the Odysseywere composed by the same person, with Probability 90%. Such an assertionconveys some information, but not in terms of frequencies, since the subject isaone-time event. Rather, it is an expression of the scholar ssubjective might think that subjective beliefs are not interesting, at least from amathematical or scientific point of view. On the other hand, people often haveto make choices in the presence of uncertainty, and a systematic way of makinguse of their beliefs is a prerequisite for successful, or at least consistent, decisionSec.

8 Fact, the choices and actions of a rational person, can reveal a lot aboutthe inner-held subjective probabilities, even if the person does not make conscioususe of probabilistic reasoning. Indeed, the last part of the earlier dialog was anattempt to infer the nurse s beliefs in an indirect manner. Since the nurse waswilling to accept a one-for-one bet that the drug would work, we may inferthat the Probability of success was judged to be at least 50%. And had thenurse accepted the last proposed bet (two-for-one), that would have indicated asuccess Probability of at least 2 than dwelling further into philosophical issues about the appropri-ateness of probabilistic reasoning, we will simply take it as a given that the theoryof Probability is useful in a broad variety of contexts, including some where theassumed probabilities only reflect subjective beliefs.

9 There is a large body ofsuccessful applications in science, engineering, medicine, management, etc., andon the basis of this empirical evidence, Probability theory is an extremely main objective in this book is to develop the art of describing un-certainty in terms of probabilistic models, as well as the skill of probabilisticreasoning. The first step, which is the subject of this chapter, is to describethe generic structure of such models, and their basic properties. The models weconsider assign probabilities to collections (sets) of possible outcomes. For thisreason, we must begin with a short review of set SETSP robability makes extensive use of set operations, so let us introduce at theoutset the relevant notation and a collection of objects, which are theelementsof the set.

10 IfSisaset andxis an element ofS,wewritex not an element ofS,wewritex/ can have no elements, in which case it is called theemptyset,denoted by .Sets can be specified in a variety of ways. IfScontains a finite number ofelements, sayx1,x2,..,xn,wewrite it as a list of the elements, in braces:S={x1,x2,..,xn}.Forexample, the set of possible outcomes of a die roll is{1,2,3,4,5,6},and theset of possible outcomes of a coin toss is{H, T},whereHstands for heads andTstands for tails. IfScontains infinitely many elementsx1,x2,..,which can be enumeratedin a list (so that there are as many elements as there are positive integers) wewriteS={x1,x2,..},4 Sample Space and ProbabilityChap. 1and we say thatSiscountably example, the set of even integerscan be written as{0,2, 2,4, 4.}