回顾与补充 上节课：随机游走(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