Dimitri P. Bertsekas and John N. Tsitsiklis

1 Introduction to ProbabilityDimitri P. Bertsekas and John N. TsitsiklisMassachusetts Institute of TechnologyWWW site for book information and Scientific, Belmont, MassachusettsAthena ScientificPost Office Box 391 Belmont, Mass. : Design:AnnGallagerc 2002 Dimitri P. Bertsekas and John N. TsitsiklisAll rights reserved. No part of this book may be reproduced in any form by anyelectronic or mechanical means (including photocopying, recording, or informa-tion storage and retrieval) without permission in writing from the s Cataloging-in-Publication DataBertsekas, Dimitri P., Tsitsiklis , John to ProbabilityIncludes bibliographical references and index1. Probabilities. 2. Stochastic Processes. I. 21 Library of Congress Control Number: 2002092167 ISBN 1-886529-40-XTothe memory ofPantelis Bertsekas and Nikos TsitsiklisContents1. Sample Space and Probabilistic Conditional Total Probability Theorem and Bayes Summary and Discrete Random Basic Probability Mass Functions of Random Expectation, Mean, and Joint PMFs of Multiple Random Summary and General Random Continuous Random Variables and Cumulative Distribution Functions.

2 Normal Random Conditioning on an Multiple Continuous Random Variables .. Derived Summary and Further Topics on Random Sums of Independent Random Variables - More on Conditional Expectation and Sum of a Random Number of Independent Random Variables .. p. Covariance and Least Squares The Bivariate Normal Distribution .. Summary and The Bernoulli and Poisson The Bernoulli The Poisson Summary and Markov Discrete-Time Markov Classification of Steady-State Absorption Probabilities and Expected Time to Absorption .. p. Continuous-Time Markov Summary and Limit Markov and Chebyshev Inequalities .. The Weak Law of Large Convergence in The Central Limit The Strong Law of Large Numbers .. Summary and .. is common sense reduced to calculationLaplaceThis book is an outgrowth of our involvement in teaching an introductory prob-ability course ( Probabilistic Systems Analysis ) at the Massachusetts Instituteof course is attended by a large number of students with diverse back-grounds, and a broad range of interests.

3 They span the entire spectrum fromfreshmen to beginning graduate students, and from the engineering school to theschool of management. Accordingly, we have tried to strike a balance betweensimplicity in exposition and sophistication in analytical reasoning. Our key aimhas been to develop the ability to construct and analyze probabilistic models inamanner that combines intuitive understanding and mathematical this spirit, some of the more mathematically rigorous analysis has beenjust sketched or intuitively explained in the text, so that complex proofs do notstand in the way of an otherwise simple exposition. At the same time, some ofthis analysis is developed (at the level of advanced calculus) in theoretical prob-lems, that are included at the end of the corresponding chapter. Furthermore,some of the subtler mathematical issues are hinted at in footnotes addressed tothe more attentive book covers the fundamentals of probability theory (probabilistic mod-els, discrete and continuous random variables, multiple random variables, andlimit theorems), which are typically part of a first course on the subject.

4 Italso contains, in Chapters 4-6 a number of more advanced topics, from which aninstructor can choose to match the goals of a particular course. In particular, inChapter 4, we develop transforms, a more advanced view of conditioning, sumsof random variables, least squares estimation, and the bivariate normal distribu-viiviiiPrefacetion. Furthermore, in Chapters 5 and 6, we provide a fairly detailed introductionto Bernoulli, Poisson, and Markov course covers all seven chapters in a single semester, with the ex-ception of the material on the bivariate normal (Section ), and on continuous-time Markov chains (Section ). However, in an alternative course, the materialon stochastic processes could be omitted, thereby allowing additional emphasison foundational material, or coverage of other topics of the instructor s most notable omission in coverage is an introduction to we develop all the basic elements of Bayesian statistics, in the form ofBayes rule for discrete and continuous models, and least squares estimation, wedo not enter the subjects of parameter estimation, or non-Bayesian problems that supplement the main text are divided in three categories:(a)Theoretical problems.

5 The theoretical problems (marked by *) constitutean important component of the text, and ensure that the mathematicallyoriented reader will find here a smooth development without major solutions are given in the text, but an ambitious reader may be ableto solve many of them, especially in earlier chapters, before looking at thesolutions.(b)Problems in the text:Besides theoretical problems, the text contains severalproblems, of various levels of difficulty. These are representative of theproblems that are usually covered in recitation and tutorial sessions , and are a primary mechanism through which many of our studentslearn the material. Our hope is that students elsewhere will attempt tosolve these problems, and then refer to their solutions to calibrate andenhance their understanding of the material. The solutions are posted onthe book s www (c)Supplementary problems:There is a large (and growing) collection of ad-ditional problems, which is not included in the book, but is made availableat the book s www site.

6 Many of these problems have been assigned ashomework or exam problems at , and we expect that instructorselsewhere will use them for a similar purpose. While the statements ofthese additional problems are publicly accessible, the solutions are madeavailable from the authors only to course like to acknowledge our debt to several people who contributedin various ways to the book. Our writing project began when we assumed re-sponsibility for a popular probability class at that our colleague Al Drakehad taught for several decades. We were thus fortunate to start with an organi-zation of the subject that had stood the test of time, a lively presentation of thevarious topics in Al s classic textbook, and a rich set of material that had beenused in recitation sessions and for homework. We are thus indebted to Al DrakePrefaceixfor providing a very favorable set of initial thankful to the several colleagues who have either taught from thedraft of the book at various universities or have read it, and have provided uswith valuable feedback.

7 In particular, we thank Ibrahim Abou Faycal, Gustavode Veciana, Eugene Feinberg, Bob Gray, Muriel M edard, Jason Papastavrou,Ilya Pollak, David Tse, and Terry teaching assistants for the class have been very helpful. Theypointed out corrections to various drafts, they developed problems and solutionssuitable for the class, and through their direct interaction with the student body,they provided a robust mechanism for calibrating the level of the thousands of bright students at at an early stage in theirstudies was a great source of satisfaction for us. We thank them for their valu-able feedback and for being patient while they were taught from a but not least, we are grateful to our families for their support through-out the course of this long P. Bertsekas , N. Tsitsiklis , Mass., May 2002 ATHENA SCIENTIFIC BOOKS1. Introduction to Probability, by Dimitri P.

8 Bertsekas and John N. Tsit-siklis, 2002, ISBN 1-886529-40-X, 430 pages2. Dynamic Programming and Optimal Control: Second Edition, Vols. Iand II, by Dimitri P. Bertsekas , 2001, ISBN 1-886529-08-6, 704 pages3. Nonlinear Programming, Second Edition, by Dimitri P. Bertsekas ,1999, ISBN 1-886529-00-0, 791 pages4. Network Optimization: Continuous and Discrete Models by , 1998, ISBN 1-886529-02-7, 608 pages5. Network Flows and Monotropic Optimization by R. Tyrrell Rockafel-lar, 1998, ISBN 1-886529-06-X, 634 pages6. Introduction to Linear Optimization by Dimitris Bertsimas and JohnN. Tsitsiklis , 1997, ISBN 1-886529-19-1, 608 pages7. Parallel and Distributed Computation: Numerical Methods by and John N. Tsitsiklis , 1997, ISBN 1-886529-01-9, 718pages8. Neuro-Dynamic Programming, by Dimitri P. Bertsekas and John , 1996, ISBN 1-886529-10-8, 512 pages9. Constrained Optimization and Lagrange Multiplier Methods, by Dim-itri P.

9 Bertsekas , 1996, ISBN 1-886529-04-3, 410 pages10. Stochastic Optimal Control: The Discrete-Time Case by Dimitri and Steven E. Shreve, 1996, ISBN 1-886529-03-5, 330 pagesx1 Sample 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:Ihope 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?

10 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 lose twodollars 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 probabilityto discuss 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.