《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(withpro
17、babilityq).NowconsiderSn,theabsolutevalueofthesimplerandomwalk.TheprocessIS1J,n11measuresateachtimeunittheabsolutedistanceofthesimplerandomwalkfromtheorigin.SomewhatsurprisinglySr,IisitselfaMarkovchain.ToprovethiswewillfirstshowthatifSn=i,thennomatterwhatitspreviousvaluestheprobabi1itythatS11equalsi
18、(asoppossedto-i)isp,/(pi+qj).PropossissitionIflSn.nlisasimplerandomwalk,thenPsn=isj=HSM=TP+qProofIfweletio=0anddefinej=maxkA)kn:it=O)then,sinceweknowtheactualofSl,itisclearthatPSn=小J=i,S=如,=ij=Ps11=s=.品|=如同=0NowtherearetwopossiblevaluesofthesequenceSi,.,SnforwhichSiI=i,.,S=iThefirstofwhichresultsinS
19、=andhasprobabilityU-JIir-itp-,2qTIAndthesecondresultsinS11=-iandhasprobability-JI-ip-3qHence央nJ,-1.PS=iS=AlSIt-J=fn-IStl=l=.,1.ij.：u；Prq2工+广(r-PP+andthepropositionisprovenFrompropositionS=+/or-/thatitfollowsuponconditioningonwhetherP1)isaMarkovchainWithtransitionrobabiIitiesJI+/”十PP+0,P.=14.2CHAPMAN
20、-KO1.MOGOROVEGUAT1.ONSANDC1.ASSSSISFICAT1.ONOFSTATESWehavealreadydefinedtheOne-StePtransitionprobabilitiesPifWenowdefinethe11-stcptransitionprobabilitiesP；tobetheprobabilitythataprocessinstateiwillbeinstateafternadditionaltransitions.Thatis,P/PXm=,nO,i,jO.OfcourseP；=P“.Thechapman-kolmogorovequations
21、providesamethodforcomputingthesen-steptransitionprobabiIities.TheseequationsareOPrB=耳母foralln,m0,allij.IandareestablishedbyobservingthatPT=PXf=PX.e=Xil=MXO=iPX=/X.=k.X0=iPXn=A-X0=i=fp:iOIfweletP11,denotethematrixofn-steptransitionprobabilities,thenequation()assertsthatPgM=Qprti)Wherethedotrepresents
22、matrixmultiplicationhence,Plfll=peprt-=p.p.p0.Twostatesiandjaccessibletoeachotheraresaidtocommunicate,andWewritetcj.PropossltiwCommunicationisanequivalencerelation.Thatis:ii.(ii) if/,；,then(iii) ifijandJk,then/k,thenthereexistsm,nsuchthatB,0,P,0.Hence,B=F-OSimiIarly1wemayshowthereexistsansforwhichP2
23、0.Twostatesthatcommunicatearesaidtobeinthesameclass;andbyProposition,anytwoclassesareeitherdisjointoridentical.WesaythattheMarkovchainisirreducibleifonlyoneclass-thatis,ifallstatescommunicatewitheachother.StateiissaidtohaveperioddifP=0whenevernisnotdivisiblebydanddisthegreatestintegerwithproperty.(I
24、fP.=0foralln0,thendefinetheperiodofitobeinfinite.)statewithperiod1issaidtobeaperiodic.1.et(7(r)denotetheperiodofi.Wenowthatperiodicityisaclassproperty.PROPOSITION4.2.2Ifi4j,thend(i)=d(j).Proof1.etmandnbesuchthatPP0,andsupposethatVrP,10.ThenP丁Ep；耳耳0,wherethesecondinequalityfollows,forinstance,sinceth
25、eleft-handsiderepresentstheprobabiIitythatstartinginjthechainwillbebackinjafter/+5+wtransitions,whereastheright-handsideistheprobabilityofthesameeventsubjecttothefurtherrestrictionthatthechainisinibothafterwandn+stransitions.Hence,d(7)dividesbothn+mandn+s+m;thus11+s+m-(n+m)=s,wheneverP*0.Therefore,d
26、(y)dividesd(i).AsimiIarargumentyieldsthatd(i)dividesd(j),thusd(i)=d(y)Foranystatesiandjdefine3betheprobabilitythat,startingini,thefirsttransitionintojoccursattimen.Formally,/=0f=P(Xd=y,X1,A=IJ-IlXO=01.etfv=Then0denotestheprobabilityofevermakingatransitionintostatej,giventhattheprocessstartsini.(Note
27、thatforij,4ispositiveif,andonlyif,jisaccessiblefromi).Statejissaidtoberecurrentiffh=1,andtransientotherwise.PROPOSITIONStatejisrecurrentif,andonlyif,EPi2lProofStatejisrecurrentif,withprobabilityl,aprocessstartingatjwilleventuallyreturn.However,bytheMarkovianpropertyitfollowsthattheprocessprobabilist
28、icallyrestartsitselfuponreturningtoj.Hence,withprobabi1ity1,itwillreturnagaintoj.Repeatingthisargument.,weseethat,withprobabi)ity1,thenumberofvisitstojwillbeinfiniteandwillthushaveinfiniteexpectation.Ontheotherhand,supposejistransient,theneachtimetheprocessreturnstojthereisapositiveprobabi1ity1-f.th
29、atitwillneveragainreturn;hencethenumberofvisitsisgeometricwithfinitemeanl(l-f1,).Bytheaboveargumentweseethatstatejisrecurrentif,andonlyif,EnumberofvisitstojX0=J=.But,letting1=PifX=j()OtherwiseItfollowsthatZAdenoteSthenumberofvisitstoj.sinced.=j=n1=P；，1.n-OJA-AfTheresultfollows.Theargumentleadingtoth
30、eabovepropositionisdoublyimportantforitalsoshowsthatatransientstatewillonlybevisitedafinitenumberoftimes(hencethenametransient).Thisleadstotheconclusionthatinafinite-stateMarkovchainnotallstatescanbetransient.Toseethis,supposethestatesare0,1,.,I/andsupposethattheyareal1transient.Thenafterafiniteamou
31、ntoftime(sayaftertimeT0)state0willneverbevisited,andafteratime(sayTl)state1willneverbevisited,andafteratime(sayT,)state2willneverbevisited,andsoon.Thus,afterafinitetimeT=maxTo,Ti,Tjnostateswillbevisited.ButastheprocessmustbeinsomestateaftertimeT,wearriveatacontradiction,whichshowsthatatleastoneofthe
32、statesmustberecurrent.Wewillusepropositiontoprovethatrecurrence,likeperiodicity,isaclassproperty.CorollaryIfiisProof1.etmrecurrentandij,thenjisrecurrent.andnbesuchthat0,7*70.Nowforanys0prnppandthusZP1.p：耳Z8andtheresultfollowsfromPropositionExample4.2（八）THESIMP1.ERANDOMWA1.K.TheMarkovchainwhosestates
33、pateisthesetofal1integersandhastransitionprobabilitiesEju=P=I-Aei=O,lWhereOpI,iscalledthesimplerandomwalk.Oneinterpretationofthisprocessisthatitrepresentsthewanderingsofadrunkenmanashewalksalongastraightline,notheristhatitrepresentsthewinningsofagamblerwhooneachplayofthegameeitherwinsorlosesonedolla
34、r.Sinceal1statesclearlycommunicateitfollowsfromcorollarythattheyareeitheralltransientoral1recurrent.SoletusconsiderstateOandattempttodetermineifisfiniteorinfinite.Sinceitisimpossibletobeeven(usingthegamblingmodelinterpretation)afteranoddnumberofplays,wemust,ofcourse,havethat年r=0,n=l,2,.Ontheotherhan
35、d,thegamblerwouldbeevenafter2ntrialsif,andonlyif,hewonnoftheseandlostnofthese.seachplayofthegameresultsinawinprobabilitypandalosswithprobabiIity-p,thedesiredprobabiIityisthusthebinomialprobabilityP=2,P(1p)n=v(p(l-p),n=l,2,3,n)!！Byusinganapproximation,duetoStirling,whichassertsthatn!-ne-石,wherewesayt
36、hata“-b*whenIim(an/b)=1,weobtain2(4川-p)”Nowitiseasytoverifythatifa,-bnthen,if,andonlyif,ZqCOO.Hence用willconvergeif,andonlyif,y(4Hl-p)v-lJ乃“does.However,4p(l-p)lwithequalityholdingif,andonlyif,P=1/2.hence,_G；=if,andonlyif,p=l2.Thus,thechainisrecurrentwhenp=l2andtransientifpl2When=1/2,theaboveprocessi
37、scalledasysaaetricrandomwalk.Wecouldalsolookatsymmetricrandomwalksinmorethenonedimension.Forinstance,inthetwo-dimensionalsymmetricrandomwalktheleft,right,up,ordowneachhavingprobability.Similarly,inthreedimensionstheprocesswould,withprobability,samemethodasintheone-dimensionalrandomwalkitcanbeshownth
38、atthetwo-dimensionalsymmetricrandomwalkisrecurrent,butallhigher-dimensionalrandomwalksarctransient.COroIIaryIfi0.SaythatWemissopportunity1ifXj.Ifwemissopportunity1,then1.etT1denotethenexttimeweenteri(7isfinitewithprobability1bycorollary).Saythatwemissopportunity2ifX.uj.Ifopportunity2ismissed,let71de
39、notethenexttimeweenteriandsaythatwemissopportunity3ifXr.,11j,andsoon.Itiseasytoseethattheopportunitynumberofthefirstsuccessisageometricrandomvariablewithmean1/：,andisthusfinitewithprobability1.Theresultfollowssinceibeingrecurrentimpiesthatthenumberofpotentialopportunitiesisinfinite.1.etjV.(r)denotet
40、henumberoftransitionsintojbytimet.IfjisrecurrentandX0=j,thenastheprocessprobabilisticallystartsoverupontransitionsintoj,itfollowsthattisarenewalprocessWilhinterarrivaldistributionf；,nl.IfX0=i,/j,andjisrecurrent,then,y(r),tissadelayedrenewalprocesswithinitialinterarrivaldistributionf.4.31.imitTheorem
41、sItiseasytoshowthatifstate;istransient,then-Byinterpretingtransitionsintostatejasbeingrenewals,weobtainthefollowingtheoremfromPropositions,and3.4.1ofChapter3.THEOREMIfiandjconununicate.then:(i)PjlimjV;(O/=l/Atf|Xo=/=l.5)!吧年7=1“hl(iii)Ifjisaperiodic,thenIimP=,j.(iv)/,jhasperiodl,henimP：=d.Ifstatejisr
42、ecurrent,thenwesaythatitispositiverecurrentif.andnidirecurrentifJUy=.Ifweletitfollowsthatarecurrentstatejispositiverecurrentif%oandnullrecurrentif,=o.Theproofofthefollowingpropositionisleftasanexercise.PROPOSITIONPositive(null)recurrenceisaclassproperly.Apositiverecurrent,aperiodicstateiscalledergod
43、ic.Beforepresentingatheoremthatshowshowtoobtainthelimitingprobabilitiesintheergodiccase,weneedthefollowingdefinition.DefinitionAprobabilitydistributionjp,oissaidtobestationeryfortheMarkovchainif与=S牝，OIftheprobabilitydistributionofxl,say,l=,x0=j,j()isaSlaIionarydistribution,thenHX1./=尸必=X=iXi=44=P,r-
44、0I-Oand.byinduction,OP=J=力PXX=PX=*A=S/=O=OHence,iftheinitialprobabilitydistributionisthestationarydistribution,thenXnwillhavethesamedistributionforall.Infact,asxn,woisaMarkovchain,iteasilyfollowsfromthisthatforeachmo.xn.xxn,mwillhavethesamejointdistributionforeachn;inotherwords,x,11owillbeastationar
45、yprocess.THEOREMAnirreducibleaperiodicMarkovchainbelongstooneofthefollowingtwoclasses:(i) Eitherthestatesarealltransientorallnullrecurrent;inthiscase,oas11foralli,jandthereexistsnoStationaiydistribution.(ii) Orelse,allstatesarepositiverecurrent,thatis,11j=Iim年0Inthiscase,忆.j=o.2.isastationarydistributionandthereexistsnootherstat
