1707611791
为了打破这个循环，佩奇和布林采用了一个很巧妙的思路，即分析一个虚拟用户在互联网上的漫游过程。他们假定：虚拟用户一旦访问了一个网页后，下一步将有相同的几率访问被该网页所链接的任何一个其他网页。换句话说，如果网页Wi有Ni个对外链接，则虚拟用户在访问了Wi之后，下一步点击那些链接当中的任何一个的几率均为1/Ni。初看起来，这一假设并不合理，因为任何用户都有偏好，怎么可能以相同的几率访问一个网页的所有链接呢？但如果我们考虑到佩奇和布林的虚拟用户实际上是对互联网上全体用户的一种平均意义上的代表，这条假设就不像初看起来那么不合理了。那么网页的排序由什么来决定呢？是由该用户在漫游了很长时间——理论上为无穷长时间——后访问各网页的几率分布来决定，访问几率越大的网页排序就越靠前。
1707611792
1707611793
为了将这一分析数学化，我们用pi（n）表示虚拟用户在进行第n次浏览时访问网页Wi的几率。显然，上述假设可以表述为（请读者自行证明）：
1707611794
1707611795
1707611796
1707611797
1707611798
这里pj→i是一个描述互联网链接结构的指标函数（indicator function），其定义是：如果网页Wj有链接指向网页Wi，则pj→i取值为1，反之则为0。显然，这条假设所体现的正是前面提到的佩奇和布林的排序原则，因为右端求和式的存在表明与Wi有链接的所有网页Wj都对Wi的排名有贡献，而求和式中的每一项都正比于pj，则表明来自那些网页的贡献与它们的自身排序有关，自身排序越靠前（即pj越大），贡献就越大。
1707611799
1707611800
为符号简洁起见，我们将虚拟用户第n次浏览时访问各网页的几率合并为一个列向量pn，它的第i个分量为pi（n），并引进一个只与互联网结构有关的矩阵H，它的第i行j列的矩阵元为Hij=pj→i/Nj，则上述公式可以改写为
1707611801
1707611802
pn+1 = Hpn
1707611803
1707611804
这就是计算网页排序的公式。
1707611805
1707611806
熟悉随机过程理论的读者想必看出来了，上述公式描述的是一种马尔可夫过程（Markov process），而且是其中最简单的一类，即所谓的平稳马尔可夫过程（stationary Markov process）[2]，而H则是描述马尔可夫过程中的转移概率分布的所谓转移矩阵（transition matrix）。不过普通马尔可夫过程中的转移矩阵通常是随机矩阵（stochastic matrix），即每一列的矩阵元之和都为1的矩阵（请读者想一想，这一特点的“物理意义”是什么？）[3]。而我们的矩阵H却可能有一些列是零向量，从而矩阵元之和为0，它们对应于那些没有对外链接的网页，即所谓的“悬挂网页”（dangling page）[4]。
1707611807
1707611808
上述公式的求解是简单得不能再简单的事情，即
1707611809
1707611810
pn = Hnp0
1707611811
1707611812
其中p0为虚拟读者初次浏览时访问各网页的几率分布（在佩奇和布林的原始论文中，这一几率分布被假定为是均匀分布）。
1707611813
1707611814
1707611815
1707611816
1707611817
因为星星在那里：科学殿堂的砖与瓦 [:1707611258]
1707611818
因为星星在那里：科学殿堂的砖与瓦 三、问题及解决
1707611819
1707611820
1707611821
如前所述，佩奇和布林是用虚拟用户在经过很长——理论上为无穷长——时间的漫游后访问各网页的几率分布，即，来确定网页排序的。这个定义要想管用，显然要解决三个问题：
1707611822
1707611823
1707611824
（1）极限是否存在？
1707611825
1707611826
（2）如果极限存在，它是否与p0的选取无关？
1707611827
1707611828
（3）如果极限存在，并且与p0的选取无关，它作为网页排序的依据是否真的合理？
1707611829
1707611830
如果这三个问题的答案都是肯定的，那么网页排序问题就算解决了。反之，哪怕只有一个问题的答案是否定的，网页排序问题也就不能算是得到了满意解决。那么实际答案如何呢？很遗憾，是后一种，而且是其中最糟糕的情形，即三个问题的答案全都是否定的。这可以由一些简单的例子看出。比方说，在只包含两个相互链接网页的迷你型互联网上，如果p0=（1，0）T，极限就不存在（因为几率分布将在（1，0）T和（0，1）T之间无穷振荡）。而存在几个互不连通（即互不链接）区域的互联网则会使极限——即便存在——与p0的选取有关（因为把p0选在不同区域内显然会导致不同极限）。至于极限存在，并且与p0的选取无关时它作为网页排序的依据是否真的合理的问题，虽然不是数学问题，答案却也是否定的，因为任何一个“悬挂网页”都能像黑洞一样，把其他网页的几率“吸收”到自己身上（因为虚拟用户一旦进入那样的网页，就会由于没有对外链接而永远停留在那里），这显然是不合理的。这种不合理效应是如此显著，以至于在一个连通性良好的互联网上，哪怕只有一个“悬挂网页”，也足以使整个互联网的网页排序失效，可谓是“一粒老鼠屎坏了一锅粥”。
1707611831
1707611832
为了解决这些问题，佩奇和布林对虚拟用户的行为进行了修正。首先，他们意识到无论真实用户还是虚拟用户，当他们访问到“悬挂网页”时，都不应该也不会“在一棵树上吊死”，而是会自行访问其他网页。对于真实用户来说，自行访问的网页显然与个人的兴趣有关，但对于在平均意义上代表真实用户的虚拟用户来说，佩奇和布林假定它将会在整个互联网上随机选取一个网页进行访问。用数学语言来说，这相当于是把H的列向量中所有的零向量都换成e/N（其中e是所有分量都为1的列向量，N为互联网上的网页总数）。如果我们引进一个描述“悬挂网页”的指标向量（indicator vector）a，它的第i个分量的取值视Wi是否为“悬挂网页”而定——如果是“悬挂网页”，取值为1，否则为0——并用S表示修正后的矩阵，则
1707611833
1707611834
1707611835
1707611836
1707611837
显然，这样定义的S矩阵的每一列的矩阵元之和都是1，从而是一个不折不扣的随机矩阵。这一修正因此而被称为随机性修正（stochasticity adjustment）。这一修正相当于剔除了“悬挂网页”，从而可以给上述第三个问题带来肯定回答（当然，这一回答没有绝对标准，可以不断改进）。不过，这一修正解决不了前两个问题。为了解决那两个问题，佩奇和布林引进了第二个修正。他们假定，虚拟用户虽然是虚拟的，但多少也有一些“性格”，不会完全受当前网页所限，死板地只访问其所提供的链接。具体地说，他们假定虚拟用户在每一步都有一个小于1的几率α访问当前网页所提供的链接，同时却也有一个几率1-α不受那些链接所限，随机访问互联网上的任何一个网站。用数学语言来说（请读者自行证明），这相当于是把上述S矩阵变成了一个新的矩阵G：
1707611838
1707611839
1707611840