Fundamental Probability FundamentalProbability:AComputationalApproach M.S.Paolella  2006 John Wiley & Sons, Ltd. ISBN: 0-470-02594-8 Fundamental Probability A Computational Approach Marc S. Paolella Copyright2006 JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester, WestSussexPO198SQ,England Telephone(+44)1243779777 Email(forordersandcustomerserviceenquiries):[email protected] VisitourHomePageonwww.wiley.com AllRightsReserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystemor transmittedinanyformorbyanymeans,electronic,mechanical,photocopying,recording,scanningor otherwise,exceptunderthetermsoftheCopyright,DesignsandPatentsAct1988orunderthetermsofa licenceissuedbytheCopyrightLicensingAgencyLtd,90TottenhamCourtRoad,LondonW1T4LP,UK, withoutthepermissioninwritingofthePublisher.RequeststothePublishershouldbeaddressedtothe PermissionsDepartment,JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester, WestSussexPO198SQ,England,[email protected],orfaxedto(+44)1243770620. Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarks.Allbrand namesandproductnamesusedinthisbookaretradenames,servicemarks,trademarksorregistered trademarksoftheirrespectiveowners.ThePublisherisnotassociatedwithanyproductorvendormentioned inthisbook. Thispublicationisdesignedtoprovideaccurateandauthoritativeinformationinregardtothesubjectmatter covered.ItissoldontheunderstandingthatthePublisherisnotengagedinrenderingprofessionalservices. Ifprofessionaladviceorotherexpertassistanceisrequired,theservicesofacompetentprofessionalshould besought. OtherWileyEditorialOffices JohnWiley&SonsInc.,111RiverStreet,Hoboken,NJ07030,USA Jossey-Bass,989MarketStreet,SanFrancisco,CA94103-1741,USA Wiley-VCHVerlagGmbH,Boschstr.12,D-69469Weinheim,Germany JohnWiley&SonsAustraliaLtd,42McDougallStreet,Milton,Queensland4064,Australia JohnWiley&Sons(Asia)PteLtd,2ClementiLoop#02-01,JinXingDistripark,Singapore129809 JohnWiley&SonsCanadaLtd,22WorcesterRoad,Etobicoke,Ontario,CanadaM9W1L1 Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappears inprintmaynotbeavailableinelectronicbooks. BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN-13:978-0-470-02594-9 ISBN-10:0-470-02594-8 Typesetin10/12TimesbyLaserwordsPrivateLimited,Chennai,India PrintedandboundinGreatBritainbyAntonyRoweLtd,Chippenham,Wiltshire Thisbookisprintedonacid-freepaperresponsiblymanufacturedfromsustainableforestry inwhichatleasttwotreesareplantedforeachoneusedforpaperproduction. Chapter Listing Preface xi 0 Introduction 1 Part I Basic Probability 7 1 Combinatorics 9 2 Probability spaces and counting 43 3 Symmetric spaces and conditioning 73 Part II Discrete Random Variables 111 4 Univariate random variables 113 5 Multivariate random variables 165 6 Sums of random variables 197 Part III Continuous Random Variables 237 7 Continuous univariate random variables 239 8 Joint and conditional random variables 285 9 Multivariate transformations 323 Appendices 343 A Calculus review 343 B Notation tables 435 C Distribution tables 441 References 451 Index 461 Contents Preface xi A note to the student (and instructor) xvi A note to the instructor (and student) xviii Acknowledgements xxi 0 Introduction 1 Part I Basic Probability 7 1 Combinatorics 9 1.1 Basic counting 9 1.2 Generalized binomial coefficients 13 1.3 Combinatoric identities and the use of induction 15 1.4 The binomial and multinomial theorems 18 1.4.1 The binomial theorem 18 1.4.2 An extension of the binomial theorem 23 1.4.3 The multinomial theorem 27 1.5 The gamma and beta functions 28 1.5.1 The gamma function 28 1.5.2 The beta function 31 1.6 Problems 36 2 Probability spaces and counting 43 2.1 Introducing counting and occupancy problems 43 2.2 Probability spaces 47 2.2.1 Introduction 47 2.2.2 Definitions 49 2.3 Properties 58 viii Contents 2.3.1 Basic properties 58 2.3.2 Advanced properties 59 2.3.3 A theoretical property 67 2.4 Problems 68 3 Symmetric spaces and conditioning 73 3.1 Applications with symmetric probability spaces 73 3.2 Conditional probability and independence 85 3.2.1 Total probability and Bayes’ rule 87 3.2.2 Extending the law of total probability 93 3.2.3 Statistical paradoxes and fallacies 96 3.3 The problem of the points 97 3.3.1 Three solutions 97 3.3.2 Further gambling problems 99 3.3.3 Some historical references 100 3.4 Problems 101 Part II Discrete Random Variables 111 4 Univariate random variables 113 4.1 Definitions and properties 113 4.1.1 Basic definitions and properties 113 4.1.2 Further definitions and properties 117 4.2 Discrete sampling schemes 120 4.2.1 Bernoulli and binomial 121 4.2.2 Hypergeometric 123 4.2.3 Geometric and negative binomial 125 4.2.4 Inverse hypergeometric 128 4.2.5 Poisson approximations 130 4.2.6 Occupancy distributions 133 4.3 Transformations 140 4.4 Moments 141 4.4.1 Expected value of X 141 4.4.2 Higher-order moments 143 4.4.3 Jensen’s inequality 151 4.5 Poisson processes 154 4.6 Problems 156 5 Multivariate random variables 165 5.1 Multivariate density and distribution 165 5.1.1 Joint cumulative distribution functions 166 Contents ix 5.1.2 Joint probability mass and density functions 168 5.2 Fundamental properties of multivariate random variables 171 5.2.1 Marginal distributions 171 5.2.2 Independence 173 5.2.3 Exchangeability 174 5.2.4 Transformations 175 5.2.5 Moments 176 5.3 Discrete sampling schemes 182 5.3.1 Multinomial 182 5.3.2 Multivariate hypergeometric 188 5.3.3 Multivariate negative binomial 190 5.3.4 Multivariate inverse hypergeometric 192 5.4 Problems 194 6 Sums of random variables 197 6.1 Mean and variance 197 6.2 Use of exchangeable Bernoulli random variables 199 6.2.1 Examples with birthdays 202 6.3 Runs distributions 206 6.4 Random variable decomposition 218 6.4.1 Binomial, negative binomial and Poisson 218 6.4.2 Hypergeometric 220 6.4.3 Inverse hypergeometric 222 6.5 General linear combination of two random variables 227 6.6 Problems 232 Part III Continuous Random Variables 237 7 Continuous univariate random variables 239 7.1 Most prominent distributions 239 7.2 Other popular distributions 263 7.3 Univariate transformations 269 7.3.1 Examples of one-to-one transformations 271 7.3.2 Many-to-one transformations 273 7.4 The probability integral transform 275 7.4.1 Simulation 276 7.4.2 Kernel density estimation 277 7.5 Problems 278 x Contents 8 Joint and conditional random variables 285 8.1 Review of basic concepts 285 8.2 Conditional distributions 290 8.2.1 Discrete case 291 8.2.2 Continuous case 292 8.2.3 Conditional moments 304 8.2.4 Expected shortfall 310 8.2.5 Independence 311 8.2.6 Computing probabilities via conditioning 312 8.3 Problems 317 9 Multivariate transformations 323 9.1 Basic transformation 323 9.2 The t and F distributions 329 9.3 Further aspects and important transformations 333 9.4 Problems 339 Appendices 343 A Calculus review 343 A.0 Recommended reading 343 A.1 Sets, functions and fundamental inequalities 345 A.2 Univariate calculus 350 A.2.1 Limits and continuity 351 A.2.2 Differentiation 352 A.2.3 Integration 364 A.2.4 Series 382 A.3 Multivariate calculus 413 A.3.1 Neighborhoods and open sets 413 A.3.2 Sequences, limits and continuity 414 A.3.3 Differentiation 416 A.3.4 Integration 425 B Notation tables 435 C Distribution tables 441 References 451 Index 461 Preface Writing a book is an adventure. To begin with, it is a toy and an amusement; then it becomes a mistress, and then it becomes a master, and then a tyrant. The last phase is that just as you are about to be reconciled to your servitude, you kill the monster, and fling him out to the public. (Sir Winston Churchill) Reproducedby permission ofLittle Brown Like many branches of science, probability and statistics can be effectively taught and appreciated at many mathematical levels. This book is the first of two on prob- ability, and designed to accompany a course aimed at students who possess a basic commandoffreshmancalculusandsomelinearalgebra,butwithnopreviousexposure to probability. It follows the more or less traditional ordering of subjects at this level, thoughwithgreaterscopeandoftenmoredepth,andstopswithmultivariatetransforma- tions.Thesecondbook,referredtoasVolumeII,continueswithmoreadvancedtopics, including (i) a detailed look at sums of random variables via exact and approximate numeric inversion of moment generating and characteristic functions, (ii) a discussion of more advanced distributions including the stable Paretian and generalized hyper- bolic, and (iii) a detailed look at noncentral distributions, quadratic forms and ratios of quadratic forms. A subsequent book will deal with the subject of statistical modeling and extraction of information from data. In principle, such prerequisites render the books appropri- ate for upper division undergraduates in a variety of disciplines, though the amount of material and, in some topics covered, the depth and use of some elements from advanced calculus, make the books especially suited for students with more focus and mathematical maturity, such as undergraduate math majors, or beginning graduate students in statistics, finance or economics, and other fields which use the tools of probability and statistical methodology. Motivation and approach Thebooksgrew(andgrew...)fromasetofnotesIbeganwritingin1996toaccompany atwo-semestersequenceI startedteachinginthe statistics andeconometricsfacultyin