马尔可夫过程

1、Markov过程过程第一节第一节 基本概念基本概念第二节第二节 MarkovMarkov链的状态分类及性质链的状态分类及性质第三节第三节 极限定理及平稳分布极限定理及平稳分布 安德雷安德雷. .安德耶维奇安德耶维奇. .马尔可夫马尔可夫 (A.A.Markov): 俄数学家，俄数学家，18561922 概率和统计领域专家。概率和统计领域专家。 当年当年MarkovMarkov研究普希金诗歌里元音字母和辅音字母研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了交替出现的规律时提出了MarkovMarkov过程的数学模型过程的数学模型. . MarkovMarkov过程过程8080年代兴起，

2、在现代工程、自然科学、年代兴起，在现代工程、自然科学、社会科学中应用广泛。社会科学中应用广泛。Markov过程过程n例：例：A： 过红绿灯过红绿灯 红灯停红灯停 绿灯行绿灯行B：下棋：下棋 当前棋局当前棋局 棋风棋风下一步的招法下一步的招法n将来的选择将来的选择不仅与不仅与目前的状态目前的状态有关，还和该过有关，还和该过程的程的过去状态过去状态有关。有关。第一节第一节 基本概念基本概念n根据当前过程的概率分布而计算未来时刻的概率根据当前过程的概率分布而计算未来时刻的概率分布。分布。1. 1. 马尔可夫过程概念马尔可夫过程概念所所处处的的状状态态为为已已知知的的在在时时刻刻系系统统过过程程或或0

3、)(t所所处处状状态态的的条条件件分分布布与与过过程程在在时时刻刻条条件件下下0,tt 特特性性称称为为之之前前所所处处的的状状态态无无关关的的与与过过程程在在时时刻刻0t马尔可夫性马尔可夫性. .具有马尔可夫性的随机过程称为具有马尔可夫性的随机过程称为马尔可夫过程马尔可夫过程. .即即: : 过程过程“将来将来”的情况与的情况与“过去过去”的情况是无的情况是无关的，和关的，和现在现在有关有关直线上的随机游动直线上的随机游动 布朗运动布朗运动用分布函数表述马尔可夫过程用分布函数表述马尔可夫过程,),(:的的状状态态空空间间随随机机过过程程设设TttXI ,个个数数值值的的任任意意如如果果对对时

4、时间间nt, 3,21Ttntttin 恰有恰有)(,)(,)(|)(112211 nnnnxtXxtXxtXxtXP ,)(|)(11RxxtXxtXPnnnnn 2021-7-86 时间时间离散离散状态状态离散离散的的马尔科夫链马尔科夫链 时间时间离散离散状态状态连续连续的马尔科夫序列的马尔科夫序列 时间时间连续连续状态状态连续连续的马尔科夫过程的马尔科夫过程 时间时间连续连续状态状态离散离散的（的（连续时间的连续时间的） 马尔科夫链马尔科夫链MarkovMarkov过程过程n马尔可夫链马尔可夫链一、一、MarkovMarkov链的定义链的定义设随机过程)(tX,Tt ，若对任一时刻 n，

5、以及任意状态jiiiin,110，有,) 1(,)(|) 1(1ninXinXjnXP) 0 (,) 1 (,01iXiX)(|) 1(inXjnXP转移概率转移概率np pij ij(n) (n) 不仅与状态不仅与状态 i i , j , j 有关，而且与时刻有关，而且与时刻 n n 有关。有关。n当当 p pij ij(n) (n) 与时刻与时刻 n n 无关时，无关时，则称则称马尔可夫链马尔可夫链是齐次是齐次的，并记为的，并记为 p pij (n)ij (n) 为为 p pij ij 。称称条件概率条件概率为马尔可夫链为马尔可夫链 X Xn n , , n n T T 在时刻在时刻 n

6、n 的的一步转移概率一步转移概率，其中其中 i i , , j j I I ，简称为，简称为转移概率转移概率。 )(1iXjXPnpnnij一步转移概率矩阵一步转移概率矩阵性质：性质：nnpppppp2222111211PIipIjipIjijij , 1 )2(, , 0 )1 (n n 步转移概率步转移概率称称条件概率条件概率为齐次马尔可夫链为齐次马尔可夫链 X Xn n , , n n T T 的的 n n 步转移概率步转移概率，并，并称称为马尔可夫链为马尔可夫链 的的 n n 步转移矩阵步转移矩阵。) 1 , 0 ,( ,)(nmIjiiXjXPpmnmnij)()(nijnpP规定：

7、规定：jijipij , 1 , 0)0( ,)ijP m mn非齐次非齐次n n步转移概率如何表示？步转移概率如何表示？马尔可夫链的马尔可夫链的统计特性统计特性完全由完全由一步转移概率一步转移概率和和初始分布初始分布决定决定：001100111100111111001111111122110000, , nnnnnnnnnnnnnnnnnnnnnnP XiXiXiP Xi XiXiXiP XiXiXiP Xi XiP XiXiXiP Xi XiP XiXiP Xi XiP Xi一步转移概率的重要性一步转移概率的重要性, 0)0(,0),( XttX且且是是独独立立增增量量过过程程设设.0),

8、(是是一一个个马马尔尔可可夫夫过过程程证证明明 ttX性质性质泊松过程是时间连续状态离散的马氏过程泊松过程是时间连续状态离散的马氏过程; ;马尔可夫链的几个简单例子马尔可夫链的几个简单例子二进制对称信道模型二进制对称信道模型离散无记忆离散无记忆信道模型。信道模型。假设某级信道输入假设某级信道输入0, 10, 1数字信号后，其数字信号后，其输出正确的概率为输出正确的概率为p p，产生错误的概，产生错误的概率为率为q q，则该级信道输入状态和输出，则该级信道输入状态和输出状态构成一个状态构成一个两状态的齐次马尔可夫两状态的齐次马尔可夫链链。0011ppqq一步转移概率矩阵一步转移概率矩阵：) 1

9、, 0,( , ,jijiqjippijpqqpP二步转移概率矩阵二步转移概率矩阵：22222)2(22qppqpqqpPP具有吸收壁和反射壁的随机游动具有吸收壁和反射壁的随机游动设一质点在线段设一质点在线段1，5 上随机游动，状态空间上随机游动，状态空间I=1，2，3，4，5，每秒钟发生一次随机游动，移动的规则是：，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在）若移动前在2，3，4处，则均以概率处，则均以概率1/3向左向左 或向右移动一单位，或停留在原处；或向右移动一单位，或停留在原处；（2）若移动前在）若移动前在1处，则以概率处，则以概率1移到移到2处；处；（3）若移动前在）若移

10、动前在5处，则以概率处，则以概率1移到移到4处。处。用nX表示在时刻n质点的位置，则nX，0n是一个有限齐次马氏链，试写出一步转移矩阵试写出一步转移矩阵.分分析析555453525145444342413534333231252423222115141312111pppppppppppppppppppppppppP01000313131000313131000313131000101P故故12345其一步转其一步转移矩阵为移矩阵为10000210210002102100021021000011P若将移动规则改为若将移动规则改为（1）若移动前在）若移动前在2，3，4处，则均以概率处，则均以概率1

11、/2向左或向右向左或向右 移动一单位；移动一单位；（2）若移动前在）若移动前在1，5处，则以概率处，则以概率1停留在原处。停留在原处。因为质点在因为质点在1，5两点被两点被“吸收吸收”，故称故称有两个吸收壁的随机游动有两个吸收壁的随机游动设设 X Xn n , , n n T T 是一个马尔可夫链，其状态空间是一个马尔可夫链，其状态空间 I I = = a a, , b b, , c c ，转移矩阵为转移矩阵为05/25/33/103/24/14/12/1P求：求： )2(;, ) 1 (204321bXcXPcXcXaXcXbXPnn, ) 1 (04321cXcXaXcXbXP/ 0001

12、122334cXPcXPcXbXPbXcXPcXaXPaXcXPcbbccaacPPPP50152315341/,043210cXPcXaXcXbXcXP05/25/33/103/24/14/12/1P解： )2(2bXcXPnn二步转移概率矩阵：二步转移概率矩阵：901720330176110315824540930172)2(PP61)2(bcP甲有赌资甲有赌资a元，乙有赌资元，乙有赌资b元，赌一局输者给赢元，赌一局输者给赢者者1元，无和局。甲赢的概率为元，无和局。甲赢的概率为p，乙赢的概，乙赢的概率为率为q=1- -p，求甲，求甲输光的输光的概率。概率。解解 状态空间状态空间I=0,1,

13、2,c，c=a+bq pa- -1 a a+10 a+b (赌徒输光问题赌徒输光问题) 设设ui表示甲从状态表示甲从状态i出发转移到状态出发转移到状态0的的概率，求概率，求ua 显然显然u0 =1，uc =0(u0表示已知表示已知甲输光甲输光情形情形下甲输光的概率，下甲输光的概率，uc表示已知表示已知乙输光乙输光情情形下甲输光的概率形下甲输光的概率) ui =pui+1 + qui-1 (i=1,2,c-1)（甲在状态（甲在状态i下输光：甲赢一局后输光或甲下输光：甲赢一局后输光或甲输一局后输光）输一局后输光） (赌徒输光问题赌徒输光问题) 1, 2 , 1)()()()(111111ciuup

14、quuuuquupqupuuqpiiiiiiiiiii 21, 1 (1)012111uuuuuuuuqppqiiiiii即即 baaubabcauciiuccuiiuuiuuiuuuuuuuubaiciiiiiiii同同理理可可得得即即,111101) 1(1) 1() 1() 1()( )()()(0101012111 rrruuuruuruuuuruurpqqppqckckiiiickikciiii1) 1( )()()(, 1 (2)10111111设设即即 ccbcbbccacaacckckkcccrrrrrruurrrrrruurrrrrruurrurrruuuk11) 1(11)

15、 1(11) 1(1111) 1(0,1111010从而从而则则令令二、基本性质二、基本性质性质性质1 1设0, nXn为马氏链，其状态空间为I，表明表明若已知现在，则过去与未来是独立的。若已知现在，则过去与未来是独立的。若nrs0，则在rriX的条件下，有|,rrssnniXiXiXP=|rrnniXiXP|rrssiXiXP ,|,/|,/|/|nnssrrnnssrrrrnnssrrssrrrrnnrrssrrrrrrnnrrssrrP XiXi XiP XiXi XiP XiP XiXi XiP Xi XiP XiP XiXiP XiXiP XiP XiP XiXiP XiXi证明n

16、步转移概率 的性质)(nijp 定理定理 设设 X Xn n , , n n T T 为马尔可夫链，则对于任意整数为马尔可夫链，则对于任意整数n n ，mm 0, 0, 和和 i i , , j j I I ，n n 步转移概率步转移概率 具有下列性具有下列性质：质：)(nijp (1) nmnmijikkjkIpppIkjkkkikIknijnnpppp112111)( )2()( )(3) mnmnPPPnnPP)( )4(C-K方程方程例例甲、乙两人进行比赛，设每局比赛中甲胜的概率是甲、乙两人进行比赛，设每局比赛中甲胜的概率是p p，乙胜的概率是，乙胜的概率是q q，和局的概率是，和局的

17、概率是r r , ,（ p+q+rp+q+r=1=1）。设每局比赛后，胜者记）。设每局比赛后，胜者记“+1”+1”分，分，负者记负者记“-1”-1”分，和局不记分。当两人中有一人获分，和局不记分。当两人中有一人获得得2 2分结束比赛。以分结束比赛。以 表示比赛至第表示比赛至第n n局时甲获局时甲获得的分数。得的分数。nX（1）写出状态空间；）写出状态空间；（3）问在甲获得）问在甲获得1分的情况下，再赛二局可以结束比分的情况下，再赛二局可以结束比赛的概率是多少？赛的概率是多少？解解（1） 记甲获得记甲获得“负负2分分”为状态为状态1，获得，获得“负负1分分”为状态为状态2，获得，获得“0分分”为

18、状态为状态3，获得获得“正正1分分”为状态为状态4，获得，获得“正正2分分”为为状态状态5，则状态空间为，则状态空间为54321，I一步转移概率矩阵一步转移概率矩阵10000000000000011prqprqprqP（2）二步转移概率矩阵）二步转移概率矩阵 221PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq（3）在2P中)2(45p是在甲得 1 分的情况下经二步转移至 2 分从而结束比赛的概率；)2(41p是在甲得 1 分的情况下经二步转移至2 分（即乙得 2 分）从而结束比赛的概率。所以题中所求概率为)2(45p)2(41p)1

19、 (0)(rprpp绝对概率绝对概率称为马氏链的称为马氏链的绝对分布绝对分布或称或称绝对概率绝对概率计算公式计算公式绝对概率由初始分布和绝对概率由初始分布和n n维转移概率完全确定维转移概率完全确定)(0)()(nijIinpipjp绝对概率绝对概率 pj(n) 的性质的性质定理定理 设设 Xn , n T 为马尔可夫链，则对于任意整数为马尔可夫链，则对于任意整数n 1 和和 j I ，绝对概率，绝对概率 pj (n) 具有下列性质：具有下列性质： ()()(1) ( )0(2) ( )(1)(3) ( )(0)(3) ( )(1)njiijiIjiijiITTnTTpnpppnpnpnnnP

20、PPPPP马氏链状态的极限分布马氏链状态的极限分布n知道了多步转移矩阵，已知初始分布可计算马氏知道了多步转移矩阵，已知初始分布可计算马氏链多步后取某个状态的概率链多步后取某个状态的概率 n如果时间无限长，取某个状态的概率是多少？如果时间无限长，取某个状态的概率是多少？反反射壁问题为例射壁问题为例 随着时间无限长，出现随着时间无限长，出现5 5种状态的种状态的概率趋于稳定。概率趋于稳定。n多步转移概率当步数趋于无穷时的极限问题多步转移概率当步数趋于无穷时的极限问题n如果上述极限存在且和初始状态无关，则马尔可如果上述极限存在且和初始状态无关，则马尔可夫链是遍历的。夫链是遍历的。n只要找到一个正整数

21、只要找到一个正整数mm，使得，使得mm步转移概率矩阵步转移概率矩阵无零元素，则该马氏链就是遍历的无零元素，则该马氏链就是遍历的。10100011100333111 003331110033300010P 反 射 壁110000110002211 00022110002200001P 吸收壁反射壁反射壁 遍历遍历 ；吸收壁；吸收壁非遍历非遍历。计算。计算一个问题：社会学家如何确定社会阶层高职业阶层或较低阶层一个问题：社会学家如何确定社会阶层高职业阶层或较低阶层在社会中的比例？在社会中的比例？马尔可夫极限概率的应用马尔可夫极限概率的应用0010121220.450.480.070.050.70.2

22、50.010.50.490.07 0.620.31PP富中低 1 1 基本概念基本概念2 2 状态类别的划分和判别状态类别的划分和判别3 3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 MarkovMarkov链的状态分类及性质链的状态分类及性质l定义（可达、互通）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系n状态分类的原因状态分类的原因瞬态分析瞬态分析 某一固定时刻的概率特性某一固定时刻的概率特性 n n步转移概率步转移概率 或绝对概率或绝对概率稳态分析稳态分析 n n趋于无穷大时系统的概

23、率特性，这种概趋于无穷大时系统的概率特性，这种概 率特性与状态的关系如何率特性与状态的关系如何需要对状态进行需要对状态进行分类分类 MarkovMarkov链的状态分类链的状态分类一、基本概念一、基本概念1.返回概率返回概率( )0,1,2,1|nijnkfP Xj Xj knXi自状态自状态 i i出发，经过出发，经过n n步首次到达步首次到达状态状态j j 的概率的概率自状态自状态i i出发，经出发，经有限步终于到达有限步终于到达状态状态j j的概率的概率( )1nijijnff返回概率返回概率-自状态自状态i i出发，经有限步终于出发，经有限步终于返返回回状态状态 i i的的概率概率ii

24、f 与 的关系上式可用来求从状态上式可用来求从状态 i 经经 n 步首次到达状态步首次到达状态 j 的概率：的概率：)(nijp)(nijf定理 对任意对任意状态状态 i , j I 及及 1 n 1,1,称称i i是周期的；若是周期的；若d di i = =1,1,称称i i是非周期的。是非周期的。( )gcd :1,0, common dividorniiidn npgreat说明说明1 13.3.周期周期d di i体现系统的发展变化中状态体现系统的发展变化中状态i i重复出现的概率周期。重复出现的概率周期。说明说明2 2若若i i的周期是的周期是d di i，并不是对所有的，并不是对所

25、有的n n满足满足 ()0indiip说明说明3 3( )gcd :1,0niiidn nf例例设设MCMC：0 0，1 1，2 2，3 3，转移概率矩阵如下，转移概率矩阵如下，试求状态试求状态0 0的周期。的周期。001/21/2001/21/21/21/2001/21/200P求下列马尔可夫链的周期求下列马尔可夫链的周期786951112/31/3111111234状态1周期？ 4 6 8 10 。 Gcd=2二、状态类别的划分及判别二、状态类别的划分及判别1 1. .状态类别的划分状态类别的划分状态状态 i iiif非常返态（暂态）非常返态（暂态）常返态常返态零常返态零常返态正常返态正常

26、返态周期周期非周期（遍历态）非周期（遍历态）iiid常返态常返态非常返态非常返态1iif1iif正常返态正常返态零常返态零常返态ii ii iif -有 限 次 返 回 概 率ii 平 均 返 回 时 间状态状态i i再次最终再进入再次最终再进入i i的概率为的概率为1-1-常返态常返态在在有限状态马尔科夫链有限状态马尔科夫链中，一切中，一切常返态都是正常返常返态都是正常返的的常返性的定义常返性的定义称期望值称期望值 为状态为状态 i i 的的平均返回平均返回时间时间。( )1niiinnf若若 f fii ii = 1 = 1，则称状态，则称状态 i i 是是常返常返的；若的；若 f fii

27、 ii 1 1，则，则称状态称状态 i i 是是非常返非常返的。的。若若 i i 0, 0, 使得使得 p pij ij( (n n) ) 0 0 ，则称自状态，则称自状态 i i 可达可达状态状态 j j ，并记为，并记为 i i j j 。（2 2）若）若 i i j j , , 且且 j j i , i , 则称状态则称状态 i i 与状态与状态 j j 互通互通，并记为，并记为 i i j j 。定理1 若若 i j , 且且 j k , 则则 i k 。若若 i j , 且且 j k , 则则 i k 。 定理定理2 2 若若 i i j j , , 则则（1 1）i i 与与 j

28、j 同为同为常返或非常返常返或非常返；（2 2）i i 与与 j j 同为同为正常返或零常返正常返或零常返；（3 3）i i 与与 j j 有有相同的周期相同的周期。传递性互通关系的状态是同一类型例 设马氏链的状态空间设马氏链的状态空间 I = 0, 1, 2, ，其转移概率，其转移概率为为分析状态分析状态0的类型。的类型。,21)1(00f解：Iipppiii ,21 ,21 ,2101,00先考查状态先考查状态0 0，,412121)2(00f,21)(00nnf, 121100nnf可见状态可见状态0 0为为正常返正常返，且，且是非周期是非周期，因而是，因而是遍历遍历的。的。因为因为 i

29、 i 0 0 ，故，故 i i 也是遍历的。也是遍历的。000011112121112100211,21, 1 111111111112,222112nnnnnnnnnnnnnnnnunfnxxxnxnxnxxxxxnxxxun 而令正常返证明：状态空间的分解 定义定义 状态空间状态空间 I I 的子集的子集 C C，若，若对于任意对于任意 i i C C 及及 k k C C 都有都有 p pik ik = 0 = 0 ，则称，则称子集子集 C C 为（随机）为（随机）闭集闭集。若闭集若闭集 C C 的状态互通，则称的状态互通，则称 C C 为为不可约不可约的。的。若马氏链若马氏链 X Xn

30、 n 的状态空间是不可约的，则称该马氏链为的状态空间是不可约的，则称该马氏链为不可约不可约。例 （例（例4.11）设马氏链设马氏链 Xn 的状态空间的状态空间 I = 1, 2, 3, 4, 5 ，转移矩阵为，转移矩阵为P，试分析其闭集及不可约性。，试分析其闭集及不可约性。000100000100100005 . 005 . 005 . 0005 . 0P1/21/21/211/211状态状态 3为吸收态，故为吸收态，故 3 是闭集；是闭集； 1, 4 ， 1, 4, 3 ， 1, 4, 2, 3 都是闭集；都是闭集； 3 和和 1, 4 是不可约闭集；是不可约闭集；因为因为 I 含有（含有（

31、非非不可约的不可约的）闭子集，故马氏链）闭子集，故马氏链 Xn 不不是不可约链。是不可约链。pij(n)的渐近性质与平稳分布是否存在？是否存在？是否与是否与 i 有关？有关？)(limnijnp对于转移概率对于转移概率 pij (n) 的极限的极限（1）pij(n)的渐近性质推论 不可约的有限马氏链必为正常返的。不可约的有限马氏链必为正常返的。有限状态的马氏链，有限状态的马氏链，不可能全是非常返态不可能全是非常返态，也不可能，也不可能含有零常返态；含有零常返态；定理 若若 j 非常返或零常返非常返或零常返，则，则Iipnijn , 0lim)(（2）平稳分布定义 称绝对概率分布称绝对概率分布

32、j , j I 为齐次马氏链的为齐次马氏链的平稳分布，若它满足，若它满足0 , 1 jIiiIiijijpPPTijTip , , 则令平稳分布平稳分布 定理定理 不可约非周期不可约非周期马氏链是马氏链是正常返的正常返的充要条件：存充要条件：存在平稳分布，且此平稳分布就是极限分布在平稳分布，且此平稳分布就是极限分布 ,1 Ijj平均返回时间和平稳分布互为倒数平均返回时间和平稳分布互为倒数例 （例例4.16）设马尔可夫链设马尔可夫链的转移概率矩阵为的转移概率矩阵为P，求马，求马氏链的平稳分布及各状态的平均返回时间。氏链的平稳分布及各状态的平均返回时间。9 . 005. 005. 01 . 08

33、. 01 . 02 . 01 . 07 . 0P解：因为该因为该马氏链是马氏链是不可约的非不可约的非周期周期有有限状态限状态，所以存在平稳分布。所以存在平稳分布。各状态的平均返回时间分别各状态的平均返回时间分别为：为：1 0.90.1 2 . 00.050.8 1 . 00.050.1 7 . 032132133212211平稳分布为：平稳分布为：5882.0 ,2353.0 ,1765.032170.11 ,25.41 ,67.51332211例例 设有状态空间设有状态空间S=0,1,2,3,4,5,6S=0,1,2,3,4,5,6的齐次马尔可夫链，的齐次马尔可夫链， 其一步转移概率矩阵为其

34、一步转移概率矩阵为0.50.50000002/ 31/ 300001/ 302/ 300000000.50.5000000.50.500000001011111117777777P(1)(1)试对试对S S进行分类，并说明各状态类型进行分类，并说明各状态类型(2) (2) 求平稳分布，其平稳分布是否唯一？求平稳分布，其平稳分布是否唯一？121713121712122312501634132312(1) 123SDCCC+=UUU60,1,23,45=UUU不可约闭子集不可约闭子集(2)(2) 由由(1)(1)知知, ,该链有三个不同的正常返不可约闭集该链有三个不同的正常返不可约闭集所以平稳分布不唯一所以平稳分布不唯一三个闭集对应的转移概率矩阵分别为三个闭集对应的转移概率矩阵分别为1122213311233000P骣= 桫112221122P骣=桫()31P =(2) 由由(1)知知,该链有三个不同的正常返不可约闭集该链有三个不同的正常返不可约闭集解方程组解方程组(1)(1)1(1)(1)(1)1231(2)(2)2(2)(