Introduction to Probability Version July 31, 2017 David F. Anderson Timo Sepp¨ala¨inen Benedek Valko´ NOT FOR DISTRIBUTION! (cid:13)c Copyright 2017 David F. Anderson, Timo Sepp¨al¨ainen and Benedek Valk´o Contents Preface 1 To the instructor 5 From gambling to an essential ingredient of modern science and society 7 Chapter 1. Experiments with random outcomes 9 1.1. Sample spaces and probabilities 9 1.2. Random sampling 12 1.3. Infinitely many outcomes 18 1.4. Consequences of the rules of probability 21 1.5. Random variables: a first look 27 1.6. Finer points ♣ 32 Exercises 34 Chapter 2. Conditional probability and independence 47 2.1. Conditional probability 47 2.2. Bayes’ formula 52 2.3. Independence 55 2.4. Independent trials 61 2.5. Further topics on sampling and independence 65 2.6. Finer points ♣ 72 Exercises 73 Chapter 3. Random variables 89 3.1. Probability distributions of random variables 89 3.2. Cumulative distribution function 95 3.3. Expectation 102 vii viii Contents 3.4. Variance 111 3.5. Gaussian distribution 116 3.6. Finer points ♣ 121 Exercises 123 Chapter 4. Approximations of the binomial distribution 137 4.1. Normal approximation 138 4.2. Law of large numbers 143 4.3. Applications of the normal approximation 145 4.4. Poisson approximation 150 4.5. Exponential distribution 155 4.6. Poisson process (cid:7) 158 4.7. Finer points ♣ 162 Exercises 164 Chapter 5. Transforms and transformations 173 5.1. Moment generating function 173 5.2. Distribution of a function of a random variable 179 5.3. Finer points ♣ 187 Exercises 188 Chapter 6. Joint distribution of random variables 195 6.1. Joint distribution of discrete random variables 195 6.2. Jointly continuous random variables 201 6.3. Joint distributions and independence 209 6.4. Further multivariate topics (cid:7) 216 6.5. Finer points ♣ 223 Exercises 224 Chapter 7. Sums and symmetry 235 7.1. Sums of independent random variables 235 7.2. Exchangeable random variables 243 7.3. Poisson process revisited (cid:7) 248 Exercises 251 Chapter 8. Expectation and variance in the multivariate setting 257 8.1. Linearity of expectation 257 8.2. Expectation and independence 262 8.3. Sums and moment generating functions 268 8.4. Covariance and correlation 269 8.5. The bivariate normal distribution (cid:7) 278 8.6. Finer points ♣ 280 Contents ix Exercises 281 Chapter 9. Tail bounds and limit theorems 291 9.1. Estimating tail probabilities 291 9.2. Law of large numbers 295 9.3. Central limit theorem 297 9.4. Monte Carlo method (cid:7) 299 9.5. Finer points ♣ 302 Exercises 303 Chapter 10. Conditional distribution 311 10.1. Conditional distribution of a discrete random variable 311 10.2. Conditional distribution for jointly continuous random variables 319 10.3. Conditional expectation 326 10.4. Further conditioning topics (cid:7) 334 10.5. Finer points ♣ 344 Exercises 345 Appendix A. Things to know from calculus 355 Appendix B. Set notation and operations 357 Exercises 360 Appendix C. Counting 363 Exercises 372 Appendix D. Sums, products and series 375 Exercises 380 Appendix E. Table of values for Φ(x) 383 Appendix F. Table of common probability distributions 385 Answers to selected exercises 387 Bibliography 403 Index 405 Preface Thistextisanintroductiontothetheoryofprobabilitywithacalculusbackground. Itisintendedforclassroomuseaswellasforindependentlearnersandreaders. We think of the level of our book as “intermediate” in the following sense. The math- ematics is covered as precisely and faithfully as is reasonable and valuable, while avoiding excessive technical details. Two examples of this: • Theprobabilitymodelisanchoredsecurelyinasamplespaceandaprobability (measure)onit,butrecedestothebackgroundafterthefoundationshavebeen established. • Randomvariablesaredefinedpreciselyasfunctionsonthesamplespace. This is important to avoid the feeling that a random variable is a vague notion. Once absorbed, this point is not needed for doing calculations. Short, illuminating proofs are given for many statements but not emphasized. The mainfocusofthebookisonapplyingthemathematicstomodelsimplesettingswith random outcomes and on calculating probabilities and expectations. Introductory probabilityisablendofmathematicalabstractionandhands-oncomputationwhere the mathematical concepts and examples have concrete real-world meaning. The principles that have guided us in the organization of the book include the following. (i)Wefoundthatthetraditionalinitialsegmentofaprobabilitycoursedevoted to counting techniques is not the most auspicious beginning. Hence we start with the probability model itself, and counting comes in conjunction with sampling. A systematictreatmentofcountingtechniquesisintheappendix. Theinstructorcan present this in class or assign it to the students. (ii) Most events are naturally expressed in terms of random variables. Hence webringthelanguageofrandomvariablesintothediscussionasquicklyaspossible. (iii) One of our goals was an early introduction of the major results of the subject, namely the central limit theorem and the law of large numbers. These are covered for independent Bernoulli random variables in Chapter 4. Preparation for them influenced the selection of topics of the earlier chapters. 1 2 Preface (iv) As a unifying feature, we derive the most basic probability distributions from independent trials, either directly or via a limit. This covers the binomial, geometric, normal, Poisson, and exponential distributions. Many students reading this text will have already been introduced to parts of the material. They might be tempted to solve some of the problems using computational tricks picked up elsewhere. We warn against doing so. The purpose of this text is not just to teach the nuts and bolts of probability theory and how tosolvespecificproblems, butalsototeachyouwhy themethodsofsolutionwork. Onlyarmedwiththeknowledgeofthe“why”canyouusethetheoryprovidedhere as a tool that will be amenable to a myriad of applications and situations. Thesectionsmarkedwithadiamond(cid:7)areoptionaltopicsthatcanbeincluded inanintroductoryprobabilitycourseastimepermitsanddependingontheinterests oftheinstructorandtheaudience. Theycanbeomittedwithoutlossofcontinuity. At the end of most chapters is a section titled Finer points on mathematical issuesthatareusuallybeyondthescopeofanintroductoryprobabilitybook. Inthe main text the symbol ♣ marks statements that are elaborated in the Finer points sectionofthechapter. Inparticular,wedonotmentionmeasure-theoreticissuesin the main text, but explain some of these in the Finer points sections. Other topics intheFinerpointssectionsincludethelackofuniquenessofadensityfunction,the Berry-Ess´een error bounds for normal approximation, the weak versus the strong law of large numbers, and the use of matrices in multivariate normal densities. These sections are intended for the interested reader as starting points for further exploration. They can also be helpful to the instructor who does not possess an advanced probability background. The symbol (cid:52) marks the end of a numbered example and remark in the text. The symbol (cid:3) marks the end of a proof. Thereisanexercisesectionattheendofeachchapter. Theexercisesbeginwith asmallnumberofwarm-upexercisesexplicitlyorganizedbysectionsofthechapter. Theirpurposeistoofferthereaderimmediateandbasicpracticeafterasectionhas beencovered. ThesubsequentexercisesundertheheadingFurtherexercisescontain problems of varying levels of difficulty, including routine ones, but some of these exercises use material from more than one section. Under the heading Challenging problems towards the end of the exercise section we have collected problems that may require some creativity or lengthier calculations. But these exercises are still fully accessible with the tools at the student’s disposal. The concrete mathematical prerequisites for reading this book consist of basic settheoryandsomecalculus,namely,asolidfoundationinsinglevariablecalculus, including sequences and series, and multivariable integration. Appendix A gives a shortlist ofthe particularcalculus topicsused inthetext. AppendixB reviewsset theory, and Appendix D some infinite series. Sets are used from the get-go to set up probability models. Both finite and infinitegeometricseriesareusedextensivelybeginningalreadyinChapter1. Single- variable integration and differentiation are used from Chapter 3 onwards to work with continuous random variables. Computations with the Poisson distribution from Section 4.4 onwards require facility with the Taylor series of ex. Multiple Preface 3 integralsarriveinSection6.2aswebegintocomputeprobabilitiesandexpectations under jointly continuous distributions. The authors welcome feedback on the text. The reader can leave comments and tell us about typos and mistakes on the online form at http://goo.gl/forms/iaXs81xQW8 We thank numerous anonymous reviewers whose comments made a real dif- ference to the book, students who went through successive versions of the text, and colleagues who used the text and gave us invaluable feedback. Illustrations wereproducedwithWolframMathematica11. Theauthorsgratefullyacknowledge support from the National Science Foundation, the Simons Foundation, the Army Research Office, and the Wisconsin Alumni Research Foundation. Madison, Wisconsin July, 2017 David F. Anderson Timo Sepp¨al¨ainen Benedek Valk´o