【精品PPT】probability(1-p).ppt

1 chapter2 probability statistics andtraffictheories copyright 2002 dr dharmap agrawalanddr qing anzeng allrightsreserved 2 outline introductionprobabilitytheoryandstatisticstheoryrandomvariablesprobabilitymassfunction pmf probabilitydensityfunction pdf cumulativedistributionfunction cdf expectedvalue nthmoment nthcentralmoment andvariancesomeimportantdistributionstraffictheorypoissonarrivalmodel etc basicqueuingsystemslittle slawbasicqueuingmodels 3 introduction severalfactorsinfluencetheperformanceofwirelesssystems densityofmobileuserscellsizemovingdirectionandspeedofusers mobilitymodels callrate calldurationinterference etc probability statisticstheoryandtrafficpatterns helpmakethesefactorstractable 4 probabilitytheoryandstatisticstheory randomvariables rvs letsbesampleassociatedwithexperimentexisafunctionthatassociatesarealnumbertoeachs srvscanbeoftwotypes discreteorcontinuousdiscreterandomvariable probabilitymassfunction pmf continuousrandomvariable probabilitydensityfunction pdf 5 discreterandomvariables inthiscase x s containsafiniteorinfinitenumberofvaluesthepossiblevaluesofxcanbeenumeratede g throwa6sideddiceandcalculatetheprobabilityofaparticularnumberappearing 1 2 3 4 6 0 1 0 3 0 1 0 1 0 2 0 2 5 probability number 6 discreterandomvariables theprobabilitymassfunction pmf p k ofxisdefinedas p k p x k fork 0 1 2 where1 probabilityofeachstateoccurring0 p k 1 foreveryk 2 sumofallstates p k 1 forallk 7 continuousrandomvariables inthiscase xcontainsaninfinitenumberofvaluesmathematically xisacontinuousrandomvariableifthereisafunctionf calledprobabilitydensityfunction pdf ofxthatsatisfiesthefollowingcriteria 1 f x 0 forallx 2 f x dx 1 8 cumulativedistributionfunction appliestoallrandomvariablesacumulativedistributionfunction cdf isdefinedas fordiscreterandomvariables forcontinuousrandomvariables 9 probabilitydensityfunction thepdff x ofacontinuousrandomvariablexisthederivativeofthecdff x i e 10 discreterandomvariablesexpectedvaluerepresentedbyeoraverageofrandomvariablenthmomentnthcentralmomentvarianceorthesecondcentralmoment expectedvalue nthmoment nthcentralmoment andvariance 2 var x e x e x 2 e x2 e x 2 11 expectedvalue nthmoment nthcentralmoment andvariance 1 2 3 4 5 6 0 1 0 3 0 1 0 1 0 2 0 2 e x 0 166 12 continuousrandomvariableexpectedvalueormeanvaluenthmomentnthcentralmomentvarianceorthesecondcentralmoment expectedvalue nthmoment nthcentralmoment andvariance 2 var x e x e x 2 e x2 e x 2 13 someimportantdiscreterandomdistributions poissone x andvar x geometrice x 1 1 p andvar x p 1 p 2 p x k p 1 p k 1 wherepissuccessprobability 14 someimportantdiscreterandomdistributions binomialoutofndice exactlykdicehavethesamevalue probabilitypkand n k dicehavedifferentvalues probability 1 p n k foranykdiceoutofn 15 someimportantcontinuousrandomdistributions normale x andvar x 2 16 someimportantcontinuousrandomdistributions uniforme x a b 2 andvar x b a 2 12 17 someimportantcontinuousrandomdistributions exponentiale x 1 andvar x 1 2 18 multiplerandomvariables therearecaseswheretheresultofoneexperimentdeterminesthevaluesofseveralrandomvariablesthejointprobabilitiesofthesevariablesare discretevariables p x1 xn p x1 x1 xn xn continuousvariables cdf fx1x2 xn x1 xn p x1 x1 xn xn pdf 19 independenceandconditionalprobability independence therandomvariablesaresaidtobeindependentofeachotherwhentheoccurrenceofonedoesnotaffecttheother thepmffordiscreterandomvariablesinsuchacaseisgivenby p x1 x2 xn p x1 x1 p x2 x2 p x3 x3 andforcontinuousrandomvariablesas fx1 x2 xn fx1 x1 fx2 x2 fxn xn conditionalprobability istheprobabilitythatx1 x1giventhatx2 x2 thenfordiscreterandomvariablestheprobabilitybecomes andforcontinuousrandomvariablesitis 20 bayestheorem atheoremconcerningconditionalprobabilitiesoftheformp x y read theprobabilityofx giveny iswherep x andp y aretheunconditionalprobabilitiesofxandyrespectively 21 importantpropertiesofrandomvariables sumpropertyoftheexpectedvalueexpectedvalueofthesumofrandomvariables productpropertyoftheexpectedvalueexpectedvalueofproductofstochasticallyindependentrandomvariables 22 importantpropertiesofrandomvariables sumpropertyofthevariancevarianceofthesumofrandomvariablesiswherecov xi xj isthecovarianceofrandomvariablesxiandxjandifrandomvariablesareindependentofeachother i e cov xi xj 0 then 23 importantpropertiesofrandomvariables distributionofsum forcontinuousrandomvariableswithjointpdffxy x y andifz x y thedistributionofzmaybewrittenaswhere zisasubsetofz foraspecialcasez x yifxandyareindependentvariables thefxy x y fx x fy y ifbothxandyarenonnegativerandomvariables thenpdfistheconvolutionoftheindividualpdfs fx x andfy y 24 centrallimittheorem thecentrallimittheoremstatesthatwheneverarandomsample x1 x2 xn ofsizenistakenfromanydistributionwithexpectedvaluee xi andvariancevar xi 2 wherei 1 2 n thentheirarithmeticmeanisdefinedby 25 centrallimittheorem thesamplemeanisapproximatedtoanormaldistributionwithe sn andvar sn 2 n thelargerthevalueofthesamplesizen thebettertheapproximationtothenormal thisisveryusefulwheninferencebetweensignalsneedstobeconsidered 26 poissonarrivalmodel apoissonprocessisasequenceofevents randomlyspacedintime forexample customersarrivingatabankandgeigercounterclicksaresimilartopacketsarrivingatabuffer therate ofapoissonprocessistheaveragenumberofeventsperunittime overalongtime 27 propertiesofapoissonprocess propertiesofapoissonprocessforatimeinterval 0 t theprobabilityofnarrivalsintunitsoftimeisfortwodisjoint nonoverlapping intervals t1 t2 and t3 t4 i e t1 t2 t3 t4 thenumberofarrivalsin t1 t2 isindependentofarrivalsin t3 t4 28 interarrivaltimesofpoissonprocess interarrivaltimesofapoissonprocesswepickanarbitrarystartingpointt0intime lett1bethetimeuntilthenextarrival wehavep t1 t p0 t e tthusthecumulativedistributionfunctionoft1isgivenbyft1 t p t1 t 1 e tthepdfoft1isgivenbyft1 t e ttherefore t1hasanexponentialdistributionwithmeanrate 29 exponentialdistribution similarlyt2isthetimebetweenfirstandsecondarrivals wedefinet3asthetimebetweenthesecondandthirdarrivals t4asthetimebetweenthethirdandfourtharrivalsandsoon therandomvariablest1 t2 t3 arecalledtheinterarrivaltimesofthepoissonprocess t1 t2 t3 areindependentofeachotherandeachhasthesameexponentialdistributionwithmeanarrivalrate 30 memorylessandmergingproperties memorylesspropertyarandomvariablexhasthepropertythat thefutureisindependentofthepast i e thefactthatithasn thappenedyet tellsusnothingabouthowmuchlongeritwilltakebeforeitdoeshappen mergingpropertyifwemergenpoissonprocesseswithdistributionsfortheinterarrivaltimes1 e itwherei 1 2 nintoonesingleprocess thentheresultisapoissonprocessforwhichtheinterarrivaltimeshavethedistribution1 e twithmean 1 2 n 31 basicqueuingsystems whatisqueuingtheory queuingtheoryisthestudyofqueues sometimescalledwaitinglines canbeusedtodescriberealworldqueues ormoreabstractqueues foundinmanybranchesofcomputerscience suchasoperatingsystems basicqueuingtheoryqueuingtheoryisdividedinto3mainsections trafficflowschedulingfacilitydesignandemployeeallocation 32 kendall snotation d g kendallin1951proposedastandardnotationforclassifyingqueuingsystemsintodifferenttypes accordinglythesystemsweredescribedbythenotationa b c d ewhere 33 kendall snotation aandbcantakeanyofthefollowingdistributionstypes 34 little slaw assumingaqueuingenvironmenttobeoperatinginastablesteadystatewhereallinitialtransientshavevanished thekeyparameterscharacterizingthesystemare themeansteadystateconsumerarrivaln theaverageno ofcustomersinthesystemt themeantimespentbyeachcustomerinthesystemwhichgivesn t 35 markovprocess amarkovprocessisoneinwhichthenextstateoftheprocessdependsonlyonthepresentstate irrespectiveofanypreviousstatestakenbytheprocess theknowledgeofthecurrentstateandthetransitionprobabilitiesfromthisstateallowsustopredictthenextstate 36 birth deathprocess specialtypeofmarkovprocessoftenusedtomodelapopulation or no ofjobsinaqueue if atsometime thepopulationhasnentities njobsinaqueue thenbirthofanotherentity arrivalofanotherjob causesthestatetochangeton 1 ontheotherhand adeath ajobremovedfromthethequeueforservice wouldcausethestatetochangeton 1 anystatetransitionscanbemadeonlytooneofthetwoneighboringstates 37 thestatetransitiondiagramofthecontinuousbirth deathprocess statetransitiondiagram 0 1 2 n 1 n n 1 0 1 1 2 2 3 n 2 n 1 n 1 n n n 1 n 1 n 2 38 m m 1 orm m 1queuingsystem whenacustomerarrivesinthissystemitwillbeservediftheserverisfree otherwisethecustomerisqueued inthissystemcustomersarriveaccordingtoapoissondistributionandcompetefortheserviceinafifo firstinfirstout manner servicetimesareindependentidenticallydistributed iid randomvariables thecommondistributionbeingexponential 39 queuingmodelandstatetransitiondiagram them m 1 queuingmodel thestatetransitiondiagramofthem m 1 queuingsystem 40 equilibriumstateequations ifmeanarrivalrateis andmeanservicerateis i 0 1 2 bethenumberofcustomersinthesystemandp i bethestateprobabilityofthesystemhavingicustomers fromthestatetransitiondiagram theequilibriumstateequationsaregivenby 41 trafficintensity weknowthatthep 0 istheprobabilityofserverbeingfree sincep 0 0 thenecessaryconditionforasystembeinginsteadystateis thismeansthatthearrivalratecannotbemorethantheservicerate otherwiseaninfinitequeuewillformandjobswillexperienceinfiniteservicetime 42 queuingsystemmetrics 1 p 0 istheprobabilityoftheserverbeingbusy therefore wehavep i i 1 theaveragenumberofcustomersinthesystemisls theaveragedwelltimeofcustomersisws 43 queuingsystemmetrics theaveragequeuinglengthis theaveragewaitingtimeofc