马尔可夫链与 PageRank：为网络排序的特征向量

当矩阵是一张概率表

一个随机（马尔可夫）矩阵 P 的元素非负、每一列之和为 1：元素 P[i,j] 是一步内从状态 j 转移到状态 i 的概率。若 p 是当前在各状态上的分布，则 P p 是一步之后的分布，P^t p 是 t 步之后的分布。这不过是矩阵乘法在为随机游走记账。

# Weather chain: states = {Sunny, Rainy}, columns sum to 1
#            from Sunny   from Rainy
P = [ [ 0.9 ,        0.5 ],   # to Sunny
      [ 0.1 ,        0.5 ] ]  # to Rainy
# start certain it is Sunny:  p0 = (1, 0)
# p1 = P p0 = (0.9, 0.1)
# p2 = P p1 = (0.86, 0.14)
# p_inf       = (0.833..., 0.166...)   <- it settles down

稳态就是一个特征向量

一个再走一步也不变的分布 pi 满足 P pi = pi——它是 P 的、对应特征值 1 的特征向量。这个特殊的特征向量就是稳态分布。每个随机矩阵都有特征值 1（全 1 行向量是它的左特征向量），所以稳态总是存在；问题在于它是否唯一、以及你是否真的会收敛到它。

Perron–Frobenius 定理给出了答案：若 P 的元素严格为正（或更一般地是不可约且非周期的），则特征值 1 是单根且其模严格大于其余所有特征值，稳态分布唯一且严格为正，并且 P^t p 从任意起点都收敛到它。

PageRank：网络图上的随机冲浪者

把网络建模为一张图：处于某页的冲浪者均匀随机地选一个出链。这就由邻接矩阵定义出一个随机矩阵。它的稳态分布按冲浪者落在各页面上的频率为页面排序——这就是 PageRank。两个修补让 Perron–Frobenius 干净地适用。

1. 悬挂节点修补：没有出链的页面以均匀随机的方式跳转到任意一页。
2. 阻尼：以概率 1 - d（通常 d = 0.85）冲浪者随机跳到任意页面，从而保证矩阵元素严格为正。
3. 结果是一个正的随机矩阵 G = d P + (1 - d)(1/n) 11^T，它有唯一的稳态分布。

如何计算：幂法

面对数十亿页面，你绝不会显式构造 G 或对它做对角化。你只需迭代：从均匀分布出发，反复施加这个映射，直到它不再变化。由于特征值 1 严格占优，这个幂法会收敛到主特征向量——也就是稳态分布——其速度由阻尼因子决定。

# PageRank via the power method (no dense matrix needed)
r = ones(n) / n            # uniform start
repeat:
    r_new = d * (P @ r) + (1 - d) / n   # apply G implicitly
    if ||r_new - r||_1 < tol: break
    r = r_new
return r                   # r is the stationary distribution