程序设计导论：Python语言实践

1.6.4　混合马尔可夫链

这里要提醒读者的是，页面排名是Web模型的属性，而不是计算的特定方法。也就是说，randomsurfer.py程序只是计算页面排名的一种方法。幸运的是，基于成熟数学领域的简单计算模型提供了一个远比模拟计算页面排名问题更有效的方法。该方法基于二维矩阵的基本数学运算（具体可参见1.4节）。

1. 马尔可夫链自乘（Squaring a Markov chain）

通过两次跳转，随机冲浪者从页面i跳转到页面j的概率是多少？第一次跳转到一个中间页面k，所以针对所有可能的页面k，先计算从页面i到k的概率，然后计算从页面k到j的概率，最后累计计算结果值。在本书的Web模型示例中，通过两次跳转从页面1跳转到页面2的概率计算方法为：从页面1到0再到2概率（0.02×0.02），加上从页面1到1再到2的概率（0.02×0.38），加上从页面1到2再到2的概率（0.38×0.02），加上从页面1到3再到2的概率（0.38×0.02），加上从页面1到4再到2的概率（0.20×0.47），合计结果为0.1172。这个计算过程适用于其他的页面对。

在矩阵乘法定义时曾涉及这种计算：结果矩阵的第i行第j列的元素为原始矩阵第i行和第j列的点积。换言之，矩阵p[][]与自身乘积的结果为一个矩阵，结果矩阵的第i行第j列元素的值是随机冲浪者通过两次跳转从页面i到页面j的概率。马尔可夫链自乘的示意图如图1-6-6所示。

图1-6-6　马尔可夫链自乘的示意图

研究两次跳转转换矩阵的元素，将有助于我们更好地理解随机冲浪者的移动行为。例如，方阵的最大元素位于2行0列，表明冲浪者位于页面2时，有1个到页面3的链接，页面3只有1个到页面0的链接。所以，从页面2开始，冲浪者经过两次跳转，结果到页面0的可能性最大。其他两次跳转路径包含多个选择，因而可能性比较小。值得注意的是，这是精确计算（仅受限于Python的浮点精度）；与之对比，程序randomsurfer.py产生的结果为估值，所以需要多次迭代以获取更为准确的估值。 ...