矩阵的幂 回顾已经多次出现的矩阵的幂 。 对于可以对角化的矩阵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