《马尔可夫链》PPT课件.ppt

第十一章 马尔可夫链,主要内容：,1. 定义（与记号）,2. 转移概率与矩阵,3. 遍历性,返回目录,1马尔可夫性的定义：,由时刻 系统的状态，可以决定系统在t 时所处的状态，而与 以前系统的历史状态无关。如微分方程的定解问题。,对于随机现象，可以描述如下：,系统在 时刻所处的状态为已知的条件下，系统在时刻t 所处状态的条件分布与在时刻 之前所处的状态无关。, 数学表达式：,先做一些假设：,随机过程设为X(t), 状态空间I= ，任选T中n个时刻, ，对应的状态为 ，则 的马氏性就是这样一个条件分布函数：,=, 马尔可夫链：,时间和状态都离散的马尔可夫过程称为马尔可夫链。,记为 ，状态空间I=,而相应的马尔可夫性用条件分布律示如下：,=,2转移概率：,记上面的条件概率为：,称为转移概率，它表示马氏链在时刻m处于状态的条件下，经过n步变化后，在时刻m+n处于状态的条件概率。,3转移概率矩阵：,当上式中,取遍状态空间I时(此时假,设I有限)，会得到N N个转移概率,它们可以组成一个N N 的矩阵，称为转移概率矩阵，,记为,它表现了马氏链经过n步后所有可能发生的状态之间的转移。,由概率的规范性，容易得到P(m,m+n)的一个性质:每一行元素横向相加等于1。,4. 齐次马氏链：,当,只与步数n有关，与起始时刻,m无关时，称此转移概率具有平稳性，或称此链是齐次马氏链。,可以记为,我们特别要掌握一步转移概率：,以及由它们组成的一步转移概率矩阵：,5例题：,例2（ ）：在01传输系统中，设每一级的传真率为p，误码率为q=1-p,并设一个单位时间传输一级， 是第一级的输入， 是第n级的输出。那么 是一个马氏链，而且还是齐次的，其状态空间I=0,1。,例3（ ）一维随机游动：设一质点在图示直线的点集I=1,2,3,4,5上作随机游动，且仅在1秒2秒等时刻发生游动。游动的概率规则是：如果点Q现在位于点i（1i5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在位于1（或5）这点上，则下一时刻就以概率1移动到2（或4）这一点上。若以 表示时刻n时Q的位置,则 是一齐次马氏链，它的一步转移概率矩阵为：,例4,排队模型：设服务系统由一个服务员,和只可以容纳两个人的等侯室组成。服务规则是先到先服务，后来者需在等候室排队。,假定一个顾客到达系统时发现系统内已有板有3个顾客，则该顾客即离去。设时间间隔t内有一个顾客进入系统的概率为q,有一原来被服务的顾客离开系统的概率为p。,又设当t充分小时，在这时间间隔内多于一个顾客进入或离开系统是不可能的。可用马氏链来描述这个服务系统,图 形,例6：（续例5）已知计算机在某一时段（15分钟） 的状态为0，问在此条件下从此时段起此计算机能连续正常工作3个时段的条件概率为多少？,6齐此马氏链的有限维分布：,先看初始分布：,是一个离散型的随机,变量，其分布律称为初始分布，可以表为：,也可以用表格式：,（2）再来看任意时刻n的一维分布：,显然，由规范性有：,另外，可以用行向量来表示分布律：, 初始分布律与任意时刻n的分布律 之间的关系:,以 的各状态值分布为划分，运用全概率公式， 即可得到：,用矩阵乘法来表达如下：,back,第二节 多步转移概率的确定,内容提要：,1. C-K方程形式,2. 方程的意义,3. 方程的证明,4. 例题,back,1C-K方程：,设,是一齐次马氏链，对,任意的u,v T，有：,用矩阵表示即：,P(u+v)=P(u)P(v),back,2方程的意义：,如果设初始时刻s，终止时刻是s+u+v。 引入中间时刻s+u，C-K方程的意义在于：,“从s时刻的状态 出发,经u+v步后转移到 状态,这一事件等价于,“从 出发，先经u步转移到中间状态 ，再从 经时段v转移到 的和事件。,back,3证明：,back,例1：设 是具有三个状态0，1，2的齐次 马氏链，一步转移矩阵为：,P=,初始分布,试求：,例2（1）在1例2中，设p=0.9，求系统二级传输后 的传真率与三级传输后的误码率；,（2）设初始分布， 。,又已知系统经n级传输后输出为1，问原发字符也是1的概率是多少？,back,第三节 遍 历 性,主要内容：,1. 举例,2. 定义,3 .有限链的遍历性充分条件,4.平稳分布,5.总结,6.例题,back,1举例：在上面例2中的一步转移矩阵,P=,计算其n步转移矩阵P(n)为,，它存在着极限,（矩阵的两行完全相同）,back,2定义：,（1）语言描述：,对固定状态j，无论链从什,么状态出发（即与左边的列无关），经过长时间的转移后，到达状态j的概率都趋近于,。,这个性质称为遍历性。,（2）数学式子表达：,或者：,（与i无关）,特别地，将行向量 提出来，由于它构成了一个分布律，即 ，称它为极限分布。,back,3遍历性的充分性条件：,定理：对齐次马氏链 ，状态空间 I= ,一步转移矩阵P(1)。,如果存在正整数m，使对任意的 ，都有 ，即矩阵P(m)= 中无零元素，,则此链具有遍历性。且其极限分布就是方程组=P(1)的满足 的唯一解。,back,4平稳分布：,在上述定理的条件下，又称为平稳分布。,其意义在于：,= 是所有状态分布中的平衡值，一旦链的状态分布达到了= ，则链的一维状态分布不会再发生变化了。,back,5总结：, 的多重意义：,(1) 代表了遍历性的存在。,(2) 极限分布。,(3) 在充分条件下，也是链的平稳分布。,back,6例题：,例1：试说明1例3中的随机游动是遍历的，并 求其极限分布。,例2：试说明1例4排队模型中的链是遍历的， 并求其极限分布。,例3：设一马氏链的一步转移矩阵为,，试讨论它的遍历性。,补充例题：若顾客的购买是无记忆的。现在市场上供应A,B,C三个不同厂家生产的50g袋装味精。,用 分别表示事件“顾客第n次购买A,B,C三厂的味精”，,则 是一个马氏链。已知顾客第一次购买三种味精的概率依次为0.2，0.4，0.4。又知道一般顾客购买的倾向表如下