Markov-chains-马尔科夫链.docx

MarkovChains4.1 INTRODUCTIONANDEXAMP1.ESConsiderastochasticprocessXn,n=0,1,2,.thattakesonafiniteorcountablenumberofpossiblevalues.Unlessotherwisementioned,thissetofpossiblewillbedenotedbythesetofnonnegativeintegers0,1,2,.IfX,=i,thentheprocessissaidtobeinstateiattimen.Wesupposethatwhenevertheprocessisinstatei,thereisafixedprobabilityP11thatitwillnextbeinstatej.Thatis,wesupposethat0PX"1=jXnl=i|iXl=iJ.X=i=Pijforallstatesi0,i,.in-,i,jandalln20.SuchastochasticprocessisknownasaMarkovchain.Equation()maybeinterpretedasstatingthat,foraMarkovchain,theconditionaldistributionofanyfuturestateX11.1giventhepaststatesXo,X.,Xll-andthepresentstateX11zisindependentofthepaststatesanddependsonlyonthepresentstate.ThisiscalledtheMarkovianproperty.Theva1uePiJrepresentstheprobabilitythattheprocesswill,wheninstatei,nextmakeatransitionintostatej.Sinceprobabilitiesarenonnegativeandsincetheprocessmustmakeatransitionintosomestate,WehavethataPi声O,i,j2O：Z4=l，i=o,1/?./.:1.etPdenotethematrixofonc-steptransitionprobabilitiesPij,sothat%0-%,1*EXAMP1.E4.1（八）TheM/G/lQueue.SupposethatcustomersarriveataservicecenterinaccordancewithaPoissonprocesswithrate.Thereisasingleserverandthosearrivalsfindingtheserverfreegoimmediatelyintoservice;allotherswaitinlineuntiltheirserviceturn.TheservicetimesofsuccessivecustomersareassumedtobeindependentrandomvariableshavingacommondistributionG：andtheyarealsoassumedtobeindependentofthearrivalprocess.TheabovesystemiscalledtheM/G/lqueueingsystem.TheletterMstandsforthefactthattheinterarrivaldistributionofcustomersisexponential,Gfortheservicedistribution；thenumber1indicatesthatthereisasingleserver.IfweletX(t)denotethenumberofcustomersinthesystematt,then；.X(t)11>0wouldnotpossesstheMarkovianpropertythattheconditionaldistributionofthefuturedependsonyonthepresentandnotonthepast.Forifweknowthenumberinthesystemattimet,then,topredictfuturebehavior,whereaswewouldnotcarehowmuchtimehadelapsedsincethelastarrival(sincethearrivalprocessismemory1ess),wewouldcarehowlongthepersoninservicehadalreadybeenthere(sincetheservicedistributionGisarbitraryandthereforenotmemoryless).Asameansofgettingaroundtheabovedi1emmaletusonlylookatthesystematmomentswhencustomersdepart.Thatis,letXndenotethenumberofcustomersleftbehindbythenthdeparture,n1.Also,letYndenotethenumberofcustomersarrivingduringtheserviceperiodofthe(n+l)stcustomer.WhenXn>0,thenthdepartureleavesbehindXncustomers-ofwhichoneentersserviceandtheotherXn-Iwaitinline.Hence,atthenextdeparturethesystemwillcontaintheXn-Icustomersthatwereinlineinadditiontoanyarrivalsduringtheservicetimeofthe(n+l)stcustomer.SinceasimiIarargumentholdswhenX,=0,WeseethatO)U=X.T+ZM'>°1匕if×,=0SinceYh,nN1,representthenumberofarrivalsinnonoverlappingserviceintervals,itfollows,thearrivalprocessbeingBoissonprocess,thattheyareindependentandOPYn=j=,e'it-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-servercenterinaccordancewithanarbitraryrenewalprocesshavinginterarrivaldistributionG.SupposefurtherthattheservicedistributionisexponentialwithrateKIfweletX11denotethenumberofcustomersinthesystemasseenbythentharrival,itiseasytoseethattheprocessX11,n21isaMarkovchain.TocomputethetransitionprobabilitiesPijforthisMarkovchain,letusfirstnotethat,aslongastherearecustomerstobeserved,thenumberofservicesinanylengthoftimetisaPoissonrandomvariablewithmeant.Thisistruesincethetimebetweensuccessiveservicesisexponentialand,asweknow,thisimpliesthatnumberofservicesthusconstitutesaPoissonprocess.Therefore,P1.i.券dG(r),i0Whichfollowssinceifanarrivalfindsiinthesystem,thenthenextarrivalwi11findi+1minusthenumbersserved,andtheprobabilitythatjwillbeservediseasilyseen(byconditioningonthetimebetweenthesuccessivearrivals)toequaltheright-handsideoftheabove.TheformulaforP10islittledifferent(itistheprobabilitythatatleasti+1PoissoneventsoccurinarandomlengthoftimehavingdistributionG)andthusisgivenbyP-fe-G(O,i0RemarkThereadershouldnotethatintheprevioustwoexamplesWewereabletodiscoveranembeddedMarkowchainbylookingattheprocessonlyatcertaintimepoints,andbychoosingthesetimepointssoastoexploitthelackofmemoryoftheexponentialdistribution.Thisisoftenafruitfulapproachforprocessesinwhichtheexponentialdistributionispresent.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：iscalledthegeneralrandomwalkandwi11bestudiedinchapter7.EXAMP1.E4.1(D)TheAbsolutevalueoftheSimpleRandcmWallk.TherandomwalkSn,n>l),whereS11=,Xi.issaidtobeasimplerandomWaIkifforsomep,0<p<l,P(X1=I)=P,P(Xi=-l)=q三l-p.Thusinthesimplerandomwalktheprocessalwayseithergoesuponestep(withprobabiIityp)ordownonestep(withprobabilityq).NowconsiderSn,theabsolutevalueofthesimplerandomwalk.TheprocessIS1J,n11measuresateachtimeunittheabsolutedistanceofthesimplerandomwalkfromtheorigin.SomewhatsurprisinglySr,IisitselfaMarkovchain.ToprovethiswewillfirstshowthatifSn=i,thennomatterwhatitspreviousvaluestheprobabi1itythatS11equalsi(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=andhasprobabilityU-JIir-itp-,2qTIAndthesecondresultsinS11=-iandhasprobability"-JI-i<p-3qHence央nJ,-1.PS"=iS=AlSIt-J=fn-IStl=l=.,1.ij.：u；Pr'q2工+广"(r'-PP'+andthepropositionisprovenFrompropositionS=+/or-/thatitfollowsuponconditioningonwhetherP<IH+Ikl=4sM,S=Ps,“=i+1|S«="帚Hence,ISJ>1)isaMarkovchainWithtransitionrobabiIitiesJI""+/”十PP'+">0,P.=14.2CHAPMAN-KO1.MOGOROVEGUAT1.ONSANDC1.ASSSSISFICAT1.ONOFSTATESWehavealreadydefinedtheOne-StePtransitionprobabilitiesPifWenowdefinethe11-stcptransitionprobabilitiesP；tobetheprobabilitythataprocessinstateiwillbeinstateafternadditionaltransitions.Thatis,P/PXm=,nO,i,jO.OfcourseP；=P“.Thechapman-kolmogorovequationsprovidesamethodforcomputingthesen-steptransitionprobabiIities.TheseequationsareOPrB=£耳母foralln,m0,allij.IandareestablishedbyobservingthatPT=PXf=PX".e=Xil=MXO=iPX=/X.=k.X0=iPXn=A-X0=i=fp:iOIfweletP'11,denotethematrixofn-steptransitionprobabilities,thenequation()assertsthatPgM="Qprti)Wherethedotrepresentsmatrixmultiplicationhence,Plfll=peprt-=p.p.p<*-2)=pnAndthusP*'0maybecalculatedbymultiplyingthematrixPbyitselfntimes.Statejissaidtobeaccessiblefromstateiifforsomen0,/>0.Twostatesiandjaccessibletoeachotheraresaidtocommunicate,andWewritetcj.PropossltiwCommunicationisanequivalencerelation.Thatis:ii.(ii) if/,<->；,then(iii) ifijandJk,then/<k.ProofThefirsttwopartsfollowtriviallyfromthedefinitionofcommunication.Toprove(iii),supposethatigJandJ÷>k,thenthereexistsm,nsuchthatB,>0,P,">0.Hence,B=>F-OSimiIarly1wemayshowthereexistsansforwhichP2>0.Twostatesthatcommunicatearesaidtobeinthesameclass;andbyProposition,anytwoclassesareeitherdisjointoridentical.WesaythattheMarkovchainisirreducibleifonlyoneclass-thatis,ifallstatescommunicatewitheachother.StateiissaidtohaveperioddifP"=0whenevernisnotdivisiblebydanddisthegreatestintegerwithproperty.(IfP".=0foralln>0,thendefinetheperiodofitobeinfinite.)statewithperiod1issaidtobeaperiodic.1.et(7(r)denotetheperiodofi.Wenowthatperiodicityisaclassproperty.PROPOSITION4.2.2Ifi4j,thend(i)=d(j).Proof1.etmandnbesuchthatP"P">0,andsupposethatVrP,'1>0.ThenP丁Ep；耳耳0,wherethesecondinequalityfollows,forinstance,sincetheleft-handsiderepresentstheprobabiIitythatstartinginjthechainwillbebackinjafter/»+5+wtransitions,whereastheright-handsideistheprobabilityofthesameeventsubjecttothefurtherrestrictionthatthechainisinibothafterwandn+stransitions.Hence,d(7)dividesbothn+mandn+s+m;thus11+s+m-(n+m)=s,wheneverP*>0.Therefore,d(y)dividesd(i).AsimiIarargumentyieldsthatd(i)dividesd(j),thusd(i)=d(y)Foranystatesiandjdefine£3betheprobabilitythat,startingini,thefirsttransitionintojoccursattimen.Formally,/=0f=P(Xd=y,X1,A=IJ-IlXO=01.etfv=Then0denotestheprobabilityofevermakingatransitionintostatej,giventhattheprocessstartsini.(Notethatforij,4ispositiveif,andonlyif,jisaccessiblefromi).Statejissaidtoberecurrentiffh=1,andtransientotherwise.PROPOSITIONStatejisrecurrentif,andonlyif,EPi2lProofStatejisrecurrentif,withprobabilityl,aprocessstartingatjwilleventuallyreturn.However,bytheMarkovianpropertyitfollowsthattheprocessprobabilisticallyrestartsitselfuponreturningtoj.Hence,withprobabi1ity1,itwillreturnagaintoj.Repeatingthisargument.,weseethat,withprobabi)ity1,thenumberofvisitstojwillbeinfiniteandwillthushaveinfiniteexpectation.Ontheotherhand,supposejistransient,theneachtimetheprocessreturnstojthereisapositiveprobabi1ity1-f.thatitwillneveragainreturn;hencethenumberofvisitsisgeometricwithfinitemeanl(l-f1,).Bytheaboveargumentweseethatstatejisrecurrentif,andonlyif,EnumberofvisitstojX0=J=.But,letting1=PifX"=j'()OtherwiseItfollowsthatZAdenoteSthenumberofvisitstoj.sinced×.=j=n1=>=P；，1.n-OJA-»AfTheresultfollows.Theargumentleadingtotheabovepropositionisdoublyimportantforitalsoshowsthatatransientstatewillonlybevisitedafinitenumberoftimes(hencethenametransient).Thisleadstotheconclusionthatinafinite-stateMarkovchainnotallstatescanbetransient.Toseethis,supposethestatesare0,1,.,I/andsupposethattheyareal1transient.Thenafterafiniteamountoftime(sayaftertimeT0)state0willneverbevisited,andafteratime(sayTl)state1willneverbevisited,andafteratime(sayT,)state2willneverbevisited,andsoon.Thus,afterafinitetimeT=maxTo,Ti,Tjnostateswillbevisited.ButastheprocessmustbeinsomestateaftertimeT,wearriveatacontradiction,whichshowsthatatleastoneofthestatesmustberecurrent.Wewillusepropositiontoprovethatrecurrence,likeperiodicity,isaclassproperty.CorollaryIfiisProof1.etmrecurrentandij,thenjisrecurrent.andnbesuchthat">0,7*7>0.Nowforanys0prnppandthusZP1.p：耳Z8andtheresultfollowsfromPropositionExample4.2（八）THESIMP1.ERANDOMWA1.K.TheMarkovchainwhosestatespateisthesetofal1integersandhastransitionprobabilitiesEju=P=I-Aei=O,±lWhereO<p<I,iscalledthesimplerandomwalk.Oneinterpretationofthisprocessisthatitrepresentsthewanderingsofadrunkenmanashewalksalongastraightline,notheristhatitrepresentsthewinningsofagamblerwhooneachplayofthegameeitherwinsorlosesonedollar.Sinceal1statesclearlycommunicateitfollowsfromcorollarythattheyareeitheralltransientoral1recurrent.SoletusconsiderstateOandattempttodetermineifisfiniteorinfinite.Sinceitisimpossibletobeeven(usingthegamblingmodelinterpretation)afteranoddnumberofplays,wemust,ofcourse,havethat年r=0,n=l,2,.Ontheotherhand,thegamblerwouldbeevenafter2ntrialsif,andonlyif,hewonnoftheseandlostnofthese.seachplayofthegameresultsinawinprobabilitypandalosswithprobabiIity-p,thedesiredprobabiIityisthusthebinomialprobabilityP=2,P(1p)n=v(p(l-p)",n=l,2,3,n)"!！Byusinganapproximation,duetoStirling,whichassertsthatn!-n"""e-石,wherewesaythata“-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,theaboveprocessiscalledasysaaetricrandomwalk.Wecouldalsolookatsymmetricrandomwalksinmorethenonedimension.Forinstance,inthetwo-dimensionalsymmetricrandomwalktheleft,right,up,ordowneachhavingprobability.Similarly,inthreedimensionstheprocesswould,withprobability,samemethodasintheone-dimensionalrandomwalkitcanbeshownthatthetwo-dimensionalsymmetricrandomwalkisrecurrent,butallhigher-dimensionalrandomwalksarctransient.COroIIaryIfi<jandjisrecurrent,thenf=l.PrfSupposeXO=i,andletnbesuchthatPj>0.SaythatWemissopportunity1ifXj.Ifwemissopportunity1,then1.etT1denotethenexttimeweenteri(7isfinitewithprobability1bycorollary).Saythatwemissopportunity2ifX.uj.Ifopportunity2ismissed,let71denotethenexttimeweenteriandsaythatwemissopportunity3ifXr.,11j,andsoon.Itiseasytoseethattheopportunitynumberofthefirstsuccessisageometricrandomvariablewithmean1/：,andisthusfinitewithprobability1.Theresultfollowssinceibeingrecurrentimpiesthatthenumberofpotentialopportunitiesisinfinite.1.etjV.(r)denotethenumberoftransitionsintojbytimet.IfjisrecurrentandX0=j,thenastheprocessprobabilisticallystartsoverupontransitionsintoj,itfollowsthatt>isarenewalprocessWilhinterarrivaldistributionf；,nl.IfX0=i,/<->j,andjisrecurrent,then,y(r),tissadelayedrenewalprocesswithinitialinterarrivaldistributionf.4.31.imitTheoremsItiseasytoshowthatifstate;istransient,then<8foralli,11-lmeaningthat,startingini,theexpectednumberoftransitionsintostatejisfinite.Asaconsequenceitfollowsthatforjtransientoasn.1.etidenotetheexpectednumberoftransitionsneededtoreturntostatej.Thatis,ifjistransient£叫ifjisrecurrent>-Byinterpretingtransitionsintostatejasbeingrenewals,weobtainthefollowingtheoremfromPropositions,and3.4.1ofChapter3.THEOREMIfiandjconununicate.then:(i)PjlimjV;(O/=l/Atf|Xo=/=l.5)!吧£年7=1“hl(iii)Ifjisaperiodic,thenIimP"=,j.(iv)/,jhasperiod<l,henimP：=d.Ifstatejisrecurrent,thenwesaythatitispositiverecurrentif.<«>andnidirecurrentifJUy=.Ifweletitfollowsthatarecurrentstatejispositiverecurrentif%>oandnullrecurrentif",=o.Theproofofthefollowingpropositionisleftasanexercise.PROPOSITIONPositive(null)recurrenceisaclassproperly.Apositiverecurrent,aperiodicstateiscalledergodic.Beforepresentingatheoremthatshowshowtoobtainthelimitingprobabilitiesintheergodiccase,weneedthefollowingdefinition.DefinitionAprobabilitydistributionjp,oissaidtobestationeryfortheMarkovchainif与=S牝，OIftheprobabilitydistributionofxl,say,l=,x0=j,j()isaSlaIionarydistribution,thenHX1./=£尸必=X°=i'X"i=£44=P,r-0I-Oand.byinduction,OP'=J=力PX"X="PX="=*A=S/=O=OHence,iftheinitialprobabilitydistributionisthestationarydistribution,thenXnwillhavethesamedistributionforall.Infact,asxn,woisaMarkovchain,iteasilyfollowsfromthisthatforeachmo.xn.xxn,mwillhavethesamejointdistributionforeachn;inotherwords,x,11owillbeastationaryprocess.THEOREMAnirreducibleaperiodicMarkovchainbelongstooneofthefollowingtwoclasses:(i) Eitherthestatesarealltransientorallnullrecurrent;inthiscase,oas11foralli,jandthereexistsnoStationaiydistribution.(ii) Orelse,allstatesarepositiverecurrent,thatis,11j=Iim年>0Inthiscase,忆.j=o.2.isastationary'distributionandthereexistsnootherstat