回顾与补充 上节课：随机游走(Random walk),Page Rank 。 记X为时间t随机游走所处的状态，则转移矩阵P,/=Pr[Xt+1= jxt=订 记p(i)为时间t在状态的概率，则有pt+i=p:·P 不可约：强连通 ·周期：gcd{t|(P)i>0},周期为1称为非周期性的 对于有限，不可约，非周期的马尔可夫链，有以下事实： 1.存在一个稳态分布元. 2. 随着t→o,p都会收敛到屁，无论从什么样的0开始. 3. 稳态分布是唯一的 4. π()=
回顾与补充 上节课: 随机游走 (Random walk), Page Rank • 记�!为时间�随机游走所处的状态, 则转移矩阵 �!,# = Pr[�$%& = �|�$ = �] • 记�$(�)为时间�在状态�的概率, 则有�$%& = �$ ⋅ � • 不可约: 强连通 • 周期：gcd � �$ !,! > 0}，周期为1称为非周期性的 对于有限，不可约，非周期的马尔可夫链，有以下事实： 1. 存在一个稳态分布�. 2. 随着 � → ∞， �! 都会收敛到�，无论从什么样的�"开始. 3. 稳态分布是唯一的 4. � � = # $! 2
谱图理论(Spectral graph theory) PageRank 谱分析：特征值+特征向量 计算机科学： +相关的线性代数 。 Pagerank ·稀疏化Sparsification 图论与组合结构： 迭代法解线性方程 ·连通性(Cheeger-不等式) 电阻网络 ·图染色 Expander codes(LDPC, 聚类(Clustering) Tanner codes) Mixing of random walks 不可近似性(Dinur''s proof of Expander graphs (efficient the PCP theorem) network,superconcentrators) 去随机化(Derandomization) 3
谱图理论 (Spectral graph theory) 3 谱分析：特征值 + 特征向量 + 相关的线性代数 图论与组合结构: • 连通性 (Cheeger不等式) • 图染色 • 聚类(Clustering) • Mixing of random walks • Expander graphs (efficient network, superconcentrators) 计算机科学: • Pagerank • 稀疏化Sparsification • 迭代法解线性方程 • 电阻网络 • Expander codes (LDPC, Tanner codes) • 不可近似性(Dinur’s proof of the PCP theorem) • 去随机化 (Derandomization)
矩阵的幂 回顾已经多次出现的矩阵的幂 。 对于可以对角化的矩阵A,收敛只需要特征值的幂是收敛的（特别地，谱半径p(A)=1 也有可能是收敛的) x=a1V1+a2v2+…+an)n Akx=afa1vi+afa2v2 +..+afanvn ·但一般来说，可能需要使用：谱半径p(A)<1当且仅当imAk=0 课后练习：考61引的特征值？日广=？ - 注意：随机游走的转移矩阵一定不会是日》对应的只会是2Y] 随机游走：P+1=p·P,转移矩阵P=D-1A,及其相似的对角阵W=DAD克 -这节课：马尔可夫链基本定理在无向图上成立：对于连通的，非二分图，存在唯一 的稳态分布，且会收敛 -3 完整证明可参照Olle Haggstrom的Finite Markov chains and algorithmic applications 5
矩阵的幂 回顾已经多次出现的矩阵的幂 • 对于可以对角化的矩阵�，收敛只需要特征值的幂是收敛的（特别地，谱半径� � = 1 也有可能是收敛的） � = ���� + ���� + ⋯ + ���� ��� = �� ����� + �� ����� + ⋯ + �� ����� • 但一般来说，可能需要使用：谱半径� � < 1当且仅当 lim %→' �% = 0 – 课后练习：考虑 � � � � 的特征值？ � � � � � =? – 注意：随机游走的转移矩阵一定不会是 � � � � ，对应的只会是 �/� �/� � � • 随机游走：�()* = �( ⋅ �，转移矩阵� ≔ �+*�，及其相似的对角阵� = �+" #��+" # – 这节课：马尔可夫链基本定理在无向图上成立：对于连通的，非二分图，存在唯一 的稳态分布，且会收敛 – 完整证明可参照Olle Häggström的Finite Markov chains and algorithmic applications 5
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量） 能否与图本身的组合性质（连通性，是否二分图）相对应？ 图的邻接矩阵的例子：完全图A=J-1=11r-1 J的特征值和特征向量是什么？ Ji=ni 6
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量） 能否与图本身的组合性质（连通性，是否二分图）相对应？ 图的邻接矩阵的例子：完全图 � = � − � = 1 1( − � � 的特征值和特征向量是什么？ � 1 = � 1 6
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量)能否与图本身的组合性质相对应？ 图的邻接矩阵的例子：二分图 。 引理：对于二分图G,如果a是A(G)的一个特征值，且重数为k,那么-也是A(G)的 一个特征值，重数也是k 。 特征值的重数(multiplicity) -代数重数(algebraic multiplicity):特征多项式里面，根的重复次数 -几何重数(geometric multiplicity小：特征值对应的特征空间的维度 一对于可对角化的矩阵（特别地，对于无向图的邻接矩阵，它们是一样的） 7
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量）能否与图本身的组合性质相对应？ 图的邻接矩阵的例子：二分图 • 引理：对于二分图�，如果 � 是� � 的一个特征值，且重数为�，那么−�也是� � 的 一个特征值，重数也是� • 特征值的重数(multiplicity) – 代数重数(algebraic multiplicity)：特征多项式里面，根的重复次数 – 几何重数(geometric multiplicity)：特征值对应的特征空间的维度 – 对于可对角化的矩阵（特别地，对于无向图的邻接矩阵，它们是一样的） 7