EECS应用概率论[试读]
1.1 模型
应用：在网页搜索中，按网页相关度由高到低进行排序 主题：有限离散时间马尔可夫链，强大数定律 背景知识：附录A.1～A.2 搜索引擎采用不同的算法将网页按给定的关键字以相关度递减的方式排序．其中一种算法的思想是计算马尔可夫链的稳态分布．本章讨论这种分布的存在性与唯一性，以及在随机浏览时找到一个特定网页所需的平均时间．我们将采用强大数定律证明马尔可夫链处于每个特定状态的时间比例是收敛的． 1.1 模型 互联网由一系列相互链接的网页组成．这些网页和它们之间的链接关系构成了一张图．如图1-1所示，图中的节点是所有的网页X．若网页i有一个到网页j的链接，则图中有一条由i到j的弧（有向边）． ... 查看全部[ 1.1 模型 ]
1.2 马尔可夫链
想象一下你正在浏览网页：假设你在网页i上浏览了一个单位时间，然后随机点击进入了网页i指向的一个网页．在这个过程中，从网页i到网页j的概率正好为P(i, j)，与前面的例子相同． 1.2.1 定义 考虑一个包含节点X = {1, 2, …, N}和有向边的有限图．假设其中有些节点具有指向自己的边．图中每条边(i, j)，都有一个权重P(i, j) > 0．这些权值使得每个点外向边的权和为1．根据习惯，如果图中没有从i到j的边，则P(i, j)为0． 以上述方式得到的矩阵P = P[(i, j)]叫作随机矩阵．这种矩阵的每个元素均为非负，并且每行的和为1．现在，我们定义以下过程{X(n... 查看全部[ 1.2 马尔可夫链 ]
1.3 分析
经过上述分析与推导之后，我们会很自然地提出以下的问题． Q1：是否每个马尔可夫链都具有一个稳态分布？ Q2：该稳态分布是否唯一？ Q3：πn是否总是趋向于稳态分布？ 1.3.1 不可约性和非周期性 为了回答上面的三个问题，首先定义马尔可夫链的一些性质． 定义1.1 不可约的，非周期性的，周期性的 (a) 如果一个马尔可夫链可以从一个状态转移到任意其他状态（也许经过许多步的跳转），那么该马尔可夫链是不可约的． (b) 假设一个马尔可夫链是不可约的，并且定义 . （1.6） 所有i都有相同的值d(i) = d（如引理2.8所示）．如果d = 1，那么该马尔可夫链是非周期性... 查看全部[ 1.3 分析 ]
1.4 击中时间
在图1-1中，假设从网页A开始浏览．在每一步以相同的概率点击进入当前页的一个外部链接网页，那么需要多少步才能到达网页E？我们把这个时间叫作网页E的击中时间，也叫首通时间，记作TE．从图中可以看到，TE的最小值为2．当然，TE也有可能比2大得多． 图1-7 这可不是我们说的击中时间 1.4.1 平均击中时间 我们的目标是计算从X0 = A开始的TE的均值： . 完成这一计算的关键在于计算从所有可能的初始页面到E的平均击中时间．也就是说，我们要计算当i = A, B, C, D, E时的β(i)， . 这么做的原因在于，从A开始命中E的平均时间与从B和从D开始的平均击... 查看全部[ 1.4 击中时间 ]
1.5 小结
马尔可夫链：状态，转移概率，不可约的，非周期性的，稳态分布，击中时间 强大数定律 大数定律：不可约意味着有唯一的稳态分布，这个分布等于长期时间比例；如果既不可约又是非周期性的，则收敛于稳态分布 击中时间：首步方程 重要方程与公式 马尔可夫链的定义 式（1.3） 马尔可夫链X(n)的概率方程 式（1.5） 平衡方程 式（1.1） 首步方程 式（1.9） 1.6 参考资料 关于马尔可夫链有非常多优秀的书籍，我最喜欢的是Grimmett和Stirzaker的Probability and Random Processes，以及Bertsek... 查看全部[ 1.5 小结 ]
书名： EECS应用概率论
作者： [美] Jean Walrand
出版社： 人民邮电出版社
译者： 黄隆波
出版年： 2015-9-30
页数： 288
定价： 69.00元
装帧： 平装
丛书： 图灵数学·统计学丛书
ISBN： 9787115398963