《概率论教学课件作者工程 第四章1－MARKOV链 兼容模式》由会员分享，可在线阅读，更多相关《概率论教学课件作者工程 第四章1－MARKOV链 兼容模式（72页珍藏版）》请在金锄头文库上搜索。
1、2014 10 30北京邮电大学电子工程学院 1 第四章 Markov链 内容内容 Markov链的概念及转移概率 包括一步和n步转移概率 的概念 n步转移概率与一步转移概率的关系 Markov链的状态分类 状态空间的分解 平稳分布 重点重点 Markov链的定义 一步转移概率及状态分类 难点难点 状态分类 2014 10 30北京邮电大学电子工程学院 2 前面讨论的随机过程是按照其数字特征来进行分类前面讨论的随机过程是按照其数字特征来进行分类 的的 在本章我们将对在本章我们将对Markov过程按其状态空间过程按其状态空间I和参数和参数 集集T进行分类进行分类 1 I和和T均离散均离散 即为本
2、章将要讨论的即为本章将要讨论的Markov链链 2 I离散离散 但但T连续连续 即为纯不连续的即为纯不连续的Markov过程过程 间间 断型断型Markov 过程过程 3 I和和T均连续均连续 即为连续型即为连续型Markov过程过程 不妨假设不妨假设 01 0 1 2 IxxIiT 以后令以后令 2014 10 30北京邮电大学电子工程学院 3 第一节第一节 Markov链的概念及转移概率链的概念及转移概率 一一 Markov链的定义链的定义 01 1 110011 4 1 1 4 1 1 n n nnnnnnnn n M nTnTi i iI Pi arkov iiPii Markov 若
3、若随随机机过过程程 对对 正正整整数数和和 有有 则则称称为为 上上式式所所 定定 表表达达的的性性质质称称为为性性 义义 链链 无无后后效效性性 011 1 若把时刻 看成 现在 把时刻 看成 过 去 把时刻看成 将来 那么性 无后效性 说 在已知系统 现在 所处状态的情况下 系统将来的状 态与 过去 所经历的状态无关 解 释 nn nMarkov 2014 10 30北京邮电大学电子工程学院 4 1 4 2 1 ijnn n ijij pnPjiMarkov nTi jI pni jnpn nMarkov 称称条条件件概概率率为为链链 的的 其其中中 一一般般地地 不不仅仅与与有有关关 而
4、而且且也也与与 有有关关 若若 不不依依赖赖于于 则则链链具具有有平平稳稳的的转转移移概概率率 即即转转移移概概 一一步步转转 率率具具 有有 移移概概率率 定定义义 平平稳稳性性 1 12 12 1 随随机机过过程程为为链链的的充充要要条条件件是是对对任任意意 的的正正整整数数及及任任意意的的非非负负整整数数 以以及及 定定理理 任任 意意的的有有 r n r r m knnrmm km nTMarkov m knnnm i ii i jI PjiiiPji 2014 10 30北京邮电大学电子工程学院 5 111 212 1 2 10 2 4 1 1 4 1 n ijn ij ij j I
5、 I pp Pppp pi jI piI i 一一步步转转移移概概率率矩矩阵阵 称称 为为系系统统的的 随随机机矩矩阵阵 它它具具有有如如下下性性质质 从从状状态态 出出发发转转移移到到系系统统各各个个状状态态的的概概 定定 率率之之和和为为 义义 4 1 3 ij ijij Markovpn npnp Markov 若链具有平稳的转移概率若链具有平稳的转移概率 即与即与 无关无关 则称马氏链是的则称马氏链是的 记为记为 本章只讨论本章只讨论 定定 齐次齐次 齐次齐次 的的 义义 链链 2014 10 30北京邮电大学电子工程学院 6 1 2 3 4 2 31 3 1141 1 1 3 n X
6、n 质质点点在在 四四个个整整数数点点上上随随机机游游动动 当当质质点点在在 时时分分别别以以的的概概率率向向左左 向向右右 或或停停留留在在原原地地 当当质质 点点在在 时时以以概概率率 返返回回原原地地 质质点点在在 时时以以概概率率 返返回回到到 若若 以以表表示示质质点点在在时时刻刻 所所处处的的位位置置 求求其其转转移移概概 例例 率率矩矩阵阵 11121314 21222324 32333431 43414244 1 2 3 4 10 1 30 1 30 10 1000 1 31 31 30 01 31 31 3 0010 pppp pppp pppp pppp P 由由题题意意知
7、知 状状态态空空间间为为 且且 则则 解解 2014 10 30北京邮电大学电子工程学院 7 12 34 1 1 3 1 3 1 31 3 1 1 3 1 3 试试画画出出状状态态转转移移图图如如下下 1 4 1 4 由由状状态态转转移移图图 我我们们 知知道道 是是质质点点游游动动不不可可 越越过过的的壁壁 因因此此 为为 即即质质点点到到达达该该 吸吸收收壁壁 反反 射射壁壁 点点后后就就被被完完 全全吸吸住住 不不再再转转移移 为为 即即质质点点一一旦旦到到达达该该 状状态态 必必然然被被反反射射回回去去 2014 10 30北京邮电大学电子工程学院 8 1 2 t q ptt 设设服服
8、务务系系统统由由一一个个服服务务员员和和只只容容纳纳两两个个人人 的的等等候候室室组组成成 服服务务规规则则是是 先先到到先先服服务务 后后来来者者需需在在等等候候 室室依依次次排排队队 假假定定一一个个顾顾客客到到达达系系统统时时发发现现系系统统内内已已有有三三个个 顾顾客客 则则该该顾顾客客即即离离去去 设设时时间间间间隔隔内内将将有有一一个个顾顾客客进进入入 系系统统的的概概率率为为 原原来来被被服服务务的的顾顾客客离离开开系系统统 即即服服务务完完毕毕 的的概概率率为为 又又设设当当充充分分小小时时 在在的的时时间间间间隔隔内内多多于于一一个个 顾顾客客进进入入或或离离开开系系统统实实
9、际际上上是是不不可可能能的的 再再设设有有无无顾顾客客来来到到 与与服服务务是是否否 例例 排排队队模模型型 完完毕毕是是相相互互独独 n n tn t 立立的的 现现用用马马氏氏链链来来描描述述该该系系统统 设设表表示示时时刻刻时时系系统统内内的的顾顾客客数数 计计算算其其一一步步转转 移移概概率率矩矩阵阵 0 1 2 3 I 分析 2014 10 30北京邮电大学电子工程学院 9 001 0001 00 1 nn pP t pqpq 根据题意根据题意 系统内原本没有顾客系统内原本没有顾客 经过的时间间隔后仍然没有顾客的概率经过的时间间隔后仍然没有顾客的概率 即无人进入该系统即无人进入该系统
10、 因此因此 同理同理 解解 多于一个的顾客离开多于一个的顾客离开 的时间间隔内不可能有的时间间隔内不可能有 tpp 0 0302 101 10 01 1 nn pPt t ppq 系统原有一个顾客 经过的时间间隔后 没有顾客的概率 即的时间间隔内原有顾客因服务完毕而离 开 且没有任何人进入该系统 因此 qppqp tPp nn 11 11 11 111 进入系统进入系统 所以所以离开离开 同时无新的顾客同时无新的顾客 或者原有顾客没有或者原有顾客没有新的顾客进入该系统新的顾客进入该系统 完毕而离开完毕而离开 且有一个且有一个 者原有顾客因服务者原有顾客因服务 这里有两种情况这里有两种情况 或或
11、后仍为一个顾客的概率后仍为一个顾客的概率 的时间间隔的时间间隔过过系统原有一个顾客系统原有一个顾客 经经 等候室服务台随机到达者随机到达者离去者离去者 qp 2014 10 30北京邮电大学电子工程学院 10 20 211022112312 303132213332 0 1111 0111 100 11110 01111 0011 pt pppqpppqpqpppq pppppqpppqp qq pqpqpqqp P pqpqpqqp pqpqp 类类似似地地有有 的的时时间间间间隔隔内内不不可可能能有有多多于于一一个个的的顾顾客客进进入入 而而 同同理理 则则 0 13 13 113 p t
12、Pp nn 客离开客离开 多于一个顾多于一个顾的时间间隔内不可能有的时间间隔内不可能有 因因 pqp t tPp nn 1 12 12 112 统的概率统的概率 显然显然 开开 且有一人进入该系且有一人进入该系 未服务完毕离未服务完毕离的时间间隔内原有顾客的时间间隔内原有顾客 即即系统有两个顾客的概率系统有两个顾客的概率 的时间间隔后的时间间隔后过过系统原有一个顾客系统原有一个顾客 经经 2014 10 30北京邮电大学电子工程学院 11 0a 1a 1aa b pq 1 1 ab pqp 两两赌赌徒徒甲甲 乙乙进进行行一一系系列列赌赌博博 赌赌徒徒甲甲有有 元元 赌赌徒徒乙乙有有 元元 每每
13、赌赌一一局局输输者者给给赢赢者者 元元 直直到到两两人人中中有有一一个个 输输光光为为止止 设设在在每每一一局局中中 甲甲赢赢的的概概率率为为 输输的的概概率率 例例1 31 3 为为 求求 赌赌博博输输光光问问题题 甲甲输输光光的的概概率率 0 1 2 0 Iccaba c 这这个个问问题题实实质质上上是是带带有有两两个个吸吸收收壁壁的的随随机机游游动动 其其状状态态空空间间 故故现现在在的的问问题题是是求求质质点点从从 点点出出发发 到到达达 状状态态先先于于到到达达状状态态 的的概概率率 0 0 010 i ac ui ucuu 设设 表表示示甲甲从从状状态态 出出发发转转移移到到状状态
14、态 的的概概率率 我我们们要要计计算算 的的是是 由由于于 和和 是是吸吸收收状状态态 故故 解解 2014 10 30北京邮电大学电子工程学院 12 11 1 2 1 1 1 iii upuquic ip iq i 由由全全概概率率公公式式 有有 即即甲甲从从有有 元元直直到到输输光光的的概概率率等等于于 他他接接下下去去以以概概率率赢赢了了一一局局 处处于于状状态态后后再再输输光光 和和 他他接接下下去去以以概概率率输输了了一一局局 处处 于于状状态态后后再再输输光光 这这两两个个互互不不相相容容的的事事件件的的并并事事件件的的概概率率 11 0 1 1 2 1 10 iiii c pq
15、q uur uuicr p uu 由由 则则上上式式实实质质上上是是一一个个差差分分方方程程 其其中中 边边界界条条件件为为 1110 1110 1 i iiii i k i k uur uur uu uuuur 由由 故故 2014 10 30北京邮电大学电子工程学院 13 1 1 11 2 1 1 11 2 1 1 i a b rpq u c i uic c b a iau c ab a u ab 即即 得得 从从而而得得 令令 求求得得甲甲输输光光的的概概率率为为 由由于于甲甲 乙乙的的地地位位是是对对称称的的 故故乙乙输输光光的的概概率率为为 1 21 1 1 2 1 1 1 c c
16、ic ic ac ac rpq rr u r rr uic r rr iau r 即即的的情情况况 得得 从从而而得得 令令 得得甲甲输输光光的的概概率率为为 2014 10 30北京邮电大学电子工程学院 14 10 1 10 21 1 1 5 0 4 1 n ijm nm nn nij n nn ijij j I n ij pPjii jI n MarkovnTPpMarkov n pp ij PnPPp ij n n 称称条条件件概概率率为为 链链的的 并并称称为为 链链的的 步步转转移移概概率率矩矩阵阵 其其中中 即即为为随随机机矩矩阵阵 当当时时 补补充充定定义义 二二 马马尔尔可可夫夫链链的的 步步转转移移概概率率 定定义义 步步转转移移概概率率 11 21 11 1 0 4 1 1 1 2 1 34 n n n n ij nln l ijikkj k I nnnnn ijikk kkj kIkI nTMarkovnln i jI p pppChapmanKolmogorov ppppPP PPP CK 记记 初初始始概概率率向向量量 时时刻刻的的绝绝对对概概率率向向量量 1
