PageRank 作为随机浏览者的平稳分布

不可约性。由于 $1-d>0$,$G$ 的每个元素都严格为正($G_{ij}\ge(1-d)/N>0$),因此从任意网页出发都能以正概率一步直接跳到任意其他网页——底层图显然是强连通的,故 $G$ 不可约。

非周期性。一个每个状态都能直接到达每个状态(包括自身,因为 $G_{ii}>0$ 也成立)的链,其可能的返回时长涵盖了所有 $1,2,3,\dots$,它们的最大公约数为1;故 $G$ 非周期。

存在性、唯一性与收敛性。$G$ 按构造是行随机矩阵(两个行随机矩阵 $P$ 与 $J/N$ 的凸组合 $dP+(1-d)\tfrac1N J$ 仍是行随机矩阵),且如上所示它不可约且非周期,故有限马尔可夫链基本定理可直接应用:存在唯一的平稳分布 $\pi$ 满足 $\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big)$,且 $G^n$ 逐项收敛到每一行都等于 $\pi$ 的矩阵。

幂迭代。由于对任意初始分布 $\pi_0$ 都有 $\pi_k=\pi_0G^k$,且 $G^k$ 的每一行当 $k\to\infty$ 时都收敛到 $\pi$,故加权平均 $\pi_0G^k$ 也收敛到 $\pi$——这正是为何从任意初始排名(通常取均匀分布)出发反复应用 $\pi_{k+1}=\pi_k G$ 必定收敛到真实 PageRank 向量的原因。