随机过程马尔科夫过程.ppt

第五章 离散时间马尔可夫链,马尔可夫过程是前苏联数学家A.A.Markov首先提出 和研究的一类随机过程. 经过世界各国几代数学家的相继努力,至今已成为内容十分丰富,理论上相当完整,应用也十分广泛的一门数学分支. 它的应用领域涉及计算机、通讯、自动控制、随机服务、可靠性、生物、经济、管理、气象、物理、化学等.,马尔可夫 (1856年6月14日1922年7月20日）,马尔可夫对数学的最大贡献是在概率论领域作出的十九世纪后二十年，他主要是沿着切比雪夫开创的方向，致力于独立随机变量和古典极值理论的研究，从而改进和完善了大数定律和中心极限定理 二十世纪初，他的兴趣转移到相依随机变量序列的研究上来，从而创立了以他命名的著名概率模型马尔可夫链,王梓坤院士(1929年)江西吉安人,1952年大学毕业后，被分派到天津南开大学数学系任教. 是一位对我国科学和教育事业作出卓越贡献的数学家和教育家，也是我国概率论研究的先驱和学术带头人之一。 1954年，他又以优异的成绩考取了赴苏研究生。踏进世界著名学府莫斯科大学，在这个学府世界概率论的奠基人柯尔莫哥洛夫院士正领导看一个强有力的概率研究集团。柯尔莫高洛夫慧眼识英才，非常信赖这位由中国选派的年轻人的能力，把他选作自己的研究生，去攻概率论的中心问题随机过程理论。 当时中国近代数学才刚刚起步，大学也没有概率课程。此时苏联的概率论水平已届于世界最前列。王梓坤也根本不知道什么是概率，可他的研究方向又恰恰被定为概率论， 著有概率论基础及其应用、随机过程论、 生灭过程与马尔科夫链等9部数学著作,马尔可夫过程的定义 马尔可夫链的转移概率与概率分布 齐次马尔可夫链状态的分类 转移概率的稳定性能,本章主要内容,引例(有限制随机游动问题) 设质点只能在0，1，2，a中的各点上作随机 游动，移动规则如下：,设Xn表示质点在n时刻所处的位置,1 马尔可夫过程的定义,基本概念 1马尔可夫性,2. 马尔可夫过程,的条件分布函数恰好等于,3.马尔可夫链,定义 参数集和状态空间都是离散的马尔可夫过程 称为马尔可夫链。,注 只讨论马尔可夫链的状态空间为有限或可列无限.,则马尔可夫性可表示为,特别 对取T=0,1,2,的马尔可夫链，记为,或,此时的马尔可夫性为,或,今后,记,二 马尔可夫链的转移概率,1. 转移概率,经过k步转移,于n+k时到达状态j的条件概率).,在n时的k步转移概率.,n时的k步转移概率矩阵.,特别 当k=1时，,特别 k时，约定,实际中常会碰到具有时齐性的马氏链,若对任意的状态i, j和时刻n，均有,则称马氏链X具有时齐性，或称X为其次马尔科夫链，简称齐次马氏链.,引理(有限制随机游动问题) 设质点只能在0，1，2，a中的各点上作随机 游动，移动规则如下：,设Xn表示质点在n时刻所处的位置，则,其一步转移概率矩阵为,例(天气预报问题) 如果明天是否有雨仅与今天的天气(是否有雨)有关，而与过去的天气无关. 并设 今天下雨、明天有雨的概率为a， 今天无雨而明天有雨的概率为b，又假设 有雨称为0状态天气，无雨称为1状态天气. Xn表示时刻n时的天气状态，则,天气的变化过程还可以用不同的马尔科夫链来描述，假设任意一天的天气与前一天的天气有关，即如果昨天和今天都为晴天，明天为晴天的概率为，昨天和今天分别为晴天和阴天，明天为晴天的概率为，昨天和今天分别为阴天和晴天，明天为晴天的概率为，如果昨天和今天都为阴天，明天为晴天的概率为。如果将阴天和晴天分别记为0,1，则昨天和今天的所有天气情况可以用数对表示为集合S=（1,1），（1,0），（0,1），（1,1），由此，将数对看做状态，天气的变化过程可用状态空间为S上的其次马尔科夫链描述，一步转移概率矩阵为：,练习 天气预报问题，其模型是：今天是否下雨依赖于前三天是否有雨（即一连三天有雨；前面两天有雨，第三天晴天),问能否把这一问题归纳为一马尔科夫链，如果可以，问该过程的状态有几个？如果过去一连三天有雨，今天有雨的概率为0.8；过去连续为晴天，而今天有雨的概率为0.2；在其他天气情况，今天的天气和昨天相同的概率为0.6，求这个马儿科夫链的转移概率.,例2 （埃伦菲斯特模型）设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的球.,其一步转移概率矩阵为,例3（群体增长）某种生物群体的每个个体在其生存期内彼此独立地产生后代，假设每个个体都以概率pk产生k个后代，且有,用Xn表示第n代生物群体的总数，它是生物群体的第n-1代的每个个体的后代个数的总和，因此第n+1代的个体总数仅依赖于第n代的个体总数，所以X=Xn, n=0,1,2,是一个马尔科夫链，状态空间为S=0,1,2，,则马氏链的一步转移概率为：,如果记第n代的生物群体个数,记i个个体各自产生的后代数分别记为随机变量 ，且 有概率分布,故一步转移概率为,例4（卜里耶模型）设一个坛子里有b个黑球和r个红球，每次随机地从坛子中摸出一个球后再放回去，并加入c个与摸出球同颜色的球。重复以上步骤将摸球进行下去，设Xn表示第n次摸球放回后坛子中的黑球数，试写出其一步转移概率矩阵和状态空间,例5：设 是相互独立同分布的随机变量序列，且,令随机序列：,验证：随机序列X=Xn: n0是一个齐次马氏链.,例6（网页浏览）用集合 表示因特网中的所有网页，假设网页 上的超级链接数为 ，对应的网页集合为 ，用户进入网页 后，按照以下规则进入新的网页；以概率p进入网页集合S中任何一个网页或者以概率q进入 的任一个超级链接，令Xn表示用户在n次选取后所在的网页，问Xn是非是一马氏链，若是的话，写出其一步转移概率.,. 马尔科夫链的概率分布,定理 (C-K方程),或矩阵形式,（解决了k步转移概率与一步转移概率间的关系）,证明,系统在n 时从状态i的出发,经过k+m步转移,于n+k+m时到达状态j,可以先在n时从状态i出发，经过k步转移于n+k时到达某种中间状态l,再在n+k时从中间状态l出发经过m步转移于n+k+m时到达最终状态j,而中间状态l要取遍整个状态空间S.,C-K方程的直观意义：,定理 马尔可夫链的k 步转移概率由 其一步转移概率 所完全确定.,若取m=1,则由C-K方程的矩阵形式:,得,分量形式,齐次马尔可夫链,为方便，一般假定时间起点为零即,对齐次马尔可夫链，k步转移概率也与起始 时刻n无关记为,相应的k步与一步转移概率矩阵分别记为,例：设Xn, n0是描述天气变化的齐次马尔科夫链，状态空间为S=0,1,其中0,1分别表示有雨和无雨，X的一步转移概率矩阵为,试对任意的i, jS,计算三步转移概率,1）初始分布,为马尔可夫链的初始分布,3.马尔可夫链 的分布,2）有限维分布,证明,又因为马尔可夫链的k步转移概率由一步转移概率所 完全确定.,所以马尔可夫链的有限维分布由其初始分布和 一步转移概率所完全确定.,3）绝对分布,为马尔可夫链 的绝对分布,的绝对分布向量. 即,绝对分布、初始分布和n步转移概率有如下关系：,或矩阵形式,的有限维分布由其初始分布和一,步转移概率所完全确定,齐次马氏链有相应的结果,解,例：如果将社会家庭中个体的收入分为低收入、中等收入和高收入三个等级，则早在20世纪50年代，社会学研究者发现个体收入的等级在很大程度上取决于其父代收入的等级。如果令Xn表示一个家庭第n代个体的收入等级，并用1,2,3分别表示低收入，中等收入和高收入，则一个家庭中相继的后代收入等级的变化可以用其次马尔科夫链来描述，状态空间为S=1,2,3，并且有以下的转移的概率矩阵,如果当前收入等级为3，试分析经过三代后个体收入等级转变为2的可能性，进一步分析经过n代后个体收入等级的概率分布，并具体计算n=10时个体收入等级的概率分布。,例（市场预测）公司A,B,C是某地区三家主要灭虫剂厂商，根据历史资料得知，公司A,B,C产品销售额的市场占有率分别为50%,30%,20%.由于C公司实行了改善销售与服务方针的经营管理策略，使其产品销售额逐步稳定上升，而A公司却下降，通过市场调查