应用：在网页搜索中，按网页相关度由高到低进行排序 主题：有限离散时间马尔可夫链，强大数定律 背景知识：附录A.1～A.2 搜索引擎采用不同的算法将网页按给定的关键字以相关度递减的方式排序．其中一种算法的思想是计算马尔可夫链的稳态分布．本章讨论这种分布的存在性与唯一性，以及在随机浏览时找到一个特... 查看全部[ 1.1 模型 ]
想象一下你正在浏览网页：假设你在网页i上浏览了一个单位时间，然后随机点击进入了网页i指向的一个网页．在这个过程中，从网页i到网页j的概率正好为P(i, j)，与前面的例子相同． 1.2.1 定义 考虑一个包含节点X = {1, 2, …, N}和有向边的有限图．假设其中有些节点具有指向自己的边．... 查看全部[ 1.2 马尔可夫链 ]
经过上述分析与推导之后，我们会很自然地提出以下的问题． Q1：是否每个马尔可夫链都具有一个稳态分布？ Q2：该稳态分布是否唯一？ Q3：πn是否总是趋向于稳态分布？ 1.3.1 不可约性和非周期性 为了回答上面的三个问题，首先定义马尔可夫链的一些性质． 定义1.1 不可约的，非周期性的，... 查看全部[ 1.3 分析 ]
在图1-1中，假设从网页A开始浏览．在每一步以相同的概率点击进入当前页的一个外部链接网页，那么需要多少步才能到达网页E？我们把这个时间叫作网页E的击中时间，也叫首通时间，记作TE．从图中可以看到，TE的最小值为2．当然，TE也有可能比2大得多． 图1-7 这可不是我们说的击中时间 1.4.1... 查看全部[ 1.4 击中时间 ]
马尔可夫链：状态，转移概率，不可约的，非周期性的，稳态分布，击中时间 强大数定律 大数定律：不可约意味着有唯一的稳态分布，这个分布等于长期时间比例；如果既不可约又是非周期性的，则收敛于稳态分布 击中时间：首步方程 重要方程与公式 马尔可夫链的定义 式（1.3） 马尔... 查看全部[ 1.5 小结 ]