资源预览内容
第1页 / 共44页
第2页 / 共44页
第3页 / 共44页
第4页 / 共44页
第5页 / 共44页
第6页 / 共44页
第7页 / 共44页
第8页 / 共44页
第9页 / 共44页
第10页 / 共44页
亲,该文档总共44页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五章 离散时间马尔可夫链马尔可夫过程是前苏联数学家A.A.Markov首先提出 和研究的一类随机过程. 经过世界各国几代数学家的相继努力,至今已成为内 容十分丰富,理论上相当完整,应用也十分广泛的一门 数学分支.它的应用领域涉及计算机、通讯、自动控制、随机 服务、可靠性、生物、经济、管理、气象、物理、 化学等.马尔可夫 (1856年6月14日1922年7月20日)马尔可夫对数学的最大贡献是在概率论领域作出的 十九世纪后二十年,他主要是沿着切比雪夫开创的 方向,致力于独立随机变量和古典极值理论的研究, 从而改进和完善了大数定律和中心极限定理二十世纪初,他的兴趣转移到相依随机变量序列的 研究上来,从而创立了以他命名的著名概率模型 马尔可夫链王梓坤院士(1929年)江西吉安人,1952年大学毕业后,被分派 到天津南开大学数学系任教. 是一位对我国科学和教育事业作出 卓越贡献的数学家和教育家,也是我国概率论研究的先驱和学术 带头人之一。1954年,他又以优异的成绩考取了赴苏研究生。踏进世界著 名学府莫斯科大学,在这个学府世界概率论的奠基人柯尔莫哥 洛夫院士正领导看一个强有力的概率研究集团。柯尔莫高洛夫慧 眼识英才,非常信赖这位由中国选派的年轻人的能力,把他选作 自己的研究生,去攻概率论的中心问题随机过程理论。 当时中国近代数学才刚刚起步,大学也没有概率课程。此时 苏联的概率论水平已届于世界最前列。王梓坤也根本不知道什么 是概率,可他的研究方向又恰恰被定为概率论, 著有概率论基础及其应用、随机过程论、 生灭过程与马尔科夫链等9部数学著作 马尔可夫过程的定义马尔可夫链的转移概率与概率分布齐次马尔可夫链状态的分类转移概率的稳定性能本章主要内容引例(有限制随机游动问题)设质点只能在0,1,2,a中的各点上作随机游动,移动规则如下:ii+1i-101a-1a设Xn表示质点在n时刻所处的位置1 马尔可夫过程的定义一.基本概念二.1马尔可夫性通俗地说,就是在知道过程现在的条件下,其 将来的条件分布不依赖于过去,则称 具有马尔可夫(Markov)性。定义 设是一个随机过程,如果 在t0时刻所处的状态为已知,它在时刻所处状态的条件分布与其在 t0 之前 所处的状态无关。2. 马尔可夫过程定义 设的状态空间为S,的条件分布函数恰好等于3.马尔可夫链定义 参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。注 只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为特别 对取T=0,1,2,的马尔可夫链,记为或此时的马尔可夫性为或今后,记二 马尔可夫链的转移概率 1. 转移概率 定义 设是马尔可夫链,称条件概率经过k步转移,于n+k时到达状态j的条件概率).在n时的k步转移概率.n时的k步转移概率矩阵.特别 当k=1时,定义 称可数维的矩阵为随机矩阵,如果显然,在n时的k步转移概率矩阵是一随机矩阵.特别 k时,约定实际中常会碰到具有时齐性的马氏链若对任意的状态i, j和时刻n,均有则称马氏链X具有时齐性,或称X为其次马尔科夫 链,简称齐次马氏链.引理(有限制随机游动问题)设质点只能在0,1,2,a中的各点上作随机游动,移动规则如下:ii+1i-101a-1a设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个球, 它们或是红色的,或是黑色的,从坛子中随机的摸出 一球,并换入一个相反颜色的球.其一步转移概率矩阵为为状态空间的齐次马尔可夫链.设经过n次摸换,坛中黑球数为Xn,则例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.马尔可夫链 的分布称 第i个分量为的(行)向量为马尔可夫链的初始分布向量. 即2)有限维分布定理 马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定.证明又因为马尔可夫链的k步转移概率由一步转移概率所 完全确定.所以马尔可夫链的有限维分布由其初始分布和 一步转移概率所完全确定.3)绝对分布为马尔可夫链 的绝对分布称 第j个分量为的(行)向量为马尔可夫链的绝对分布向量. 即绝对分布、初始分布和n步转移概率有如下关系:或矩阵形式的有限维分布由其初始分布和一步转移概率所完全确定齐次马氏链有相应的结果例 设是具有三个状态0,1,2的齐次马尔可夫链,其一步转移概率矩阵为初始分布试求:解例:如果将社会家庭中个体的收入分为低收入、 中等收入和高收入三个等级,则早在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公司却下降,通过市场调查发现三公司 间的顾客流动情况如下表:公司周期0的顾顾 客数周期1的顾顾客数 A B C A50003500 500 1000 B3000300 2400 300C2000100 100 3100 周期2的顾顾客数 100003900 3000 3100其中产品销售周期是季度,现在的问题是按照目前的 趋势发展下去,A公司的销售额或客户转移的影响将 严重到什么程度?更全面的,三个公司的产品销售额 的占有率将如何变化?转移概率矩阵初始分布:第一周期的市场占有率向量为:第k周期的市场占有率向量为:练习 设是状态空间为a,b,c的齐次马氏链.其一步转移概率矩阵为
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号