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.

2 Functions of Random Variables .. Expectation, Mean, and Variance .. Joint PMFs of Multiple Random Variables .. Conditioning .. Independence .. Summary and Discussion ..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.

3 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 .. 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.

4 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.

5 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.

6 N. Space Probabilistic Conditional Total Probability Theorem and Bayes Summary and Space and ProbabilityChap. 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?

7 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?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.

8 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. 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.

9 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.

10 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.