概率统计和随机过程课件第十三章 马尔可夫链

第十三章马尔可夫链马尔可夫过程是一类特殊的随机过程,最初是由俄国数学家马尔可夫1896年生物学,经济,管理,教育,气象物理,化学等等.马尔可夫链是离散状态的马尔可夫过程,提出和研究的应用十分广泛,其应用领域涉及计算机,通信,自动.控制,随机服务,可靠性,1例：一维随机游动一个质点在直线上的五个位置:0,1,2,3,4做随机游动.当它处在位置1或2或3时,以的1/3概率向左移动一步而以2/3的概率向右移动一步;当它到达位置0时,以概率1返回位置1;当它到达位置4时以概率1停留在该位置上(称位置0为反射壁,称位置4为吸收壁).20123412/32/32/31/31/31/313第一节:马尔可夫链的定义一．定义1设随机过程的状态空间是}),({TttXS有限集或可列集,对于T内任意n+1个参数和内任意个状态121nnttttS1n,,,,,121nnjjjj如果条件概率})(,,)(,)(|)({221111nnnnjtXjtXjtXjtXP})(|)({11nnnnjtXjtXP(13.1)5恒成立,则称此过程为马尔可夫链.式(13.1)称为马尔可夫性,或称无后效性.马氏性的直观含义可以解释如下:将看作为现在时刻,那末,就是过去时nt121,,,nttt刻,而则是将来时刻.于是,(13.1)式是说,当已知1nt注：并不需要间隔相等，比如121,,,nttt其中121212,,,,kmnmnkmnkttttttnnn6系统现时情况的条件下,系统将来的发展变化与系统的过去无关.我们称之为无后效性.许多实际问题都具有这种无后效性.例如生物基因遗传从这一代到下一代的转移中仅依赖于这一代而与以往各代无关.1111{()|(),,()}kkkkmnmnmnmnmnmnPXtjXtjXtj11{()|()}kkkkmnmnmnmnPXtjXtj7二马尔可夫链的分类状态空间是离散的(有限集或可列集),参数集ST可为离散或连续的两类.三离散参数马尔可夫链（1）转移概率定义2在离散参数马尔可夫链},,,,,),({210nttttttX中,条件概率称为在)(})(|)({1mijmmtpitXjtXP)(tX8时刻(参数)由状态一步转移到状态的一步转移mtij概率,简称转移概率.条件概率称为在时)(})(|)({)(mnijmnmtpitXjtXP)(tX刻(参数)由状态经步转移到状态的步mtinjn转移概率.9n(2)转移概率的性质:对于状态空间内的任意两个S状态和,恒有ij(1)0)()(mnijtp(2),1)()(mSjnijtp,2,1n)()(mSjnijtp})(|)({itXjtXPmnmSj})({})(,)({itXPitXjtXPmSjmnm({()}){()}{()}mnmjSmPXtjXtiPXti1})({})({itXPitXPmm10四.离散参数齐次马尔可夫链定义3在离散参数马尔可夫链},,,,,),({210nttttttX中,如果一步转移概率不依赖于参数,即)(mijtpmt对任意两个不等的参数和,有mtktkm)(})(|)({1mijmmtpitXjtXPijkijkkptpitXjtXP)(})(|)({1则称此马尔可夫链具有齐次性或时齐性,称)(tX为离散参数齐次马尔可夫链.11例1：Bernoulli序列是离散参数齐次马尔可夫链.第二节参数离散的齐次马尔可夫链对离散参数齐次马尔可夫链,本节讨论以下四个问题.一转移概率矩阵设是齐次马尔可夫链,由于状},,,,,),({210nttttttX态空间是离散的(有限集或可列集),不妨设其状态S空间.},,,2,1,0{nS12则对内的任意两个状态和,由转移概率排序ijijp一个矩阵000101011101jjiiijppppppPppp称为(一步)转移概率矩阵})(|)({1itXjtXPpmmijn步概率转移矩阵()(),nnijijSPp13转移概率矩阵的性质：(1),即元素均非负;0ijp(2),即每行和为1.1Sjijp具有以上两个特点的方阵称为随机矩阵.转移概率矩阵就是一个随机矩阵.例1Bernoulli序列的状态空间,转移概率矩阵}1,0{S})(|)({1itXjtXPpmmij1,0,})({1jpjqjtXPm14例2：一维随机游动一个质点在直线上的五个位置:0,1,2,3,4做随机游动.当它处在位置1或2或3时,以的1/3概率向左移动一步而以2/3的概率向右移动一步;当它到达位置0时,以概率1返回位置1;当它到达位置4时以概率1停留在该位置上(称位置0为反射壁,称位置4为吸收壁).00011011ppqpPppqp150123412/32/32/31/31/31/31161000000120003312000331203300001P17二切普曼-柯尔莫哥洛夫方程定理一设是马尔可夫链,则有},,,,,),({210nttttttX)()()()()()(nmlkjkmnikmlnijtptptp(13.6)称为切普曼-柯尔莫哥洛夫方程.()()(()|())((),()|())ijnlmmnlmmnlmnmkPtPXtjXtiPXtjXtkXti证明：18(()|())(()|())mnlmnkmnmPXtjXtkPXtkXti()()()()ikkjnlmmnkPtPt据马尔科夫性(()|(),())(()|())mnlmmnkmnmPXtjXtiXtkPXtkXti19如果马尔可夫链具有齐次性,那么切普曼-柯尔莫哥洛夫方程化为即()()()()()(),nlnlnlnlijikkjkpppPPP进一步改写为矩阵形式(2)2PP其中是两步转移概率矩阵,是一步转移)()2()2(ijpPPkjkikijppp)2(1,1ln当时,得到20用数学归纳法可得nnPP)(,4,3,2n(13.8)因此，也常把作为步转移概率矩阵的符号。nPn这表明:n步转移概率矩阵()()()nnijPp等于一步转移概率矩阵P的n次幂.21例5传输数字0和1的通讯系统,每个数字的传输需经过若干步骤,设每步传输正确的概率为9/10,传输错误的概率为1/10,问:(1)数字1经三步传输出1的概率是多少?(2)若某步传输出数字1,那么又接连两步都传输出1的概率是多少?22设表示第步输出数字，则是一齐次马氏链，状态空间，一步转移概率矩阵{,0,1,2}{01},nnXnXnS291821810101001001918821010100100PP解：2312121(1,1|1)(1|1)(1|1,1)nnnnnnnnPXXXPXXPXXX1211111(1|1)(1|1)0.81nnnnPXXPXXpp1(3)()11110.218182907561001010010kkkppp24三.有限维概率分布称为初始分布.马尔可夫链在初始时刻的概率},,,),({210tttttX0t},)({)(00jtXPtpj,2,1,0j分布:初始分布与转移概率完全地确定了马尔可夫链的任何有限维分布.不妨设齐次马尔可夫链的参数集和状态空间都是非负整数集,那么有如下定理。25定理二设齐次马尔可夫链的状态},2,1,0),({nnX空间则对任意个非负整数},,,,2,1,0{iSnnkkk21和内的任意个状态Sn,,,,21njjj有})(,,)(,)({2211nnjkXjkXjkXP)()()(011122111)0(nnnnkkjjkkjjkijiipppp(13.9)112211220{(),(),,()}{(0),(),(),,()}nnnniPXkjXkjXkjPXiXkjXkjXkj证明：26例6在本节例5中,设初始时输入0和1的概率分别为1/3和2/3,求第2、3、6步都传输出1的概率.由题知0112(0)(0)33pp1(2)(3)236111110{1,1,1}(0)iiiPXXXpppp1(3)(2)111110((0))0.4128iiipppp解:2728马尔可夫链在任何时刻的一维概率分布nt(){()},jnnptPXtj,2,1,0j又称为绝对概率,或称为瞬时概率.事实上，由(13.9)或全概率公式，对于齐次马尔科夫链，有,)()(0)(0inijinjptptp,2,1,0j(13.11)式中是初始时刻.0t式(13.11)表明:齐次马尔可夫链在时刻的瞬时概率完全地由初始分布和步转移概率所确定.n写成向量形式得)),(,),(),((10njnntptptp)(00100)),(,),(),((njPtptptp步转移概率矩阵nnnijnPpP)()()(29nt例7本节例2中,设质点在初始时刻恰处在状态2,0t试求在时刻,质点处在各个状态的概率.2t212000335400099144009991220099300001P3000102030404(2)(2)2021(),(),(),(),()(0,0,1,0,0)()()0,1,2,3,4jiijjiptptptptptptptppj2144(),0,,0,,9990,1,2,3,4jptj据题意31四.平稳分布如果一维分布与无关,那么据)(njtpnt定义4对于齐次马尔可夫链如果},,,,),({210tttttX存在概率分布满足,jp,2,1,0j,0iijijppp,2,1,0j(13.12)则称为平稳分布,称具有平稳性,,jp),2,1,0(j)(tX是平稳齐次马尔可夫链.,)()(01iijninjptptp,2,1,0j(13.10)作如下定义：32改写成向量:平稳分布律要满足定理：如果齐次马尔可夫链的初},,,),({210tttttX始分布},)({)(00jtXPtpj),2,1,0(j是一个平稳分布,则0(){()}(),jnnjptPXtjpt,2,1,0j),2,1(n),,,,,(210jppppPppppj),,,,,(210并且有10jjp33例8带一个反射壁的一维随机游动,以表示jtXn)(在时刻粒子处于状态,状态空间ntj},,,2,1,0{jS转移概率,00qp1qpppjj1,),2,1,0(jqpjj1,),3,2,1(j求平稳分布,2,1,0,jpj平稳分布满足方程组jp解：35),,,,,(210jppppPppppj),,,,,(210并且有10jjp