第六章 马尔可夫链

Markov过程安德雷.安德耶维奇.马尔可夫(A.A.Markov):俄数学家，1856~1922概率和统计领域专家。当年Markov研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了Markov过程的数学模型Markov过程80年代兴起，在现代工程、自然科学、社会科学中应用广泛。2020/3/9Markov过程1．马尔可夫性通俗地说，就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，则称}),({TttX具有马尔可夫（Markov)性。定义设}),({TttX是一个随机过程，如果}),({TttX在t0时刻所处的状态为已知，它在时刻0tt所处状态的条件分布与其在t0之前所处的状态无关。0tt现在0tt将来0tt过去2.马尔可夫过程定义设}),({TttX的状态空间为S,122,,nntttT如果对(),,1,2,,1iiiXtxxSin在条件下)(ntX的条件分布函数恰好等于11()nnXtx在条件下的条件分布函数,即11221111(),(),,()(()((,))())nnnnnnnnnPXtxPXtxXtxXtxXtxXRtxx{(),}XttT马尔则称为可夫过程.3.马尔可夫链定义参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。注只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为12122,,,,,,nnntttTiiiS对11111122()(),((())(()()),),,nnnnnnnnnPXtiPXtixXtiXtiRXtiXti有2020/3/97时间离散状态离散的马尔科夫链时间离散状态连续的马尔科夫序列时间连续状态连续的马尔科夫过程时间连续状态离散的马尔科夫过程Markov过程8/32第六章Markov链第一节基本概念第二节Markov链的状态分类及性质第三节极限定理及平稳分布第四节Markov链的应用9/32第六章Markov链第一节基本概念1.转移概率２.Chapman-kolmogorov方程3.Markov链的分布4.齐次Markov链５.Markov链举例1.转移概率定义设}0,{nXn是马尔可夫链,称条件概率{,0}nXnni(它表示系统在时处于状态的条件下经过k步转移,于n+k时到达状态j的条件概率).()()(,,,0,)1kijnknpnPXjXijSnik{,0}nXn为在n时的k步转移概率.()()kijipnj称以为第行底列元素的矩阵))(()()()(npnkijkP{,0}nXn为系统在n时的k步转移概率矩阵.第一节基本概念()()ijnpnP记为特别当k=1时，(1)()ijnpn为系统在时的一步转移概率,(1)(1)()(())ijnpnP为系统的一步转移概率矩阵()ijpn记为第一节基本概念1.转移概率定义称可数维的矩阵)(ijpP为随机矩阵，如果0,(,)1,()ijijjpijpi显然，}0,{nXn在n时的k步转移概率矩阵)()(nkP是一随机矩阵.特别k＝０时，约定(0)1,,,00ijijijpijSnij(0)()I.Pn此时为单位矩阵第一节基本概念1.转移概率２.Chapman-kolmogorov方程定理(C-K方程)()()()()()(),,,0,,kmkmijilljlpnpnpnknmkijS或矩阵形式)()()()()()(knnnmkmkPPP（解决了k步转移概率与一步转移概率间的关系）证明()(){)kmijnkmnpnPXjXi{,())nkmnlnkPXjliXX,){()nkmnnklPXjXliX,)()nkmnnlkPXjXiXl第一节基本概念２.Chapman-kolmogorov方程定理(C-K方程)()()()()()(),,,0,,kmkmijilljlpnpnpnknmkijS或矩阵形式)()()()()()(knnnmkmkPPP（解决了k步转移概率与一步转移概率间的关系）证明,)()nkmnnlkPXjXiXl第一节基本概念)(,)(nnkmnnnklkPXiPXjXXlXil)(()nnkmnknklPXiPllXXjX()()()()kmilljlpnpnk系统在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方程的直观意义：２.Chapman-kolmogorov方程第一节基本概念若取m=1,则由C-K方程的矩阵形式:)()()()()()(knnnmkmkPPP得(1)()(1)()()()kknnnkPPP(1)()(1)()knnknkPPP()(1)(1)()nnnknkPPPP分量形式11212(1)()()(1)()kkkijijjjjjjjjpnpnpnpnk(,0)nk(,0,,)nkijS２.Chapman-kolmogorov方程第一节基本概念定理马尔可夫链的k步转移概率由其一步转移概率所完全确定.２.Chapman-kolmogorov方程第一节基本概念1）初始分布(0)0(),iqPXiiS称为马尔可夫链的初始分布3.马尔可夫链的分布}0,{nXn称第i个分量为)0(iq的(行)向量)0(q为马尔可夫链的初始分布向量.即)()0()0(iqq第一节基本概念2）有限维分布定理马尔可夫链}0,{nXn的有限维分布由其初始分布和一步转移概率所完全确定.证明12121,0,,,,,nnntttiiiiS对3.马尔可夫链的分布}0,{nXn第一节基本概念1212{,,,}ntttnPXiXiXi12120{,}(),,,ntnittPXiXiXiiX12201{,,(}),,nttitnPXiXXiiXi12012(,,,,)ntttniPXiXiXiXi121110200,()()()tttiXiXiPPXXiiPXiXi11110(,,,)nntnttnXiPXiXiXi12100121()()()tttiXiXiPPXiPXiXi11()nntntnPXiXi11211121(0)11(0)()().nninntttttiiiiiiniqpptpt2）有限维分布3.马尔可夫链的分布}0,{nXn第一节基本概念又因为马尔可夫链的k步转移概率由一步转移概率所完全确定.所以马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定.3.马尔可夫链的分布}0,{nXn第一节基本概念2）有限维分布3）绝对分布()(),0,njnqPXjnjS称为马尔可夫链的绝对分布}0,{nXn称第j个分量为)(njq的(行)向量)0(q为马尔可夫链}0,{nXn的绝对分布向量.即)()()(njnqq绝对分布、初始分布和n步转移概率有如下关系：()(0)()(0)0,,nnjiijiqqpnijS或矩阵形式)0()()0()(nnPqq3.马尔可夫链的分布}0,{nXn第一节基本概念()()njnqPXj(0)()(0)0,,niijiqpnijS0((),)niPXiXj0((,)niPXiXj0(,)niPXiXj00()()niPXiPXjXi3）绝对分布3.马尔可夫链的分布}0,{nXn第一节基本概念4.齐次马尔可夫链定义{,0}nXn设是一马尔可夫链,如果其一步转移概率)(npij恒与起始时刻n无关，记为ijp{,0}nXn则称为齐次(时间其次或时齐)马尔可夫链.否则，称为非齐次马尔可夫链.显然对齐次马尔可夫链，k步转移概率也与起始时刻n无关．记为()kijp第一节基本概念为方便，一般假定时间起点为零．即()0(),,0kijkpPXjXiijSk相应的k步与一步转移概率矩阵分别记为(k)PP与定理()()(0)(1),0;(2),0;(3){,0}kkkknkkXnPPqqP的有限维分布由其初始分布和一步转移概率所完全确定4.齐次马尔可夫链第一节基本概念例１(天气预报问题)如果明天是否有雨仅与今天的天气(是否有雨)有关，而与过去的天气无关.并设今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为b，又假设有雨称为0状态天气，无雨称为1状态天气.Xn表示时刻n时的天气状态，则}0,{nXn是以}1,0{S为状态空间的齐次马尔可夫链.其一步转移概率矩阵为bbaa11P５.马尔可夫链举例第一节基本概念例2(有限制随机游动问题)设质点只能在{0，1，2，···，a}中的各点上作随机游动，移动规则如下：1{1,2,,1}ia（）移动前处;1,0,,rqprqp0000,0,1prprii+1i-1pqr010p0r20i（）移动前处3ia（）移动前处a-1aqaar,0,1aaaaqrqr第一节基本概念５.马尔可夫链举例设Xn表示质点在n时刻所处的位置，则其一步转移概率矩阵为{,0}{0,1,,}nXnSa是以为状态空间的齐次马尔可夫链.aarqprqprqprqpr000000000000000000000000P例2(有限制随机游动问题)第一节基本概念５.马尔可夫链举例设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的球.{,0}nXn是以},,1,0{mS为状态空间的齐次马尔可夫链.设经过n次摸换,坛中黑球数为Xn,则例3(坛子放回摸球问题)第一节基本概念５.马尔可夫链举例其一步转移概率矩阵为01000001010000000202000001010000010mmmmmmmmmP例3(坛子放回摸球问题)第一节基本概念５.马尔可夫链举例甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局。甲赢的概率为p，乙赢的概率为q=1-p，求甲输光的概率。解状态空间I={0,1,2,,c}，c=a+bqpa-1aa+10a+b第一节基本概念５.马尔可夫链举例例4(赌徒输光问题)设ui表示甲从状态i出发转移到状态0的概率，求ua显然u0=1，uc=0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率)ui=pui+1+qui-1(i=1,2,,c-1)（甲在状态i下输光：甲赢一局后输光或甲输一局后输光）第一节基本概念５.马尔可夫链举例例4(赌徒输光问题)1,,2,1)()()()(111111ciuupquuuuquupqupuuqpiiiiiiiiiii第一节基本概念第一节基本概念５.马尔可夫链举例例4(赌徒输光问题)ˆ21,1(1)012111uuuuuuuuqppqiiiiii即第一节基本概念第一节基本概念５.马尔可夫链举例例4(赌徒输光问题)baaubabcauciiuccuiiuuiuuiuuuuuuuubaiciiiiiiii同理可得即,111101)1(1)1()1()1()()()()(0