数学模型5-1马氏模型.pdf

第五章 马氏第五章 马氏 Markov Model 与隐马氏模型与隐马氏模型 HMM 5 1 马氏模型 5 2 隐马氏模型 4 1 马氏模型马氏模型 马氏模型 马氏链理论简介 马氏模型应用 食堂就餐人数问题 I 某大学有三个食堂A B C 调查显示 在食堂 A就餐的人中paa部分仍然回到食堂A 有pab部分 选择食堂B pac部分选择食堂C 在食堂B就餐的 人中pbb部分仍然回到食堂B 有pba部分选择食堂 A pbc部分选择食堂C 在食堂C就餐的人中pcc部 分仍然回到食堂C 有pca部分选择食堂A pcb部 分选择食堂B 请估计在食堂A B C的就餐人数 食堂就餐人数问题 II A B C Pac Pca Pcc Paa Pab Pbc PbaPcb 食堂就餐人数问题 III 令An为第n天在食堂A就餐的人数比例 令Bn为第n天在食堂B就餐的人数比例 令Cn为第n天在食堂C就餐的人数比例 不动点问题 I 问题 极限是否存在 若存在 不动点问题 II 若初值为 0 A0 B0 C0 并令P为上式中的 矩阵 则 若 1 3 1 3 1 3 P由下面的矩阵给出 我们可以具体计算 An Bn Cn 不动点问题 III nAnBnCnnAnBnCn 0 19470 2500 0 2500 0 2500 0 2500 0 2500 0 2500 0 2500 0 2500 0 2500 0 2500 0 1946 0 1945 0 1945 0 1945 0 1945 0 1945 0 1945 0 1945 0 1945 0 5553 0 5554 0 5555 0 5555 0 5555 0 5555 0 5555 0 5555 0 5555 0 5555 11 12 13 14 15 16 17 18 19 20 10 45000 28330 2667 20 50080 24580 2533 30 52610 22320 2507 40 53950 21040 2501 50 54680 20320 2500 60 55070 19930 2500 70 55290 19710 2500 80 55410 19590 2500 90 55480 19520 2500 100 55510 19490 2500 不动点问题 IV 问题的特征 每一步活动只与当前处在什么 状态 有关 与过去的 状态 没有关系 矩阵P特殊性 每行和为1 表示下一个时 刻的状态必须在A B C中之一 马尔可夫链模型 简称马氏链 离散时间随机过程 对于离散的时间 t 0 1 2 3 的每一个 t 对应一个随机变量 t 我们把 0 1 n 这样一个随机变量的序列叫做离 散时间的随机过程 随机过程 所有 t t 0 1 2 3 具有公共的取 值集合 我们把此集合叫做状态空间 记 为 状态空间 记 为 S 离散时间随机过程 对于一个固定的 0 1 n 就是一个状态的序列 称为该随 机过程的一条轨道 我们把 t 的取值 叫做该条轨道在时间 t 的状态 的联合分布称为 的一个有限维分布 我们用 的全部有 限维分布刻画它的统计特性 马氏 Markov 链 随机过程 n n 0 称为有限状态马氏链 若 n 只有有限个取值且满足 记之为pi j n n k 矩阵P n n k pi j n n k 称为从n出发的k 步转移概率矩阵 时齐马氏链 如果马氏链的转移矩阵与出发时刻无关 即 pi j n n k pi j 0 k 则称此马氏链 是时齐的 时齐的 这时将 Pi j n n k 简单地记为 Pi j k 通常不特别说明 马氏链就指时齐马氏 链 前面的食堂问题就是一个1步时齐马氏 链 高阶马氏过程 若一个随机过程满足 也就是说随机过程下一时间的发展只和包括当 前时间在内的最近的k个时间的状态有关 而和 这k个时间之前的历史没有关系 其中k 0 1 2 我们把这样的随机过程叫做k 阶马氏 链 阶马氏 链 零 1 阶马氏过程 显然 零阶马氏链就是说下一时间的发展和 当前状态及已有历史都独立 也就是相互 独立的随机序列 过程 1 阶马氏链就是前面的马氏链 关于名称的一点说明 参考书中 看到马氏链 过程 的时候要根据上下 文进行判断 有的时候是指普遍的马氏链 包括 高阶 一阶 零阶 有时候特指一阶马氏链 在大多数情况下 如不特别说明 通常是特指 一阶时齐的马氏链一阶时齐的马氏链 如果将一个 k 阶马氏链的相邻 k 个时间的状态 合为一个新的状态 yn xn xn 1 xn k 1 则 yn 是一个 1 阶马氏链 转移概率矩阵性质 其中第三个方程称之为C K方程 时齐马氏链性质 I 时齐马氏链由转移概率矩阵和初分布完全 确定 设转移概率矩阵为P pij 初始分 布 则 时齐马氏链性质 II 若记 i n P n i n i n i S 即所谓 绝对概率 则 马氏链的不变分布 状态空间S上的一个概率分布 1 2 N 称为转移概率矩阵P的不变概率分布 简称不变分布 如果 P 一般来说 不变分布未必存在 若不变分 布存在且唯一 记为 则它是以下代数方 程组的唯一非负解 几个概念 I 可达和互通 状态i称为可达状态j 如果存在i i0 i1 in j 使得 常返性 马氏链 n n 0 状态y称为常返 的 如果概率为一地发生如下事件 从y出发的状 态 有限时间内离开状态y 此后又必到达y 如此无限重复 马氏链的遍历极限 I 若马氏链 n n 0 的状态空间S为有 限集 不妨设S 1 2 N 且 转移矩 阵为P 是一个互通常返马氏链 则它存在 唯一的不变概率分布 1 2 N 并 使得 马氏链的遍历极限 II 若马氏链 n n 0 的状态空间S为有限集 不妨设S 1 2 N 且转移矩阵矩阵的 每个元素为正 则它存在唯一不变概率分 布 1 2 N 满足如下 指数 遍历性 马氏链的遍历极限 III 令Ti 是 1 n 首次出现状态 i 的 时间 那么 i E Ti 0 i 就是一个平 均返回 状态i 时间 有结论如下 对于互通常返马氏链 设不变分布为 1 2 N 则 句子的平均长度 设DNA序列 四个字母 A C G T 构成 每个 字母的出现是独立同分布的 记为i i d 每 个字母出现的概率分别是PA PC PG PT 现 在有一个特殊的机器 生物上称之为限制性 内切酶 遇到AA就将序列切断 问题 这些片断的平均长度是多少 句子的平均长度 例如序列为 限制性内切酶将序列切成如下片断 TGCAATCGGATAACCAAACA TGCAATCGGATAACCAAACA 句子的平均长度 马氏链 状态集合 A B AA Xn 原始链上第n个位置结尾处的状态 例子 TATCAAT 句子的平均长度 马氏链 转移概率矩阵为 其中 句子的平均长度 马氏链 不变分布 1 2 3 那么句子的平均长度即为1 3 句子的平均长度 马氏链 平均长度为 句子的平均长度 马氏链 思考 如果限制性内切酶的识别位点为 AC 切下片断的平均长度是多少 提示 考虑状态集合为 Page Rank Basic idea of Page Rank Calculation of Page Rank Page Rank and Markov chain Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Basic Idea of Page Rank Suppose that Page d1contains hyperlinks to 10 pages Page d2just has a single link to page d3 The contribution of d2to pr d3 should be greater than the contribution of d1 The simplest solution is to allocate a weight of wde 1 L d to the hyperlink from document d to document e where L d is the number of hyperlinks from d Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Random Surfer Model wdecan be thought of as the probability of following the link to page e if the user is on page d The case where wde 1 L d corresponds to the random surfer model on any page the random surfer is equally likely to choose any of the available links Simplified Page Rank Calculation Once pr d is accepted as a measure of the importance of d there is a natural consequence In the calculation of pr d a hyperlink from a page d1to d should count for more than a hyperlink from page d2to d if pr d1 pr d2 This motivates where L d is the set of pages which link to page d Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Simplified Page Rank Calculation Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf pr 0 35 pr 0 1 pr 0 25 pr 0 15 pr d 1 3 1 3 1 3 1 1 2 1 2 1 Simplified Page Rank Calculation Change pr d will change the page ranks of other pages which in turn change pr d In other words the definition of page rank is recursive Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Markov Chain Interpretation Let Notice that each row of W sums to 1 Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Markov Chain Interpretation If the system converges then pr WTpr pr is the invariant distribution of the Markov chain In other word pr is an eigenvector of WT Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Damping Factor The model we have used to develop Page Rank is the random surfer model Now let s suppose that the random surfer will eventually stop clicking The probability that the random surfer continues clicking when he arrives at a page is called the damping factor and denoted by A typical value of is 0 85 Modified from http www eee bham ac uk russellm ee3j2 Slides 202009 OHP10 20Page 20Rank 202009 pdf Page Rank Taking into account the damping facto