DOC

Markov

By Maria Thomas,2014-07-23 23:36
9 views 0
MarkovMarkov

    Markov

Chin.Quart2008,23(2):.ofMath

    ;207214

    ;MarkovChainInducedbyRandom

    ;DynamicalSystemonGraph

    ;ZHENGLIUChaoyang2

    ;(1.DepartmentofAppliedMathematics,DonghuaUniversity,Shanghai201620,China;2.Zhengzhou

    ;DongxifangComputerNetworkEngineeringLimited,HenanUniversity,Zhengzhou450008,China)

    ;Abstract:Inthispaper,wedefineamodelofrandomdynamicalsystems(RDS)ongraphs ;andprovethattheyareactuallyhomogeneousdiscrete-timeMarkovchains.Moreover,a ;necessaryandSUflicientconditioniSobtainedforthattwostatevectorscancommunicate ;witheachotherinarandomdynamicalsystem(RDS1.

    ;Keywords:randomdynamicalsystem(RDS);Markovchain;communicate ;2000MRSubjectClassiflcation:37B99,68Q20

    ;CLCnumber:O157.6DocumentCOde:A

    ;ArtkleID:1002-0462(20081020207-08

    ;?1.RandomDynamicalSystem

    ;Inthedevelopmentofmathematicalfoundationsforatheoryofcomputersimulation,the ;studyofaclassofdiscretedynamicalsystemsongraphsisofparticularimportance[24.

    ;Ingeneral,adiscretedynamicalsystemisasysteminwhichtheevolutionofthevariables ;ismeasuredindiscretetimesteps.Thebehaviorofthesystemisgovernedbyadifference ;equation,orareturnmap,thatgivesthe(n+1)thvalueofvariablesasafunctionofthe

    ;precedingnthvalueofthevariables.Thatistosay,itcanbecharacterizedasaniterated ;function.Adiscretedynamicalsystemshowscomplexbehavioreveninsimplesystemswith

    ;fewvariables6.

    ;Inthispaper,weconstructamodelofrandomdynamicalsystemsongraphsasfollows ;LetG:(E)beagraphwithvertexsetV=andedgesetE.Foreachvertex

    ;i,1in,thereisastatezt?F2={0,1).NowweupdatethestateztwithanewstateYt,

    ;Receiveddate:2007.10-30

    ;Foundationitem:SupposedbytheScienceFoundationofDonghuaUniversity ;Biography:ZHENGJie(1979-),female,nativeofXingtai,Hebei,alecturerofDonghuaUniversity,Ph.D.,

    ;engagesincombinatoricsandgraphtheory.

    ;

    ;CHINESEQUARTERLYJOURNALOFMATHEMATICSVb1.23

    ;whichisararldomvariablewiththefollowingdistribution

    ;where

;withprobabilitypt,

    ;withprobability1,

    ;Dl=0and(,J)?E)

    ;Dl(i,J)?E)

    ;Asusual,denotethesetof0-1vectorsofdimensionnby ;Definition1.1

    ;(1.1)

    ;LetG=(E)beagraphonV=.Wecalltherarldommapping ;Ran,G:,

    ;(Xl,X2,…,zn)H(!,l,!,2,…,)

    ;ARandomDynamicalSystem(RDS)onG,whereyi(i=1,2,…,n)aredeterminedby(1.1)

    ;Definition1.2ForaRDSRan,G,itsfunctionaldigraphr([Ran,G)isdefinedasan ;arclabeleddirectedgraphwiththevertexsetandthearCset ;{(,)l,J?FandPr([Ran,G()=J)>0),

    ;wherePr([Ran,G()=J)istheprobabilityoftheevent[Ran,G()=Jandthelabelofthe ;arCfromItoJisPr([Ran,G()=).

    ;Example1.3LetGbeagraphofwithvertices1,2,3,4andedgesetE:{(1,2),(2,3),

    Ran,G)isshownasFigure1. ;(3,4)).ThenbyDefinition1.2r(

    ;RecallsomeimportantdefinitionsofaMarkovchain ;Definition2.1?Letx0

    ;,

    ;Xl,X2,…be

    ;thatx0,X1,2,…formaMarkovchainiffor

    ;asequenceofintegerrarldomvariables.Wesay ;anyintegersi0,il,?--,t,

    ;Pr(t=i,IZo=io,X1=il,…,Xt1=it1)=Pr(=itlXt1=it-1)

    ;WethinkofthevaluesoftheXt’SasbeingthestatesoftheMarkovchain.IfXt=it, ;then

    ;wesaytheprocessisinstateitattimet.Moreover,ifXt=itandXt+1=it+1,thenwesay

    ;thereisatransitionfromstateittostateit+lattimet. ;Definition2.21IAMarkovchainx0

    ;,

    ;Xl,X2,…issaidtobehomogeneousifitsatisties

    ;thepropertythatforallintegersm,n0,ifPr(n=J)>0andPr(m=J)>0,then

    ;Pr(Xn+l=1=J)=Pr(Xm+1=il=J)

    ;Definition2.3【】InahomogeneousMarkovchainx0

    ;,

    ;Xl,X2,…,let

    ;PO=Pr(Xn+1==i)

    ;

    ;No.2ZHENGJieetal:MarkovChainInducedby ;andcallPijthetransitionprobabilityfromstateitostateJ.ThematrixP=iscalled

    ;thetransitionprobabilitymatrixoftheMarkovchain. ;NOWwestateourmainresultofthissection.

;

    ;Figure1theFunctionalDigraphofG

    ;Theorem2.4Therandomvectorsequence

    ;,Ran,G(),Ran,G(),Ran,G.(),…

    ;isahomogeneousMarkovchain.

    ;(

    ;ProofLetRan,GbearandomdynamicalsystemonG=(E),whereV

    ;beaninitial:rarldomstatevectorinFn.Forconvenience,denote ;X0=X,X1=Ran,G(),X2:Ran,G(),….

    ;=

    ;n,and

    ;SupposetheeventRan,c](xt)=Xt+l,t0happenswithpositiveprobability.Let/0,Il,…,

    ;

    ;210CHINESEQUARTERLYJOURNALOFMATHEMATICSVb1.23

    ;bedeterminedvectorsin.Firstwehavethefollowingassertion: ;Pr(Xo=Io,X1:I1,?,Xt=It)

    ;=

    ;Pr(Xo=~)Pr(X1=I1lXo=~)Pr(X2=l1=I1)

    ;?

    ;Pr(t=lt1=It1)

    ;Itcanbeillustratedasfollows.Iftheevent(X0

    ;firsttheeventX0=/0musthappen,thatis,the

    ;:

    ;Io)n(X1:I1)n…n(Xt:It)happens,

    ;initialconditionmustbesatisfied.Thatis

    ;whythefirstfactorisPr(Xo=/0).Atthenextstep,theeventX1:I1happensconditioned

    ;ontheeventX0=/0.SowehavethefactorPr(l=I1lX0:/0).Whenthethirdstepbegins, ;thestatevectoroftheRDSRan,GisnowXl:I1.Accordingtothedefinitionof[Ran,G], ;thestateofavertexdependsonthestatesofitsadjacentverticesanditself.Sothestate

    ;vectorIlcanbechangedintoarandomstatevectortotallydependingonI1itselfandhaving

    ;nothingtodowith/0.IfX2=/2,thentheremustbeafactorPr(X2=Is[X1:I1),whichis ;theprobabilityofthedesiredeventhappeningatthethirdstep.Therestcanbededucedby

    ;analogy.

    ;Bythedefinitionoftheconditionalprobabilityandtheaboveargument,wehave ;Pr(Xt=l=Io,X1=I1,…,Xt1=It1)

    ;Pr(Xo=Io,X1=I1,…,Xt1=It1,Xt=It)

    ;Pr(Xo=Io.X1=

    ;Pr(Xo=Io)Pr(X1

    ;l,…,Xt1=It1)

    ;=

    ;I1lXo=Io)…Pr(t=lt1=It1)

    ;Pr(Xo=Io)Pr(X1=I1lXo:Io)

    ;=

    ;Pr(Xt:l咒一1=It1)

;ThustheMarkovpropertyholds.

    ;?

    ;Pr(Xt1=It1lXt2=It2)

    ;Easytoseethatthetransitionprobabilityfromastatevectortoanotherdoesnotdepend

    ;ont.ThenX0,X1,X2…isahomogeneousMarkovchain.Thiscompletestheproof. ;?3.ANecessaryandSucientCondition

    ;forCommunication

    ;InthetheoryoftheMarkovchain,communicationisoneofthemostimportantconcepts

    Let. ;Definition3.1【】

    ;JbetwostatesofaMarkovchainandPbethetransition ;probabilitymatrix(Definition2.3).Ifthereexistsanonnegativeintegerksuchthatthe(,J) ;elementinP,,isnotzero,thenwesaythatthestateJisaccessiblefromthestatei.

    ;Denoteitbyi_J.Ifi_3and_iIthenwesaythatiandJcancommunicateanddenote

    ;itbyiHJ.

    ;Inthefollowing.webegintostudythecommunicationrelation’’+”ofthestatevectorsin

    ;aRDSdefinedbyDefinition1.1.

    ;

    ;No.2ZHENGJieetal:MarkovChmnInducedby211

    ;Definition3.2Letkbeanon.negativeintegerandG=(E)beagraphwithvertex

    ;setnandedgesetE.DefineagraphGasfollows.ThevertexsetofGis ;v01,V02,…,V0n,11,V12,…,Vln,…,…,…,Vkl,Vk2,…,n)

    ;ThereisanedgebetweenviiandVpqinGifandonlyifIiPI=1and(J,q)?E.

    ;Example3.3

    ;Figure2.

    ;2

    ;IfGistheleftgraphinFigure2andk=3.thenG.istherightonein ;G

    ;V01

    ;G3

    ;Figure2theGraphGandtheGraphG3

    ;Definition3.4LetG=(E)beagraphwithvertexsetnandkbeanon-negative

    ;integer.SupposethereexistpathsPl,P2,…,inG(Definition3.2)satisfyingthe~llowing

    ;threeconditions:

    ;1.Each(1in)isoflength;

    ;2.Thetwoendpointsofeachpath(1

    ;1r,sn;

    ;in)arev0rand8,respectively,where

    ;3.TheverticesVkl,Vk2,…,knareallcontainedinthesepaths.

    ;ThenwecallPl,P2,…,endsaturatedinG

    ;Example3.5ForExample3.3,thepaths

    ;P=V02llV22V31

    ;

    ;212CHINESEQUARTERLYJOURNALOFMATHEMATICSVO1.23 ;areendsaturated.

null

    ;DenotethelabelsofVrl,ur2,…,vrnbyIr?F,where1r<.Wewanttoshow ;Pr([aan,G()=I1)>0,

    ;Pr([Ran,G](I1):jl2)>o,

    ;……

    ;?

    ;Pr([Ran,G(/k1)=J)>0

    F,respectively,where ;Suppose=(al,a2,…,an)?FandIr+l=(bl,b2,…,bn)?

    ;07’<,Io=IandIk=J.ByourlabelmethodoftheverticesinG,thelabelbl(1ln) ;ofthevertex+1)lisfromoneofitsneighborsin.Moreover,fromthesecondconditionin

    ;Definition3.6,iftwovertices(r+1)pandu(r+1)qgettheirstatesfromthesameneighborVrt

    ;in,thenbp=bq:at.ThenbyDefinition1.1,theevent[Ran,al(Ir)=Ir+lhappenswith

    ;positiveprobability.

    ;BytheChapmanKolmogorovequation[51wehavePr([Ran,G()=J)>0.Thatis,the ;statevectorJisaccessiblefromthestatevectorI. ;Nextweprove”“.IfthestatevectorJ=(J1,J2,…,Jn)?Fisaccessiblefromthestate ;vector=(il,i2,…,in)?,thenthereexistsanintegersuchthatinthematrixP,the

    ;IJelementP}Jisnotzero,wherePisthetransitionprobabilitymatrixoftheMarkovchain

    .ThenthereexistI1,I2,…,k—l?suchthat ;inducedbyRDS[Ran,G

    ;Pr([aan,G()=I1)>0,

    ;Pr([Ran,G](I1):jl2)>o,

    ;Pr([Ran,al(Ik1)=J)>0.

    ;Labeltheverticesv01,v02,…,v0n,Vkl,Vk2,…,uninGwithil,i2,…,in,jl,2,…,Jn,

    ;respectively.Foreach7’andl,labelthevertexVrlwiththe/-thelementof.Thenallvertices ;inGhave0-1labels.FromthednitionofaRDSfRan,G,thevertexVklgetsitslabel ;fromoneofitsneighborsv(k1)(rk

    ;1.1)inVk1andtheyhavethesame0-1labe1.Similarly, ;(七一1)(rk1,1)getsitslabelfromoneofitsneighborsv(k2)(rk

    ;2,1)inVk2andtheyhavethe

    ;same0-1labe1.Continuethisprocessandwecanfindapathfromavertexv0(ro,

    ;l】?VOtothe

    ;vertexuk】?Yk

    ;/’1=v0(r0,1)Vl(n,1)v2(r2.1)(七一2)(rk2,1)v(k1)(rk1,1)

    Vkl

    ;andtheverticesinPlhavethesamelabe1.

    ;Similarly,wecanfind/’2(fromavertexinV0toVk2),P3(fromavertexinV0toVk3),…,

    ;andPn(fromavertexinV0toun)inG.Itiseasytocheckthatthepaths/’1,/’2,…,are

    ;endsaturatedandsatisfythetwoconditionsinDefinition3.6.Then(,J)isadaptiveinG.

    ;Thenthefollowingresultisimmediate

    ;Corollary3.8TwostatevectorsI=(il,i2,…,in)?FandJ=(J1,J2,…,Jn)?F

    ;cancommunicateintheMarkovchaininducedbyaRDS[Ran,Gifandonlyifthereexistsan ;integersuchthatboth(,J)and()areadaptiveinG.

    ;

    ;214CHINESEQUARTERLYJOURNALOFMATHEMATICSVb1.23 ;References

;1

    BACLAWSKIK,ROTAC,BILLEYS.AnIntroductiontotheTheoryofProbability[M].MA:MITPress

    ;1989.

    ;2

    BARRETTCL,HUNTIIIHB,MARATHEMV,eta1.Onsomespecialclassesofsequentialdynamical

    408. ;systems[J].AnnCombin,2003,7:381

    ;3

    BARRETTCL,MORTVEITHS,REIDYSCM.ElementsofatheoryofcomputersimulationII:sequential

    ;dynamicalsystems[J].ApplMathComputation,2002,107:121136.

    ;4

    BARRETTCL,MORTVEITHS,REIDYSCM.ETSIV:Sequentialdynamicalsystems:fixedpoints.

    ;invertibilityandequivalence[J].ApplMathComputation,2003,134:153-171. ;5

    FELLERW.AnIntroductiontoProbabilityTheoryandItsApplications[M].NewYork:JohnWiley&

    ;Sons,1950.

    ;6

    MURRAYJD.MathematicalBiologyI:AnIntroduction[M].NewYork:Springer-Verlag.2002

    ;

    ;

Report this document

For any questions or suggestions please email
cust-service@docsford.com