▣顾：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