Markov-chains-马尔科夫链.docx

《Markov-chains-马尔科夫链.docx》由会员分享，可在线阅读，更多相关《Markov-chains-马尔科夫链.docx（56页珍藏版）》请在第壹文秘上搜索。

1、MarkovChains4.1 INTRODUCTIONANDEXAMP1.ESConsiderastochasticprocessXn,n=0,1,2,.thattakesonafiniteorcountablenumberofpossiblevalues.Unlessotherwisementioned,thissetofpossiblewillbedenotedbythesetofnonnegativeintegers0,1,2,.IfX,=i,thentheprocessissaidtobeinstateiattimen.Wesupposethatwhenevertheprocessi

2、sinstatei,thereisafixedprobabilityP11thatitwillnextbeinstatej.Thatis,wesupposethat0PX1=jXnl=i|iXl=iJ.X=i=Pijforallstatesi0,i,.in-,i,jandalln20.SuchastochasticprocessisknownasaMarkovchain.Equation()maybeinterpretedasstatingthat,foraMarkovchain,theconditionaldistributionofanyfuturestateX11.1giventhepa

3、ststatesXo,X.,Xll-andthepresentstateX11zisindependentofthepaststatesanddependsonlyonthepresentstate.ThisiscalledtheMarkovianproperty.Theva1uePiJrepresentstheprobabilitythattheprocesswill,wheninstatei,nextmakeatransitionintostatej.Sinceprobabilitiesarenonnegativeandsincetheprocessmustmakeatransitioni

4、ntosomestate,WehavethataPi声O,i,j2O：Z4=l，i=o,1/?./.:1.etPdenotethematrixofonc-steptransitionprobabilitiesPij,sothat%0-%,1*EXAMP1.E4.1（八）TheM/G/lQueue.SupposethatcustomersarriveataservicecenterinaccordancewithaPoissonprocesswithrate.Thereisasingleserverandthosearrivalsfindingtheserverfreegoimmediately

5、intoservice;allotherswaitinlineuntiltheirserviceturn.TheservicetimesofsuccessivecustomersareassumedtobeindependentrandomvariableshavingacommondistributionG：andtheyarealsoassumedtobeindependentofthearrivalprocess.TheabovesystemiscalledtheM/G/lqueueingsystem.TheletterMstandsforthefactthattheinterarriv

6、aldistributionofcustomersisexponential,Gfortheservicedistribution；thenumber1indicatesthatthereisasingleserver.IfweletX(t)denotethenumberofcustomersinthesystematt,then；.X(t)110wouldnotpossesstheMarkovianpropertythattheconditionaldistributionofthefuturedependsonyonthepresentandnotonthepast.Forifweknow

7、thenumberinthesystemattimet,then,topredictfuturebehavior,whereaswewouldnotcarehowmuchtimehadelapsedsincethelastarrival(sincethearrivalprocessismemory1ess),wewouldcarehowlongthepersoninservicehadalreadybeenthere(sincetheservicedistributionGisarbitraryandthereforenotmemoryless).Asameansofgettingaround

8、theabovedi1emmaletusonlylookatthesystematmomentswhencustomersdepart.Thatis,letXndenotethenumberofcustomersleftbehindbythenthdeparture,n1.Also,letYndenotethenumberofcustomersarrivingduringtheserviceperiodofthe(n+l)stcustomer.WhenXn0,thenthdepartureleavesbehindXncustomers-ofwhichoneentersserviceandthe

9、otherXn-Iwaitinline.Hence,atthenextdeparturethesystemwillcontaintheXn-Icustomersthatwereinlineinadditiontoanyarrivalsduringtheservicetimeofthe(n+l)stcustomer.SinceasimiIarargumentholdswhenX,=0,WeseethatO)U=X.T+ZM1匕if,=0SinceYh,nN1,representthenumberofarrivalsinnonoverlappingserviceintervals,itfollow

10、s,thearrivalprocessbeingBoissonprocess,thattheyareindependentandOPYn=j=,eit-dG(x).j=0,1Form(4,1.2)and()tfollowsthatX.n=i,2,.)isaMarkovchainwithtransitionprobabiHtiesgivenbyPll=e山邛dG(x).j0JP,*P11=OotherwiseSupposethatcustomersEXAMP1.E4.1(B)TheM/G/lQueue.arriveatasingle-servercenterinaccordancewithana

11、rbitraryrenewalprocesshavinginterarrivaldistributionG.SupposefurtherthattheservicedistributionisexponentialwithrateKIfweletX11denotethenumberofcustomersinthesystemasseenbythentharrival,itiseasytoseethattheprocessX11,n21isaMarkovchain.TocomputethetransitionprobabilitiesPijforthisMarkovchain,letusfirs

12、tnotethat,aslongastherearecustomerstobeserved,thenumberofservicesinanylengthoftimetisaPoissonrandomvariablewithmeant.Thisistruesincethetimebetweensuccessiveservicesisexponentialand,asweknow,thisimpliesthatnumberofservicesthusconstitutesaPoissonprocess.Therefore,P1.i.券dG(r),i0Whichfollowssinceifanarr

13、ivalfindsiinthesystem,thenthenextarrivalwi11findi+1minusthenumbersserved,andtheprobabilitythatjwillbeservediseasilyseen(byconditioningonthetimebetweenthesuccessivearrivals)toequaltheright-handsideoftheabove.TheformulaforP10islittledifferent(itistheprobabilitythatatleasti+1Poissoneventsoccurinarandom

14、lengthoftimehavingdistributionG)andthusisgivenbyP-fe-G(O,i0RemarkThereadershouldnotethatintheprevioustwoexamplesWewereabletodiscoveranembeddedMarkowchainbylookingattheprocessonlyatcertaintimepoints,andbychoosingthesetimepointssoastoexploitthelackofmemoryoftheexponentialdistribution.Thisisoftenafruit

15、fulapproachforprocessesinwhichtheexponentialdistributionispresent.EXMP1.E4.1(C)SuasofIndependent,IdenticallyDistributedRandoavariables.TheGeneralRandomWalk.1.etXi,i1,beindependentandidenticallydistributedwithP(Xi=j)=aj,j=0,1,.IfweletSo=OandS,二x,r-lThenS11,n0isaMarkovchainforwhichFlj=aj-Sn,n0：iscalle

16、dthegeneralrandomwalkandwi11bestudiedinchapter7.EXAMP1.E4.1(D)TheAbsolutevalueoftheSimpleRandcmWallk.TherandomwalkSn,nl),whereS11=,Xi.issaidtobeasimplerandomWaIkifforsomep,0pl,P(X1=I)=P,P(Xi=-l)=q三l-p.Thusinthesimplerandomwalktheprocessalwayseithergoesuponestep(withprobabiIityp)ordownonestep(withprobabi