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

第五章第五章 离散时间马尔可夫链离散时间马尔可夫链马尔可夫过程是前苏联数学家马尔可夫过程是前苏联数学家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,10,1，则昨，则昨天和今天的所有天气情况可以用数对表示为集合天和今天的所有天气情况可以用数对表示为集合S={S={（（1,11,1），（），（1,01,0），（），（0,10,1），（），（1,11,1））} }，由此，，由此，将数对看做状态，天气的变化过程可用状态空间为将数对看做状态，天气的变化过程可用状态空间为S 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: n≥0}是一个是一个齐次次马氏氏链.例例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, n≥0}是描述天气是描述天气变化的化的齐次次马尔科夫科夫链，状，状态空空间为S={0,1},其中其中0,1分分别表示有雨和无表示有雨和无雨，雨，X的一步的一步转移概率矩移概率矩阵为试对任意的试对任意的i, j∈∈S,计算三步转移概率计算三步转移概率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 CA50003500 500 1000B3000300 2400 300C2000100 100 3100周期周期2的顾客数的顾客数 100003900 3000 3100其中产品销售周期是季度，现在的问题是按照目前的其中产品销售周期是季度，现在的问题是按照目前的趋势发展下去，趋势发展下去，A公司的销售额或客户转移的影响将公司的销售额或客户转移的影响将严重到什么程度？更全面的，三个公司的产品销售额严重到什么程度？更全面的，三个公司的产品销售额的占有率将如何变化？的占有率将如何变化？转移概率矩阵转移概率矩阵初始分布初始分布：第一周期的市场占有率向量为第一周期的市场占有率向量为：第第k周期的市场占有率向量为周期的市场占有率向量为：练习练习 设是状态空间为{a,b,c}的齐次马氏链.其一步转移概率矩阵为。