Grinstead and Snell’s Introduction to Probability

1 GrinsteadandSnell'sIntroductionto ProbabilityTheCHANCEP roject1 Versiondated4 July20061 Copyright (C) a versionof GrinsteadandSnell's`Introductionto Probability , 2ndedition',publishedby theAmericanMathematicalSo-ciety, Copyright (C) freelyredistributableunderthetermsof ourwivesandin DiscreteProbability DiscreteProbabilities.. Distributions..182 ContinuousProbability ContinuousProbabilities.. Functions..553 .. ing.. 1204 .. 1755 Distributions.. Densities.. 2056 .. DiscreteRandomVariables.. 2687 Sumsof DiscreteRandomVariables.. ContinuousRandomVariables.. 2918 Law of .. 316vviCONTENTS9 .. Trials.. Trials.

2 35610 .. 39311 Markov .. Chains.. Chains.. 45212 EuclideanSpace.. 'sRuin.. 493 Appendices499 Index503 PrefaceProbability theorybeganin seventeenth centuryFrancewhenthetwo greatFrenchmathematicians,BlaisePascalan dPierredeFermat,correspondedover two prob-lemsfromgamesof thosePascalandFermatsolved continuedto in uencesuch earlyresearchersas Huygens,Bernoulli,andDeMoivrein estab-lishinga mathematicaltheoryof Probability . Today, Probability theoryis a well-establishedbranch of mathematicsthat ndsapplicationsin everyareaof scholarlyactivity frommusicto physics,andin dailyexperiencefromweatherpredictiontopr edictingtherisksof designedforan introductoryprobability coursetaken by sophomores,juniors,andseniorsin mathematics,thephysicalandsocialsciences ,engineering, presents a thoroughtreatment of Probability ideasandtechniquesnecessaryfora rmunderstandingof usedin a variety of courselengths,levels,andareasof usein a standardone-termcourse,in which bothdiscreteandcontinuousprobability is covered,students shouldhave takenas a prerequisitetwo termsofcalculus.

3 Includinganintroductionto orderto cover Chap-ter11,which containsmaterialonMarkov chains,someknowledgeof matrixtheoryis usedin a discreteprobability such a way thatthediscreteandcontinuousprobability discussionsarepresentedin a separate,butparallel, Probability ando erssomestrongpedagogicalvaluein thatthediscretediscussionscansometimesse rve to motivatethemoreabstractcontinuousprobabi lity usein a discreteprobability course,studentsshouldhave taken onetermof calculusas a assumedor necessaryin orderto obtainfullbene tsfromtheuseof thecomputingmaterialandexamplesin thetexthave beenwrittenin each of thelanguagesTrueBASIC,Maple, distributedontheWeb as partof theChanceProject,which is de-votedto providingmaterialsforbeginningcoursesin Probability ,solutionsto theodd-numberedexercises,andcurrent errataarealsoavailableat obtainallof thesolutionsby writingtoeitherof theauthors,at rigorandemphasis: Probability is a wonderfullyintuitive andapplicable eldof have triednotto spoilitsbeauty by presentingtoo ,we have triedto developthekey ideasin a somewhatleisurelystyle,to providea variety of interestingapplicationsto Probability , andtoshow someof thenonintuitive examplesthatmake Probability such a.

4 Thereareover 600exercisesin thetextprovidingplenty of oppor-tunity forpracticingskillsanddevelopinga soundunderstandingof be donewithandwithouttheuseof acomputerandmoretheoreticalexercisesto improve theunderstandingof cultexercisesareindicatedby solutionmanualforallof theexercisesis availableto remarks:Introductoryprobability is a subjectin which thefunda-mentalideasarestillcloselytiedt o thoseof thefoundersof thisreason,therearenumeroushistoricalcom ments in thetext,especiallyas theydealwiththedevelopment of useof computerprograms: Probability theorymakes predictionsaboutexperiments , it lendsitselfbeautifullyto theuseof computersas a mathematicaltool to thetextthecomputeris utilizedin ,it providesa labora-torywherechanceexperiments canbe simulatedandthestudents cangeta feelingforthevariety of such thecomputerin Probability hasbeenalreadybeautifullyillustratedby WilliamFellerin thesecondeditionof hisfamoustextAn Introductionto ProbabilityTheoryandItsApplications(NewY ork:Wiley, 1950).

5 In thepreface,Fellerwroteabouthistreatment of uctuationin cointossing:\Theresultsaresoamazingandso atvariancewithcommonintuitionthateven sophisticatedcolleaguesdoubtedthatcoinsa ctuallymisbehave as a simulatedexperiment is thereforeincluded."In additionto providinga laboratoryforthestudent, thecomputeris a powerfulaidin understandingbasicresultsof Probability theory. For example,thegraphicalillustrationof theapproximationof thestandardizedbinomialdistributionsto thenormalcurve is a moreconvincingdemonstrationof theCentralLimitTheoremthanmany of theformalproofsof , thecomputerallowsthestudent tosolve problemsthatdonotlendthemselves to closed-formformulassuch as waitingtimesin ,theintroductionof thecomputerchangestheway in which we lookat many problemsin Probability .

6 For example,beingableto calculateexactbinomialprobabilitiesforex periments upto 1000trialschangestheway we Probability texttoday owes a greatdebtto WilliamFeller,whotaught us allhow to make Probability comealive as a youPREFACEix ndanexample,anapplication,or anexercisethatyoureallylike, it probablyhaditsoriginin Feller'sclassictext,An Introductionto Probability areindebtedto many peoplefortheirhelpin Markov Chainspresentedin thebookwas developedby JohnKemeny a silent co-authorforthematerialoncontinuousproba bility in anearlierversionof pagesof comments of thesecomments wereverythought-provoking;in addition,theyprovideda student'sperspective thisversionof thebookhave theirgenesisin providedextensive helpwiththetypesettingandthe thecomputerprogramsin , we thanktheAmericanMathematicalSociety, andin particularSergeiGelfandandJohnEwing,fort heirinterestin thisbook;theirhelpin its production;andtheirwillingnessto make DiscreteProbabilitiesProbabilityIn thischapter,we shall rstconsiderchanceexperiments witha nitenumber ofpossibleoutcomes!

7 1,!2, .. ,!n. Forexample,we rolla dieandthepossibleoutcomesare1, 2, 3, 4, 5, 6 correspondingto tossa coinwithpossibleoutcomesH (heads)andT (tails).It is frequentlyusefulto be ableto referto anoutcomeof anexperiment. Forexample,we might want to writethemathematicalexpressionwhich gives thesumof fourrollsof a dothis,we couldletXi,i= 1;2;3;4;represent thevaluesof theoutcomesof thefourrolls,andthenwe couldwritetheexpressionX1+X2+X3+X4forthe sumof 's arecalledrandomvariables. A randomvari-ableis simplyanexpressionwhosevalueis theoutcomeof a in thecaseof othertypes of variablesin mathematics,randomvariablescantake ondi erent therandomvariablewhich represents therollof shallassignprobabilitiesto thepossibleoutcomesof dothisbyassigningto each outcome!

8 Ja nonnegative numberm(!j) in such a way thatm(!1) +m(!2) + +m(!6) = 1:Thefunctionm(!j) is calledthedistributionfunctionof thecaseof therollof thediewe wouldassignequalprobabilitiesor probabilities1/6to each of of probabilities,onecouldwriteP(X 4) =2312 CHAPTER1. DISCRETEPROBABILITYDISTRIBUTIONSto meanthattheprobability is 2=3 thata rollof a diewillhave a valuewhich therandomvariablewhich represents thetossof a thiscase,therearetwo possibleoutcomes,which we canlabel as H havereasonto suspectthatthecoincomesuponeway moreoftenthantheotherway,it is naturalto assigntheprobability of 1/2to each of thetwo bothof theabove experiments,each outcomeis assignedan thecasein example,if a drugis foundtobe e ective 30percent of thetimeit is used,we might assigna Probability .

9 3 thatthedrugis e ective thenexttimeit is thatit is note ective. Thislastexampleillustratestheintuitivefr equencyconceptof , if we havea probabilitypthatanexperiment willresultin outcomeA, thenif we repeatthisexperiment a largenumber of timeswe shouldexpectthatthefractionof timesthatAwilloccuris aboutp. To check intuitive ideaslike this,we shall ndit helpfultolookat someof theseproblemsexperimentally. We could,forexample,tossa coina largenumber of timesandseeif thefractionof timesheadsturnsupis about1 couldalsosimulatethisexperiment ona want to be ableto performanexperiment thatcorrespondsto a givensetofprobabilities;forexample,m(!1) = 1=2,m(!2) = 1=3, andm(!)

10 3) = 1= thiscase,onecouldmarkthreefacesof a six-sideddiewithan!1, two faceswithan!2,andonefacewithan! thegeneralcasewe assumethatm(!1),m(!2), .. ,m(!n) areallrationalnumbers,withleastcommonden ominatorn. Ifn >2, we canimaginea longcylindricaldiewitha cross-sectionthatis a (!j) =nj=n, thenwe canlabelnjof thelongfacesof thecylinderwithan!j, andif oneof theendfacescomesup,we 2, a coincouldbe willbe particularlyinterestedin repeatinga chanceexperiment a largenum-ber of a convenient way to carryouta fewrepetitions,it wouldbe di cultto carryouta largenumber of largenumber of operationsin a veryshorttime,it is naturalto turnto must rst nda computeranalogof rollinga doneonthecomputerby meansof arandomnumber ,thecomputercanbe asked fora realnumber between0 and1, or an integerin a given setof consecutive the rstcase,therealnumbersarechosenin such a way thattheprobability thatthenumber liesin any particularsubintervalof thisunitinterval is equalto thelengthof thesecondcase.