随机过程马尔科夫过程PPT学习教案

1、会计学1随机随机(su j)过程马尔科夫过程过程马尔科夫过程第一页，共44页。王梓坤院士王梓坤院士(1929年年)江西吉安人江西吉安人,1952年大学毕业后，被分派年大学毕业后，被分派到天津南开大学数学系任教到天津南开大学数学系任教. 是一位对我国科学和教育事业作出是一位对我国科学和教育事业作出卓越贡献的数学家和教育家，也是我国概率卓越贡献的数学家和教育家，也是我国概率(gil)论研究的先论研究的先驱和学术带头人之一。驱和学术带头人之一。 1954年，他又以优异的成绩考取了赴苏研究生。踏进世界著年，他又以优异的成绩考取了赴苏研究生。踏进世界著名学府莫斯科大学，在这个学府世界概率名学府莫斯科大学

2、，在这个学府世界概率(gil)论的奠基人论的奠基人柯尔莫哥洛夫院士正领导看一个强有力的概率柯尔莫哥洛夫院士正领导看一个强有力的概率(gil)研究集团研究集团。柯尔莫高洛夫慧眼识英才，非常信赖这位由中国选派的年轻。柯尔莫高洛夫慧眼识英才，非常信赖这位由中国选派的年轻人的能力，把他选作自己的研究生，去攻概率人的能力，把他选作自己的研究生，去攻概率(gil)论的中心论的中心问题随机过程理论。问题随机过程理论。 当时中国近代数学才刚刚起步，大学也没有概率当时中国近代数学才刚刚起步，大学也没有概率(gil)课课程。此时苏联的概率程。此时苏联的概率(gil)论水平已届于世界最前列。王梓坤论水平已届于世界最

3、前列。王梓坤也根本不知道什么是概率也根本不知道什么是概率(gil)，可他的研究方向又恰恰被定，可他的研究方向又恰恰被定为概率为概率(gil)论，论，著有概率著有概率(gil)论基础及其应用、随机过程论、论基础及其应用、随机过程论、生灭过程与马尔科夫链等生灭过程与马尔科夫链等9部数学著作部数学著作 第2页/共44页第二页，共44页。马尔可夫过程的定义马尔可夫过程的定义马尔可夫链的转移马尔可夫链的转移(zhuny)概率与概率分布概率与概率分布齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类转移转移(zhuny)概率的稳定性能概率的稳定性能本章主要本章主要(zhyo)内容内容第3页/共44页第三页，

4、共44页。 引例(有限制随机游动问题) 设质点只能在0，1，2，a中的各点上作随机 游动，移动(ydng)规则如下：11,2,1ia（）移动前处; 1, 0,rqprqp0000,0,1p rprii+1i-1pqr010p0r20i （ ）移动前处3ia（）移动前处a-1aqaar,0,1aaaaq rqr设设Xn表示质点在表示质点在n时刻时刻(shk)所处的位置所处的位置第4页/共44页第四页，共44页。1马尔可夫过程马尔可夫过程(guchng)的定义的定义一.一.基本概念基本概念1马尔可夫性马尔可夫性通俗地说，通俗地说，就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，就是在知道

5、过程现在的条件下，其将来的条件分布不依赖于过去，则称则称),(TttX具有具有马尔可夫（马尔可夫（Markov)性。性。定义定义设设),(TttX是一个随机过程，如果是一个随机过程，如果),(TttX在在t0时刻所处的状态为已知，它在时刻所处的状态为已知，它在时刻时刻0tt 所处状态的条件分布与其在所处状态的条件分布与其在 t0 之前之前 所处的状态无关。所处的状态无关。0tt现在0tt将来0tt过去第5页/共44页第五页，共44页。2. 马尔可夫过程马尔可夫过程(guchng)定义定义 设设),(TttX的状态空间为S,122,nntttT 如果对( ),1,2,1iiiX txxSin在条

6、件下)(ntX的条件分布函数恰好等于11()nnX tx在条件下的条件分布函数,即11221111( ),( ),()( )(,)()nnnnnnnnnP X txP X txX txX txX txXRtxx( ),X t tT马尔则称为可夫过程.第6页/共44页第六页，共44页。3.马尔可夫链马尔可夫链定义定义 参数集和状态空间都是离散的马尔可夫过程参数集和状态空间都是离散的马尔可夫过程(guchng)称为马尔可夫链。称为马尔可夫链。注注 只讨论马尔可夫链的状态只讨论马尔可夫链的状态(zhungti)空间为有限或可列无限空间为有限或可列无限.则马尔可夫性可表示则马尔可夫性可表示(biosh

7、)为为12122, , ,nnntttT i iiS 对11111122()( ),( )( )(),),nnnnnnnnnP X tiP X tixX tiX tiRX tiX ti有第7页/共44页第七页，共44页。特别特别(tbi)对取对取T=0,1,2,的马尔可夫链，记为的马尔可夫链，记为0),(nnX或0,nXn此时的马尔可夫性为此时的马尔可夫性为011, , ,nni iiS 对有0111(1)(1)(0),(1( )( ),nnnnP X niPXiXiX niXX niin10110111,),()nnnnnnnnXP XiP XXiXiiXii或今后今后,记记1,2,3,0,

8、1,2,ST,0nXn 马尔可夫链记为马氏链也称,或系统第8页/共44页第八页，共44页。二二 马尔可夫链的转移马尔可夫链的转移(zhuny)概率概率1. 转移转移(zhuny)概率概率定义定义 设0,nXn是马尔可夫链,称条件概率,0nXnni(它表示系统在 时处于状态的条件下经过k步转移,于n+k时到达状态(zhungti)j的条件概率).( )( )(,0,)1kijn knpnP Xj Xi jS nik,0nXn 为在在n时的时的k步转移概率步转移概率.( )( )kijipnj称以为第 行底 列元素的矩阵)()()()(npnkijkP,0nXn 为系统在n时的k步转移概率矩阵步转

9、移概率矩阵.第9页/共44页第九页，共44页。( )( )ijnp nP记为特别特别(tbi) 当当k=1时，时，(1)( )ijnpn 为系统在 时的一步转移概率,(1)(1)( )( )ijnpnP为系统的一步转移概率矩阵( )ijp n记为第10页/共44页第十页，共44页。定义定义 称可数维的矩阵称可数维的矩阵)(ijpP 为随机矩阵，如果为随机矩阵，如果0,(, )1,()ijijjpi jpi显然，显然，0,nXn在在n时的时的k步转移概率矩阵步转移概率矩阵)()(nkP是一随机是一随机矩阵矩阵.特别特别(tbi)k时，约定时，约定(0)1,00ijijijpi jS nij(0)

10、( )I.Pn 此时为单位矩阵第11页/共44页第十一页，共44页。实际实际(shj)中常会碰到具有时齐性的马氏链中常会碰到具有时齐性的马氏链若对任意若对任意(rny)的状态的状态i, j和时刻和时刻n，均有，均有( )(1)(2)ijijijpnpnpn则称马氏链则称马氏链X具有时齐性，或称具有时齐性，或称X为其次为其次(qc)马尔科夫链，简称齐次马氏链马尔科夫链，简称齐次马氏链.第12页/共44页第十二页，共44页。 引理(有限制随机(su j)游动问题) 设质点只能在0，1，2，a中的各点上作随机(su j) 游动，移动规则如下：11,2,1ia（）移动前处; 1, 0,rqprqp00

11、00,0,1p rprii+1i-1pqr010p0r20i （ ）移动前处3ia（）移动前处a-1aqaar,0,1aaaaq rqr第13页/共44页第十三页，共44页。设设Xn表示质点表示质点(zhdin)在在n时刻所处的位置，则时刻所处的位置，则其一步(y b)转移概率矩阵为,00,1, nXnSa是以为状态空间的齐次马尔可夫链.aarqprqprqprqpr000000000000000000000000P第14页/共44页第十四页，共44页。例例(天气预报问题天气预报问题) 如果明天是否有雨仅与今天如果明天是否有雨仅与今天(jntin)的天气的天气(是否有雨是否有雨)有关，而与过去

12、的天气无关有关，而与过去的天气无关. 并设并设今天今天(jntin)下雨、明天有雨的概率为下雨、明天有雨的概率为a，今天今天(jntin)无雨而明天有雨的概率为无雨而明天有雨的概率为b，又假设，又假设有雨称为有雨称为0状态天气，无雨称为状态天气，无雨称为1状态天气状态天气. Xn表示时刻表示时刻n时的天气状态，则时的天气状态，则0,nXn是以1 , 0S为状态空间的齐次马尔可夫链.其一步转移概率矩阵为其一步转移概率矩阵为bbaa11P第15页/共44页第十五页，共44页。天气的变化过程还可以用不同的马尔科夫链来描述，假设任意一天的天气与前一天的天气有关，即如果昨天和今天都为晴天，明天为晴天的概

13、率为天气的变化过程还可以用不同的马尔科夫链来描述，假设任意一天的天气与前一天的天气有关，即如果昨天和今天都为晴天，明天为晴天的概率为，昨天和今天分别为晴天和阴天，明天为晴天的概率为，昨天和今天分别为晴天和阴天，明天为晴天的概率为，昨天和今天分别为阴天和晴天，明天为晴天的概率为，昨天和今天分别为阴天和晴天，明天为晴天的概率为，如果昨天和今天都为阴天，明天为晴天的概率为，如果昨天和今天都为阴天，明天为晴天的概率为。如果将阴天和晴天分别记为。如果将阴天和晴天分别记为0,1，则昨天和今天的所有天气情况可以用数对表示为集合，则昨天和今天的所有天气情况可以用数对表示为集合S=（1,1），（），（1,0），

14、（），（0,1），（），（1,1），由此，将数对看做状态，由此，将数对看做状态(zhungti)，天气的变化过程可用状态，天气的变化过程可用状态(zhungti)空间为空间为S上的其次马尔科夫链描述，一步转移概率矩阵为：上的其次马尔科夫链描述，一步转移概率矩阵为：第16页/共44页第十六页，共44页。100001100001P第17页/共44页第十七页，共44页。练习练习天气预报问题，其模型是：今天是否下雨依赖于前三天是否有雨（即一连三天有雨；前面两天有雨，第三天晴天天气预报问题，其模型是：今天是否下雨依赖于前三天是否有雨（即一连三天有雨；前面两天有雨，第三天晴天.),问能否把这一问题归纳为一

15、马尔科夫链，如果可以问能否把这一问题归纳为一马尔科夫链，如果可以(ky)，问该过程的状态有几个？如果过去一连三天有雨，今天有雨的概率为，问该过程的状态有几个？如果过去一连三天有雨，今天有雨的概率为0.8；过去连续为晴天，而今天有雨的概率为；过去连续为晴天，而今天有雨的概率为0.2；在其他天气情况，今天的天气和昨天相同的概率为；在其他天气情况，今天的天气和昨天相同的概率为0.6，求这个马儿科夫链的转移概率，求这个马儿科夫链的转移概率.第18页/共44页第十八页，共44页。例例2 （埃伦菲斯特模型）设一个坛子中装有（埃伦菲斯特模型）设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的

16、摸出一球，并换入一个相反个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反(xingfn)颜色的球颜色的球.其一步转移概率其一步转移概率(gil)矩阵为矩阵为01000001010000000202000001010000010mmmmmmmmmP,0nXn 是以, 1 , 0mS为状态空间的齐次马尔可夫链为状态空间的齐次马尔可夫链.设经过设经过n次摸换次摸换,坛中黑球数为坛中黑球数为Xn,则则第19页/共44页第十九页，共44页。例例3（群体增长）某种生物群体的每个个体在其生存期内彼此独立地产生后代（群体增长）某种生物群体的每个个体在其生存期内彼此独立地产生后代(hud

17、i)，假设每个个体都以概率，假设每个个体都以概率pk产生产生k个后代个后代(hudi)，且有，且有00,(1,2,)1kkkpkp用用Xn表示第表示第n代生物群体代生物群体(qnt)的总数，它是生物群体的总数，它是生物群体(qnt)的第的第n-1代的每个个体的后代个数的总和，因此第代的每个个体的后代个数的总和，因此第n+1代的个体总数仅依赖于第代的个体总数仅依赖于第n代的个体总数，所以代的个体总数，所以X=Xn, n=0,1,2,是一个马尔科夫链，状态空间为是一个马尔科夫链，状态空间为S=0,1,2，第20页/共44页第二十页，共44页。则马氏链的一步则马氏链的一步(y b)转移概率为：转移概

18、率为：1()nnP Xj Xi如果记第如果记第n代的生物代的生物(shngw)群体个数群体个数nXi记记i个个体各自产生的后代数分别个个体各自产生的后代数分别(fnbi)记为随机变量记为随机变量 ，且，且 有概率分布有概率分布12,i (0,1, )lli(),0,1,2lkPkpk故一步故一步转移概率转移概率为为112()()nniP Xj XiPj第21页/共44页第二十一页，共44页。例例4（卜里耶模型）设一个坛子里有（卜里耶模型）设一个坛子里有b个黑球和个黑球和r个红球，每次随机地从坛子中摸出一个球后再放回去，并加入个红球，每次随机地从坛子中摸出一个球后再放回去，并加入c个与摸出球同颜

19、色的球。重复以上步骤将摸球进行下去，设个与摸出球同颜色的球。重复以上步骤将摸球进行下去，设Xn表示第表示第n次摸球放回后坛子中的黑球数，试写出其一步转移概率矩阵和状态次摸球放回后坛子中的黑球数，试写出其一步转移概率矩阵和状态(zhungti)空间空间1( )(),1,0,ijnnpnP Xj Xiijicbrncijibrnc 其他第22页/共44页第二十二页，共44页。例例5：设：设 是相互独立同分布的随机变量是相互独立同分布的随机变量(su j bin lin)序列，且序列，且:0nn(1),(1)1,0,0nnPpPppn 令随机令随机(su j)序列：序列：0,0nnkkXn验证：随机

20、序列验证：随机序列(xli)X=Xn: n0是一个齐次马氏链是一个齐次马氏链.第23页/共44页第二十三页，共44页。例例6（网页浏览）用集合（网页浏览）用集合 表示因特网中的所有网页，假设网页表示因特网中的所有网页，假设网页 上的超级链接数为上的超级链接数为 ，对应的网页集合为，对应的网页集合为 ，用户进入网页，用户进入网页 后，按照以下后，按照以下(yxi)规则进入新的网页；以概率规则进入新的网页；以概率p进入网页集合进入网页集合S中任何一个网页或者以概率中任何一个网页或者以概率q进入进入 的任一个超级链接，令的任一个超级链接，令Xn表示用户在表示用户在n次选取后所在的网页，问次选取后所在

21、的网页，问Xn是非是一马氏链，若是的话，写出其一步转移概率是非是一马氏链，若是的话，写出其一步转移概率.12=NS， ，i(1)iillN()iiS SSii+,=,jiiijjiqpSlNppSN第24页/共44页第二十四页，共44页。. 马尔科夫链的概率分布马尔科夫链的概率分布定理定理(dngl) (C-K方程方程)()( )()( )( )(),0, ,k mkmijilljlpnpn pnkn m ki jS或矩阵或矩阵(j zhn)形式形式)()()()()()(knnnmkmkPPP（解决了（解决了k步转移步转移(zhuny)概率与一步转移概率与一步转移(zhuny)概率间的关系）

22、概率间的关系）证明证明()( )k mijn k mnpnP Xj Xi ,()n kmnln kPXjliXX ,)()n k mnn klPXj XliX,)()n k mnnlkPXj XiXl 第25页/共44页第二十五页，共44页。)(,)(nn k mnnn klkPXiP Xj XXlXil )()nn k mn kn klPXiPllXXj X ( )()( )()kmilljlpn pnk系统在系统在n 时从状态时从状态i的出发的出发(chf),经过经过k+m步转移步转移,于于n+k+m时到达状态时到达状态j,可以先在可以先在n时从状态时从状态i出发出发(chf)，经过，经过

23、k步转移于步转移于n+k时到达某种中间状态时到达某种中间状态l,再在再在n+k时从中间状态时从中间状态l出发出发(chf)经过经过m步转移于步转移于n+k+m时到达最终状态时到达最终状态j,而中间状态而中间状态l要取遍整个状态空间要取遍整个状态空间S.C-K方程方程(fngchng)的直观意义：的直观意义：第26页/共44页第二十六页，共44页。定理定理 马尔可夫链的马尔可夫链的k 步转移概率由步转移概率由其一步转移概率其一步转移概率 所完全所完全(wnqun)确定确定.若取若取m=1,则由则由C-K方程的矩阵方程的矩阵(j zhn)形式形式:)()()()()()(knnnmkmkPPP得得

24、(1)( )(1)( )( )()kknnnkPPP(1)( )(1)()knnknkPPP( )(1)(1)()nnnknkPPPP分量分量(fn ling)形式形式11 212(1)( )( )(1)()kkkijijj jj jjjjpnpnpnpnk ( ,0)n k ( ,0, ,)n ki jS第27页/共44页第二十七页，共44页。齐次马尔可夫链齐次马尔可夫链为方便，一般为方便，一般(ybn)假定时间起点为零即假定时间起点为零即对齐次马尔可夫链，对齐次马尔可夫链，k步转移概率也与起始步转移概率也与起始时刻时刻n无关记为无关记为( )kijp( )0(),0kijkpP Xj Xi

25、i jS k相应相应(xingyng)的的k步与一步转移概率矩阵分别记为步与一步转移概率矩阵分别记为(k)PP与第28页/共44页第二十八页，共44页。例：设例：设Xn, n0是描述天气变化是描述天气变化(binhu)的齐次马尔科夫链，状态空间为的齐次马尔科夫链，状态空间为S=0,1,其中其中0,1分别表示有雨和无雨，分别表示有雨和无雨，X的一步转移概率矩阵为的一步转移概率矩阵为0.70.30.40.6P试对任意的试对任意的i, jS,计算三步转移计算三步转移(zhuny)概率概率(3)ijp20.610.390.520.48P320.5830.4170.5560.444PPP第29页/共44

26、页第二十九页，共44页。1）初始）初始(ch sh)分布分布(0)0(),iqP XiiS称为马尔可夫链的初始为马尔可夫链的初始(ch sh)分布分布3.马尔可夫链马尔可夫链 的分布的分布0,nXn称称 第第i个分量为个分量为)0(iq的的(行行)向量向量)0(q为马尔可夫链为马尔可夫链的的初始分布向量初始分布向量. 即即)()0()0(iqq2）有限）有限(yuxin)维分布维分布定理定理 马尔可夫链马尔可夫链0,nXn的的有限维分布有限维分布由其由其初始初始分布分布和和一步转移概率一步转移概率所完全确定所完全确定.证明证明12121, 0, , , ,nnnttt i ii iS 对第30

27、页/共44页第三十页，共44页。1212,ntttnP Xi XiXi12120,(),ntnittPXi XiXiiX12201,(),nttitnPXi XXiiXi12012(,)ntttniPXi XiXiXi121110200,()()()tttiXiXiPP XXiiP XiXi11110(,)nntnttnXiP XiXiXi12100121()()()tttiXiXiPP XiP Xi Xi11()nntntnP Xi Xi112111 21(0)11(0)( )().nninntttttiii iiiniqpptpt第31页/共44页第三十一页，共44页。又因为马尔可夫链的又

28、因为马尔可夫链的k步转移步转移(zhuny)概率由一步转移概率由一步转移(zhuny)概率所概率所完全确定完全确定.所以马尔可夫链的有限所以马尔可夫链的有限(yuxin)维分布由其初始分布和维分布由其初始分布和一步转移概率所完全确定一步转移概率所完全确定.第32页/共44页第三十二页，共44页。3）绝对）绝对(judu)分布分布( )(),0,njnqP XjnjS称为马尔可夫链为马尔可夫链 的的绝对分布绝对分布0,nXn称称 第第j个分量为个分量为)(njq的的(行行)向量向量)0(q为马尔可夫链为马尔可夫链0,nXn的的绝对分布向量绝对分布向量. 即即)()()(njnqq绝对分布绝对分布

29、(fnb)、初始分布、初始分布(fnb)和和n步转移概率有如下关系：步转移概率有如下关系：( )(0)( )(0)0, ,nnjiijiqqpni jS或矩阵或矩阵(j zhn)形式形式)0()()0()(nnPqq第33页/共44页第三十三页，共44页。( )()njnqP Xj(0)( )(0)0, ,niijiqpni jS0(),)niPXiXj0(,)niPXi Xj0(,)niP Xi Xj00()()niP XiP Xj Xi第34页/共44页第三十四页，共44页。( )( )(0)(1),0;(2),0;(3) ,0kkkknkkXnPPqqP的有限的有限(yuxin)维分布由

30、其初始分布和一维分布由其初始分布和一步转移步转移(zhuny)概率所完全确定概率所完全确定齐次马氏链有相应齐次马氏链有相应(xingyng)的结果的结果第35页/共44页第三十五页，共44页。例例 设0,nXn是具有三个状态0，1，2的齐次马尔可夫链，其一步转移概率矩阵为3104411142431044P初始分布初始分布, 2 , 1 , 0,31)0(iqi试求：022(1) (0,1);(2) (1).P XXP X第36页/共44页第三十六页，共44页。解解020201(0,1)(0(10)P XXP XP XX（）)(2)0113p(2)01p其中为一个两步转移概率，在两步转移概率矩阵

31、中是第一行第二列的元素.22PP（ ）5181 65131 621 63911 611 6645(2)01516p02(0,1)P XX1553 1648第37页/共44页第三十七页，共44页。(0)(2)21(2)(1)iiiP Xqp(2)(2)(2)0111211()3ppp1 519()3 162161124第38页/共44页第三十八页，共44页。例：如果例：如果(rgu)将社会家庭中个体的收入分为低收入、中等收入和高收入三个等级，则早在将社会家庭中个体的收入分为低收入、中等收入和高收入三个等级，则早在20世纪世纪50年代，社会学研究者发现个体收入的等级在很大程度上取决于其父代收入的等

32、级。如果年代，社会学研究者发现个体收入的等级在很大程度上取决于其父代收入的等级。如果(rgu)令令Xn表示一个家庭第表示一个家庭第n代个体的收入等级，并用代个体的收入等级，并用1,2,3分别表示低收入，中等收入和高收入，则一个家庭中相继的后代收入等级的变化可以用其次马尔科夫链来描述，状态空间为分别表示低收入，中等收入和高收入，则一个家庭中相继的后代收入等级的变化可以用其次马尔科夫链来描述，状态空间为S=1,2,3，并且有以下的转移的概率矩阵，并且有以下的转移的概率矩阵0.650.280.070.150.670.180.120.360.52P第39页/共44页第三十九页，共44页。如果当前收入等级为如果当前收入等级为3，试分析，试分析(fnx)经过三代后个体收入等级转变为经过三代后个体收入等级转变为2的可能性，进一步分析的可能性，进一步分析(fnx)经过经过n代后个体收入等级的概率分布，并具体计算代后个体收入等级的概率分布，并具体计算n=10时个体收入等级的概率分布。时个体收入等级的概率分布。(