应用：在网页搜索中，按网页相关度由高到低进行排序 主题：有限离散时间马尔可夫链，强大数定律 背景知识：附录A.1～A.2 搜索引擎采用不同的算法将网页按给定的关键字以相关度递减的方式排序．其中一种算法的思想是计算马尔可夫链的稳态分布．本章讨论这种分布的存在性与唯一性，以及在随机浏览时找到一个特定网页所需的平均时间．我们将采用强大数定律证明马尔可夫链处于每个特定状态的时间比例是收敛的． 1.1 模型 互联网由一系列相互链接的网页组成．这些网页和它们之间的链接关系构成了一张图．如图1-1所示，图中的节点是所有的网页X．若网页i有一个到网页j的链接，则图中有一条由i到j的弧（有向边）． 图1-1 在网络中，网页总是指向其他的网页．在本图中P(A, B) = 1/2，P(D, E) = 1/3 直观上看，一个高级别网页所指向的网页也应具有较高的级别（在实际中，除了我们在此讨论的网页级别度量方式，搜索引擎的排序结果还取决于网页中关键字是否出现以及其他许多因素）．因此，我们定义网页i的级别π(i)为一个正数，并且满足 P(j, i)表示所有网页j的外向链接中指向i的链接所占的比例．如果j没有指向i的链接，则P(j, i) = 0．在上述例子中，我们有P(A, B) = 1/2，P(D, E) = 1/3，P(B, A) = 0等．这一算法的思想源自拉里•佩奇（Larry Page，见图1-2），这也是PageRank（佩奇排序）这一名字的由来． 图1-2 谷歌公司创始人之一拉里•佩奇 可以将这些等式以矩阵的形式记作 . （1.1） 这里，π是一个以π(i)为分量的行向量，而P是一个以P(i, j)为元素的方阵． 式（1.1）称为平衡方程．这里我们注意到，如果一个向量π是这个方程的解，那么π的任意倍数也是这个方程的解．为方便起见，我们将解归一化，使得所有网页的级别之和为1： . （1.2） 图1-3 这是平衡方程吗 对于图1-1中的例子，平衡方程为 再加上π(i)的和为1这一条件，可以得到 . 由此可以看到，网页A具有最高的级别，网页E具有最低的级别．运用这一方法的搜索引擎会将这些网页级别与其他因素相结合来进行网页排序．一些搜索引擎也会采用这一度量的变种来对网页进行排序．