Random Walks on Graphs

《Random Walks on Graphs》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、RandomWalksonGraphsJosepFabregaJourneesCombinatoireetAlgorithmesduLittoralMediterraneenUPC,Barcelona,7{8June2011OutlineSimplerandomwalksongraphsRandomwalksandMarkovchainsMixingrate.Hitting,commuteandcovertimesRandomwalksandharmonicfunctionsConnectionwithele

2、ctricalnetworksRandomwalksonweightedgraphsRecurrenceininnitegraphsRandomwalksinalgorithmdesignReferencesIDoyle,P.G.andSnell,J.L.,Randomwalksandelectricnetworks,CarusMathematicalMonographsvol.22(1984).IGrimmett,G.,Probabilityongraphs,CambridgeUniv.Press(2010).

3、ILovasz,L.,Randomwalksongraphs:asurvey,Combinatorics,PaulErd}osiseighty,Vol.2,Keszthely(1993).SimplerandomwalksLetG=(V;E)beaconnectedgraph,jVj=nandjEj=m.IGivenaninitialvertexv0,selectatrandom"anadjacentvertexv1,andmovetothisneighbour.IThenselectatrandom"ane

4、ighborv2ofv1,andmovetoit;etc.Simplerandomwalksv0=3Simplerandomwalks3!4Simplerandomwalks3!4!1Simplerandomwalks3!4!1!3Simplerandomwalks3!4!1!3!2!


SimplerandomwalksThesequenceofverticesv0;v1;v2;:::;vk;:::selectedinthiswayisasimplerandomwalkonG.Ateachstepk,wehav

5、earandomvariableXktakingvaluesonV.Hence,therandomsequenceX0;X1;X2;:::;Xk;:::isadiscretetimestochasticprocessdenedonthestatespaceV.SimplerandomwalksWhatdoesatrandom"mean?Ifattimekweareatvertexi,chooseuniformlyanadjacentvertexj2(i)tomoveto.Letd(i)denotethedeg

6、reeofvertexi.81<;ifij2Epij=P(Xk+1=jjXk=i)=d(i):0;otherwiseThesetransitionprobabilitiesdonotdependontime"k.Simplerandomwalksj111d(j1)d(i)i11d(i)d(i)j21j31d(j2)d(j3)Figure:TransitionprobabilitiesRandomwalksandMarkovchainsTheMarkovpropertyholds:conditionalonthep

7、resent,thefutureisindependentofthepast.P(Xk+1=jjXk=i;Xk1=ik1;:::;X0=i0)=P(Xk+1=jjXk=i)=pijTherandomsequenceofverticesvisitedbythewalk,X0;X1;:::;Xn;:::isaMarkovchainwithstatespaceVandmatrixoftransitionprobabilitiesP=(pij)i;j2VRandomwalksandMarkovchains0111110

8、B4444CBB11CCB000CB22CBB1111CCP=B0CB4444CB111CB00CB@333CA11100333RandomwalksandMarkovchainsPisastochasticmatrix,Xpij=1j2VLetDbethediagonalmatrixwith(D)ii=1=d(i)andAbetheadjacencymat