518 pages
Missing: waarschijnlijkheid | Must include: waarschijnlijkheid
25 KB – 518 Pages
PAGE – 1 ============
GrinsteadandSnell’sIntroductiontoProbabilityTheCHANCEProject1Versiondated4July20061Copyright(C)2006PeterG.Doyle.ThisworkisaversionofGrinsteadandSnell’s`IntroductiontoProbability,2ndedition’,publishedbytheAmericanMathematicalSo-ciety,Copyright(C)2003CharlesM.GrinsteadandJ.LaurieSnell.ThisworkisfreelyredistributableunderthetermsoftheGNUFreeDocumentationLicense.
PAGE – 3 ============
ContentsPrefacevii1DiscreteProbabilityDistributions11.1SimulationofDiscreteProbabilities.11.2DiscreteProbabilityDistributions..182ContinuousProbabilityDensities412.1SimulationofContinuousProbabilities..412.2ContinuousDensityFunctions.553Combinatorics753.1Permutations.753.2Combinations.923.3CardSh.1204ConditionalProbability1334.1DiscreteConditionalProbability..1334.2ContinuousConditionalProbability.1624.3Paradoxes1755DistributionsandDensities1835.1ImportantDistributions.1835.2ImportantDensities2056ExpectedValueandVariance2256.1ExpectedValue2256.2VarianceofDiscreteRandomVariables..2576.3ContinuousRandomVariables.2687SumsofRandomVariables2857.1SumsofDiscreteRandomVariables2857.2SumsofContinuousRandomVariables..2918LawofLargeNumbers3058.1DiscreteRandomVariables..3058.2ContinuousRandomVariables.316v
PAGE – 4 ============
viCONTENTS9CentralLimitTheorem3259.1BernoulliTrials3259.2DiscreteIndependentTrials..3409.3ContinuousIndependentTrials35610GeneratingFunctions36510.1DiscreteDistributions..36510.2BranchingProcesses37610.3ContinuousDensities39311MarkovChains40511.1Introduction..40511.2AbsorbingMarkovChains41611.3ErgodicMarkovChains.43311.4FundamentalLimitTheorem.44711.5MeanFirstPassageTime45212RandomWalks47112.1RandomWalksinEuclideanSpace.47112.2Gambler’sRuin48612.3ArcSineLaws.493Appendices499Index503
PAGE – 5 ============
Preface ProbabilitytheorybeganinseventeenthcenturyFrancewhenthetwogreatFrenchmathematicians,BlaisePascalandPierredeFermat,correspondedovertwoprob-lemsfromgamesofchance.ProblemslikethosePascalandFermatsolvedcontinuedtosuchearlyresearchersasHuygens,Bernoulli,andDeMoivreinestab-lishingamathematicaltheoryofprobability.Today,probabilitytheoryisawell-establishedbranchofmathematicsthatapplicationsineveryareaofscholarlyactivityfrommusictophysics,andindailyexperiencefromweatherpredictiontopredictingtherisksofnewmedicaltreatments.Thistextisdesignedforanintroductoryprobabilitycoursetakenbysophomores,juniors,andseniorsinmathematics,thephysicalandsocialsciences,engineering,andcomputerscience.Itpresentsathoroughtreatmentofprobabilityideasandtechniquesnecessaryforaunderstandingofthesubject.Thetextcanbeusedinavarietyofcourselengths,levels,andareasofemphasis.Foruseinastandardone-termcourse,inwhichbothdiscreteandcontinuousprobabilityiscovered,studentsshouldhavetakenasaprerequisitetwotermsofcalculus,includinganintroductiontomultipleintegrals.InordertocoverChap-ter11,whichcontainsmaterialonMarkovchains,someknowledgeofmatrixtheoryisnecessary.Thetextcanalsobeusedinadiscreteprobabilitycourse.Thematerialhasbeenorganizedinsuchawaythatthediscreteandcontinuousprobabilitydiscussionsarepresentedinaseparate,butparallel,manner.Thisorganizationdispelsanoverlyrigorousorformalviewofprobabilityandsomestrongpedagogicalvalueinthatthediscretediscussionscansometimesservetomotivatethemoreabstractcontinuousprobabilitydiscussions.Foruseinadiscreteprobabilitycourse,studentsshouldhavetakenonetermofcalculusasaprerequisite.Verylittlecomputingbackgroundisassumedornecessaryinordertoobtainfullbfromtheuseofthecomputingmaterialandexamplesinthetext.AlloftheprogramsthatareusedinthetexthavebeenwrittenineachofthelanguagesTrueBASIC,Maple,andMathematica.ThisbookisdistributedontheWebaspartoftheChanceProject,whichisde-votedtoprovidingmaterialsforbeginningcoursesinprobabilityandstatistics.Thecomputerprograms,solutionstotheodd-numberedexercises,andcurrenterrataarealsoavailableatthissite.Instructorsmayobtainallofthesolutionsbywritingtoeitheroftheauthors,[email protected]@swarthmore.edu.vii
PAGE – 6 ============
viiiPREFACEFEATURESLevelofrigorandemphasis:Probabilityisawonderfullyintuitiveandapplicableofmathematics.Wehavetriednottospoilitsbeautybypresentingtoomuchformalmathematics.Rather,wehavetriedtodevelopthekeyideasinasomewhatleisurelystyle,toprovideavarietyofinterestingapplicationstoprobability,andtoshowsomeofthenonintuitiveexamplesthatmakeprobabilitysuchalivelysubject.Exercises:Thereareover600exercisesinthetextprovidingplentyofoppor-tunityforpracticingskillsanddevelopingasoundunderstandingoftheideas.Intheexercisesetsareroutineexercisestobedonewithandwithouttheuseofacomputerandmoretheoreticalexercisestoimprovetheunderstandingofbasiccon-cepts.Moreexercisesareindicatedbyanasterisk.Asolutionmanualforalloftheexercisesisavailabletoinstructors.Historicalremarks:Introductoryprobabilityisasubjectinwhichthefunda-mentalideasarestillcloselytiedtothoseofthefoundersofthesubject.Forthisreason,therearenumeroushistoricalcommentsinthetext,especiallyastheydealwiththedevelopmentofdiscreteprobability.Pedagogicaluseofcomputerprograms:Probabilitytheorymakespredictionsaboutexperimentswhoseoutcomesdependuponchance.Consequently,itlendsitselfbeautifullytotheuseofcomputersasamathematicaltooltosimulateandanalyzechanceexperiments.Inthetextthecomputerisutilizedinseveralways.First,itprovidesalabora-torywherechanceexperimentscanbesimulatedandthestudentscangetafeelingforthevarietyofsuchexperiments.ThisuseofthecomputerinprobabilityhasbeenalreadybeautifullyillustratedbyWilliamFellerinthesecondeditionofhisfamoustextAnIntroductiontoProbabilityTheoryandItsApplications(NewYork:Wiley,1950).Inthepreface,Fellerwroteabouthistreatmentofincointossing:\Theresultsaresoamazingandsoatvariancewithcommonintuitionthatevensophisticatedcolleaguesdoubtedthatcoinsactuallymisbehaveastheorypredicts.Therecordofasimulatedexperimentisthereforeincluded.”Inadditiontoprovidingalaboratoryforthestudent,thecomputerisapowerfulaidinunderstandingbasicresultsofprobabilitytheory.Forexample,thegraphicalillustrationoftheapproximationofthestandardizedbinomialdistributionstothenormalcurveisamoreconvincingdemonstrationoftheCentralLimitTheoremthanmanyoftheformalproofsofthisfundamentalresult.Finally,thecomputerallowsthestudenttosolveproblemsthatdonotlendthemselvestoclosed-formformulassuchaswaitingtimesinqueues.Indeed,theintroductionofthecomputerchangesthewayinwhichwelookatmanyproblemsinprobability.Forexample,beingabletocalculateexactbinomialprobabilitiesforexperimentsupto1000trialschangesthewayweviewthenormalandPoissonapproximations.ACKNOWLEDGMENTSAnyonewritingaprobabilitytexttodayowesagreatdebttoWilliamFeller,whotaughtusallhowtomakeprobabilitycomealiveasasubjectmatter.Ifyou
PAGE – 9 ============
Chapter1DiscreteProbabilityDistributions 1.1SimulationofDiscreteProbabilitiesProbabilityInthischapter,weshallconsiderchanceexperimentswithanumberofpossibleoutcomes!1,!2,,!n.Forexample,werolladieandthepossibleoutcomesare1,2,3,4,5,6correspondingtothesidethatturnsup.WetossacoinwithpossibleoutcomesH(heads)andT(tails).Itisfrequentlyusefultobeabletorefertoanoutcomeofanexperiment.Forexample,wemightwanttowritethemathematicalexpressionwhichgivesthesumoffourrollsofadie.Todothis,wecouldletXi,i=1;2;3;4;representthevaluesoftheoutcomesofthefourrolls,andthenwecouldwritetheexpressionX1+X2+X3+X4forthesumofthefourrolls.TheXi’sarecalledrandomvariables.Arandomvari-ableissimplyanexpressionwhosevalueistheoutcomeofaparticularexperiment.Justasinthecaseofothertypesofvariablesinmathematics,randomvariablescantakeontvalues.LetXbetherandomvariablewhichrepresentstherollofonedie.Weshallassignprobabilitiestothepossibleoutcomesofthisexperiment.Wedothisbyassigningtoeachoutcome!janonnegativenumberm(!j)insuchawaythatm(!1)+m(!2)++m(!6)=1:Thefunctionm(!j)iscalledthedistributionfunctionoftherandomvariableX.Forthecaseoftherollofthediewewouldassignequalprobabilitiesorprobabilities1/6toeachoftheoutcomes.Withthisassignmentofprobabilities,onecouldwriteP(X4)=231
PAGE – 10 ============
2CHAPTER1.DISCRETEPROBABILITYDISTRIBUTIONStomeanthattheprobabilityis2=3thatarollofadiewillhaveavaluewhichdoesnotexceed4.LetYbetherandomvariablewhichrepresentsthetossofacoin.Inthiscase,therearetwopossibleoutcomes,whichwecanlabelasHandT.Unlesswehavereasontosuspectthatthecoincomesuponewaymoreoftenthantheotherway,itisnaturaltoassigntheprobabilityof1/2toeachofthetwooutcomes.Inbothoftheaboveexperiments,eachoutcomeisassignedanequalprobability.Thiswouldcertainlynotbethecaseingeneral.Forexample,ifadrugisfoundtobee30percentofthetimeitisused,wemightassignaprobability.3thatthedrugisethenexttimeitisusedand.7thatitisnote.Thislastexampleillustratestheintuitivefrequencyconceptofprobability.Thatis,ifwehaveaprobabilitypthatanexperimentwillresultinoutcomeA,thenifwerepeatthisexperimentalargenumberoftimesweshouldexpectthatthefractionoftimesthatAwilloccurisaboutp.Tocheckintuitiveideaslikethis,weshallithelpfultolookatsomeoftheseproblemsexperimentally.Wecould,forexample,tossacoinalargenumberoftimesandseeifthefractionoftimesheadsturnsupisabout1/2.Wecouldalsosimulatethisexperimentonacomputer.SimulationWewanttobeabletoperformanexperimentthatcorrespondstoagivensetofprobabilities;forexample,m(!1)=1=2,m(!2)=1=3,andm(!3)=1=6.Inthiscase,onecouldmarkthreefacesofasix-sideddiewithan!1,twofaceswithan!2,andonefacewithan!3.Inthegeneralcaseweassumethatm(!1),m(!2),,m(!n)areallrationalnumbers,withleastcommondenominatorn.Ifn>2,wecanimaginealongcylindricaldiewithacross-sectionthatisaregularn-gon.Ifm(!j)=nj=n,thenwecanlabelnjofthelongfacesofthecylinderwithan!j,andifoneoftheendfacescomesup,wecanjustrollthedieagain.Ifn=2,acoincouldbeusedtoperformtheexperiment.Wewillbeparticularlyinterestedinrepeatingachanceexperimentalargenum-beroftimes.Althoughthecylindricaldiewouldbeaconvenientwaytocarryoutafewrepetitions,itwouldbetocarryoutalargenumberofexperiments.Sincethemoderncomputercandoalargenumberofoperationsinaveryshorttime,itisnaturaltoturntothecomputerforthistask.RandomNumbersWemustacomputeranalogofrollingadie.Thisisdoneonthecomputerbymeansofarandomnumbergenerator.Dependingupontheparticularsoftwarepackage,thecomputercanbeaskedforarealnumberbetween0and1,oranintegerinagivensetofconsecutiveintegers.Inthecase,therealnumbersarechoseninsuchawaythattheprobabilitythatthenumberliesinanyparticularsubintervalofthisunitintervalisequaltothelengthofthesubinterval.Inthesecondcase,eachintegerhasthesameprobabilityofbeingchosen.
PAGE – 11 ============
1.1.SIMULATIONOFDISCRETEPROBABILITIES3.203309.762057.151121.623868.932052.415178.716719.967412.069664.670982.352320.049723.750216.784810.089734.966730.946708.380365.027381.900794Table1.1:SampleoutputoftheprogramRandomNumbers.LetXbearandomvariablewithdistributionfunctionm(!),where!isinthesetf!1;!2;!3g,andm(!1)=1=2,m(!2)=1=3,andm(!3)=1=6.Ifourcomputerpackagecanreturnarandomintegerinthesetf1;2;:::;6g,thenwesimplyaskittodoso,andmake1,2,and3correspondto!1,4and5correspondto!2,and6correspondto!3.Ifourcomputerpackagereturnsarandomrealnumberrintheinterval(0;1),thentheexpressionb6rc+1willbearandomintegerbetween1and6.(Thenotationbxcmeansthegreatestintegernotexceedingx,andisreadorofx.”)Themethodbywhichrandomrealnumbersaregeneratedonacomputerisdescribedinthehistoricaldiscussionattheendofthissection.ThefollowingexamplegivessampleoutputoftheprogramRandomNumbers.Example1.1(RandomNumberGeneration)TheprogramRandomNumbersgeneratesnrandomrealnumbersintheinterval[0;1],wherenischosenbytheuser.Whenwerantheprogramwithn=20,weobtainedthedatashowninTable1.1.2Example1.2(CoinTossing)Aswehavenoted,ourintuitionsuggeststhattheprobabilityofobtainingaheadonasingletossofacoinis1/2.Tohavethecomputertossacoin,wecanaskittopickarandomrealnumberintheinterval[0;1]andtesttoseeifthisnumberislessthan1/2.Ifso,weshallcalltheoutcomeheads;ifnotwecallittails.Anotherwaytoproceedwouldbetoaskthecomputertopickarandomintegerfromthesetf0;1g.TheprogramCoinTossescarriesouttheexperimentoftossingacoinntimes.Runningthisprogram,withn=20,resultedin:THTTTHTTTTHTTTTTHHTT.Notethatin20tosses,weobtained5headsand15tails.Letustossacoinntimes,wherenismuchlargerthan20,andseeifweobtainaproportionofheadsclosertoourintuitiveguessof1/2.TheprogramCoinTosseskeepstrackofthenumberofheads.Whenweranthisprogramwithn=1000,weobtained494heads.Whenweranitwithn=10000,weobtained5039heads.
25 KB – 518 Pages