▣顾：Random walk on graphs 给定图G=(V,E) 图上的随机游走： 。 从一个给定的顶点出发 ·接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 ·不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？（混合时间，mixing time) 4. 从点s出发，多久才会到达点t?(hitting time) 5. 多久才会遍历每个顶点至少一次？（遍历时间，cover time) 2
回顾：Random walk on graphs 给定图� = (�, �) 图上的随机游走: • 从一个给定的顶点出发 • 接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 • 不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？(混合时间，mixing time) 4. 从点s出发，多久才会到达点t? (hitting time) 5. 多久才会遍历每个顶点至少一次？(遍历时间，cover time) 2
回顾：幂迭代与无向图上的随机游走 令A为无向图的邻接矩阵，D为度数的对角矩阵.（注：因为是无向图，所以A是对称的） 记p(v)为时间t在点v的概率，则有 +1o=∑p.Waeg u:uv∈E 可以写出矩阵的形式：p+1=(AD-1)p:,进而有p=(AD-1)p:p为列向量 凄膏课義衲薄装鼎的答使的 :,一般Markov chain分析里面习惯使用行向量； 转移矩阵W:=AD1 要研究Wt,只需要研究A=DAD的幂迭代，因为： A=D2WD克与wt=D克An 对于实数对称矩阵A=VΣVr的幂迭代： Ak=V公kvr=∑ 背 1≤isn 对称矩阵A的特征值是怎么样分布的？上节课：邻接矩阵的特征值分布 4
回顾：幂迭代与无向图上的随机游走 令�为无向图的邻接矩阵, � 为度数的对角矩阵. （注：因为是无向图，所以�是对称的） 记 �!(�)为时间�在点�的概率，则有 �!"# � = ( $:$&∈( �! � ⋅ 1 deg � 可以写出矩阵的形式：�!"# = ��$# �! ，进而有�! = ��$# !�% ； �!为列向量 注意：之前第9次课里面使用的是行向量；一般Markov chain分析里面习惯使用行向量； 这节课我们将会进行谱分析，这里更适合使用列向量的记号 转移矩阵� ≔ ��)# 要研究�!, 只需要研究� = �)! "��)! "的幂迭代, 因为: � = � # & � �$# & ⇒ �! = �)# * �! � # * 对于实数对称矩阵� = �Σ�#的幂迭代： �+ = �Σ+�, = ( #-.-/ �. +�.�. , 对称矩阵�的特征值是怎么样分布的？上节课：邻接矩阵的特征值分布 4
无向图上随机游走的稳态分布 如果分布满足元=W元，则称元为稳态分布 稳态分布是一个“平衡态”/不动点 特别地：元=Wt元，t 注意：如果极限分布存在，则一定是一个稳态分布 给定无向图G,令d∈Rn为顶点度数的向量，m=IE引 定理.概率分布元=立是G上随机游走的一个稳态分布， 2m 换言之，向量元=品是A01的个右特征向量，且特征值为1 5
无向图上随机游走的稳态分布 如果分布�满足 � = �� ，则称� 为稳态分布 稳态分布是一个“平衡态”/ 不动点 特别地： � = �! �, ∀� 注意：如果极限分布存在，则一定是一个稳态分布 给定无向图 �，令 � ⃗ ∈ ℝ! 为顶点度数的向量， � = � 定理. 概率分布� = #⃗ $% 是�上随机游走的一个稳态分布. 换言之， 向量� = #⃗ $%是��&'的一个右特征向量，且特征值为1 5
Fundamental Theorem of Markov Chains 无向图上的马尔可夫链基本定理 0于 是否对于任意无向图，不管从什么样的o开始，总有p:→ 元=a随着t→o? 2m 一不一定：非连通的，或者二分图 对于无向图，连通性即强连通，非可约；非二分图，则意 味着非周期的 因此无向图上的马尔可夫链基本定理说的是： 对于任意有限的，连通的，非二分图，不管从什么样的o开始，总有 p→元= 随着t→∞ 2m 5
6
Lazy Random Walks 对于二分图，可以考虑惰性随机游走： ·每一步会以1/2的概率停留在当前状态； 以1/2的概率，随机地从邻居里面均匀地选取一个， 作为下一步的状态。 用矩阵表示的话则有p:=(侵1+AD-1)po. 定理对于任意有限的，连通的，不管从什么样的P0 开始，=1+AD）6→票 6
7
转移矩阵的谱分析 记W=AD-1为随机游走的转移矩阵，Z=1+2AD-1为惰性随机游走的转移炬 要研究P:=Wpo,可以先分析w的特征空间 注意：尽管A是对称的，W不一定是对称的 不过W与一个对称矩阵是相似的：DWDi=D(AD-1)D2=DAD左=A 1 1 定理.W与A拥有相同的特征值 注意：w不一定有两两正交的特征向量 7
8
d-regular graphs(d-正则图) 对于d-正则图，有W=A=1-L,记w的特征值为a1≥a2≥…之an，正交正归化的特征向量为，v2,,n 要研究p:=Wpo,可以把po=c1y1+…+cnn展开 那么W'po=c1aD1+c2a吃v2+…+Cna克n W=A=1-L的特征空间： ·12a1,am≥-1 1=a1,对应的特征向量为1 a1>2当且仅当图是连通的 a41=-an当且仅当图是二分图（课后练习） 可见连通性，和非二分图的性质，分别对应于a2一1 这意味着，对连通的非二分图，Wpo→c11ast→∞ 如果a2-1+e,则e越大，收敛越快 Fundamental Theorem of Markov chain, for undirected graph! C1V1是什么？ 对于d-正则图，元=豆=为特征值为1对应的特征向量，因此，=1a=。.)=六po)=言 2m n 因此c==元 8
9 Fundamental Theorem of Markov chain, for undirected graph!
Lazy Random Walks 要证明，=（侵1+AD),→品 随着t→oo: 2m 对d-正则图，W=A,z=1+aA 2 2d 若w的特征值为a1≥2≥…≥n 则Z的特征值为1-1≥ 1+2≥…2 2 1+n≥0 2 2 (课后练习) 定理对有限的连通无向图随着t→0，，=(1+A0Po→品，不管从任何p,出发 9
10 定理. 对有限的连通无向图 , 随着 � → ∞ ， � ! = #* � + #* � � ) # ! � 0 → 2⃗ *3 ，不管从任何 � 0出发
混合时间(mixing time) 既然P→元=日收敛，收敛速度？ 2m 回顾：给定概率分布与，它们的TV距离定义为 注意0sdv(,)s1 定义.e-混合时间为最小的整数t使得： lpt-πl1≤epo 定义，谱间隔(spectral gap:入=min{1-a2,1-lan} 10
12
Mixing time (for d-regular graphs) 定理随机游走的c-混合时间最多为log(②)，其中=minf1-a2,1-lan 证明：取v1,V2,,Vn为A的一组正交正规特征向量的基。 设po=c1v1+c2v2++cnn,则pt=Wtp0=C1iv1,+c2吃v2+…+cna克n 由Cauchy--Schwarz不等式，Ilm,-πl1≤Vp:-πl2元 Ilp:-πl陉=lc2a吃v2+…+Cnatvn3=c吃a经|lv2ll3+…+c2a2 llnll =c吃aα好+…+ca≤(1-02t(c经+…+c) 注意到po本身作为一个概率分布，满足Ilpo陉=∑ipo()2≤ipo()=lpol1=1 因此lp:-π陉≤(1-)2t→lp:-πl1≤Vn1-)'≤vme ,注：非d-regular的情况下v1,v2,,yn需要取作A的正交正规特征向量基，会有额外Vn的损失 当ispectral gap为常数时i.e.入=(1)ル，随机游走在0(1og)步内收敛， 对正则图且λ=2(1)时，我们可以在01ogn)步内，均匀随机采样到一个顶点. 13
Mixing time (for d-regular graphs) 13 定理. 随机游走的�-混合时间最多为# 4 log / 5 , 其中� = min 1 − �*, 1 − |�/| . 证明：取�!, �", … , �#为�的一组正交正规特征向量的基。 设�$ = �!�! + �"�" + … + �#�#，则�% = �%�$ = �!�! %�! + �"�" %�" + ⋯ + �#�# % �# 由Cauchy-Schwarz不等式， �! − � # ≤ � �% − � & �! − � " " = �"�" ! �" + ⋯ + �#�# ! �# " " = �" "�" "% �" " " + ⋯ + �# "�# "! �# " " = �" "�" "! + ⋯ + �$ %�$ %& ≤ 1 − � %& �% % + ⋯ + �$ % 注意到 �$本身作为一个概率分布，满足 �$ * * = ∑. �0 � * ≤ ∑. �0 � = �0 # = 1 因此 �% − � & & ≤ 1 − � "% ⇒ �% − � # ≤ � 1 − � ! ≤ � �%&! • 注：非d-regular的情况下�#, �*, … , �/需要取作�的正交正规特征向量基，会有额外 �的损失 • 当spectral gap为常数时(i.e. � = Ω(1))， 随机游走在� log / 5 步内收敛. • 对正则图且� = Ω(1)时，我们可以在�(log �)步内，均匀随机采样到一个顶点. �