13第四章马尔可夫链

第四章马尔可夫链1.马尔可夫链定义2.一步转移概率及多步转移概率3.初始概率及绝对概率4.Chapman-Kolmogorov（C-K）方程5.遍历的马尔可夫链及平稳分布6.马尔可夫链状态分类时间、状态都是离散的马尔可夫过程，称为马尔可夫链。例如：天气预报质点的随机游动例如：在某数字通信系统中传递0，1两种信号，且传递需要经过若干级。因为系统中有噪声，各级将造成错误，若某级输入0，1信号后，其输出不产生错误的概率为p，产生错误的概率为1-p，则该级的输入输出状态构成了一个两个状态的马氏链。马尔可夫链定义设有随机过程{Xn,n∈T}，若对于任意的整数n∈T和任意的i0,i1,…,in+1∈I，条件概率满足}|{},,,|{11110011nnnnnnnniXiXPiXiXiXiXP则称{Xn,n∈T}为马尔可夫链，简称马氏链将来的状态只与当前状态有关，与过去状态无关为了描述马尔可夫链（n+1）维分布率，最重要的是条件概率P{Xn+1=in+1|Xn=in}.它表示在时刻n取in值的条件下，下一时刻n+1取值为in+1的概率（一步转移概率）定义4.2称条件概率为马尔可夫链{Xn,n∈T}在时刻n的一步转移概率，其中i,j∈I，简称转移概率。}|{)(1iXjXPnpnnij定义4.3若对任意的i,j∈I，马尔可夫链{Xn,n∈T}的转移概率与n无关，则称马尔可夫链是齐次马尔可夫链。我们只讨论齐次马氏链。并将记为()ijpnijp设P表示一步转移概率所组成的矩阵，则nnppppppP2122211211称为系统状态的一步转移概率矩阵，它具有如下性质：1.2.Ijipij,,0IjipIjij,,1满足上述两个性质的矩阵成为随机矩阵定义4.4称条件概率为马尔可夫链{Xn,n∈T}的n步转移概率，并称1,0,,},|{)(nmIjiiXjXPpmnmnij)()()(nijnpP为马尔可夫链的n步转移矩阵。规定(0)0,1,ijijpij()()()11121()()()21222nnnmnnnmpppppp例题设马尔可夫链{Xn,n∈T}有状态空间I={0,1}，其一步转移概率矩阵为11100100ppppP求和两步转移概率矩阵P(2)}0|0{2mmXXP解：(2)m2m00m2mmm2mm2mmmm2m1mmm2m1m1m1mmmm1m1mP{X0,X0}PP{X0|X0}P{X0}P{X0,X0}P{X0,,X0}P{X0}P{XX0,X1P{X0,X0}P{X0,X0}P{X0,X0,X0}P{X0}P{X0,X10},X0}PX{mm1mm1m2m1mm1mm2m1mm1mP{X0}P{X0|X0,X0}P{X0|X0}P{X1,X0}P0|X1,X0}P{X1|X{X1,X0}0}(2)000001(2)20101(2)(2)10111001001111PPPPPPPPPPPPPm2m1m1mm2m1m1m(1)(1)(1)(1)0000100100001001P{X0|X0}P{X0|X0}P{X0|X1}P{X1|X0}=PPPP=PPPPnnPP)(结论：n步转移矩阵)2(P定理4.1设{Xn,n∈T}为马尔可夫链，则对任意整数n≥0，0≤Ln和i,j∈I，n步转移概率具有下列性质：1.2.3.4.Iklnkjliknijppp)()()(IkIkjkkkiknijnnpppp111211)()1()(nnPPPnnPP)(Chapman-Kolmogorov方程(){,}{,}{|}{,}{}{,,}{}{,,}{}{|,}{|{|}{}nijmnmmnmmmnmmmnmlmkImmnmlmmlmmmlmlmkIkmnmlmlIlmPXkXiPXPPXjXiPXjXiPXiPXjXiPXiPXjXkXiPXiPXjXkXiPXjXkXiPXkXikXPkX()()()()|}kInlllnlkjikikkjkmkIIPPPPkXi（1）证明设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动。以Xn表示时刻n质点所处的位置，则{Xn,n∈T}是一个齐次马尔可夫链，求一步和k步转移概率。,1,1,10(ji-1,i+1)iiiiijPpPqpP解：一步转移概率为：...........................q0p00......0q0p0......00q0p...........................P例题：无限制随机游动()kji为偶数()kji为奇数质点在数轴上移动，规律同上例。当质点一旦达到Xn=0时，Xn+1就停留该0状态，这种状态称为吸收态。{Xn,n∈T}是一个齐次马尔可夫链，求一步转移概率。解:000,1,1,10j0i1i10ji1,i-1,i1jiiiiijPPPPPqP例题：带一个吸收壁的随机游动10000..000..000..000..0000.........qpqpPqpq质点在数轴上移动，规律同上例。随机游动的状态空间I={0,1,2…a},其中0和a为吸收态。求一步转移概率。解:000,1,1,10j010j01i11i10ji1,i-1,i1jaaajiiiiijPPPPPPaPqaP例题：带2个吸收壁的随机游动a10000...000...000...00000000......qpqpqpqp..........................0000..0000..0000..0000..000001qpqpqpqp如果明天是否有雨仅与今日是否有雨有关，而与过去的天气无关.并设今日下雨，明日有雨概率为0.7，今日无雨明日有雨的概率为0.4，并把有雨称为0状态，无雨称为1状态。则问：今日有雨且第5日仍有雨的概率为多少？例题：天气预报问题解：设状态0代表有雨，状态1代表无雨，则一步转移矩阵为：00011011PP0.70.3P=PP0.40.64(4)(4)0001(4)40001(4)(4)10111011PP0.57490.4251PPP=P=PP0.56680.4332PP所以今天有雨，第5天有雨的概率为：(4)000.5749P定义：称为n时刻马尔可夫链的绝对概率；称为n时刻的绝对概率向量。)(},{)(IjjXPnpnj12(){(),(),},0TnpnpnnP定义：称为马尔可夫链的初始概率；简记为称为马尔可夫链的初始概率向量。0(0){},()jpPXjjI),,()0(21ppTPjp例题：设马尔可夫链有k个状态，已知第n-1时刻的绝对概率向量为))1(,),1(),1((21npnpnpk求第n时刻绝对概率向量。(1)TnP定理4.2设{Xn,n∈T}为马尔可夫链，则对任意j∈I和n≥1，绝对概率pj(n)具有下列性质：1.2.3.4.Iinijijppnp)()(Iiijijpnpnp)1()()()0()(nTTnPPPPPP)1()(nnTT证明定理4.3设{Xn,n∈T}为马尔可夫链，则对任意i1,…,in∈I和n≥1，有IiiiiiinnnnpppiXiXP11},,{11证明11101110111011011{,...}({,,...}),,...}{}{|}...{|}nniIniInnnniIPXiXiPXiXiXiPXiXiXiPXiPXiXiPXiXi11110{}......nnnniiiiiIiiiiiiIPXippppp例题：设某地区有1600居民，有甲、乙、丙三个工厂的产品在该地区销售，据调查8月份买甲、乙、丙三个工厂产品的户数分别为480，320，800，9月份调查发现原买甲48户转买乙，96户转买丙；原买乙的有32户转买甲，有64户转买丙；原来买丙的有64户转买甲，有32户转买乙，估算9月份及12月份，甲、乙、丙三个工厂的产品在该地区市场占用率。一个有限状态的马氏链,当满足条件时,经过一段试验时间后,过程将到平稳(或平稳)状态,此后过程那一个状态的概率不再随时间而变化.0)(sijp(1)解:显然遍历01011/21/2(,)(,)2/53/5001010110112254/9135/9251马尔可夫链的状态分类周期、非周期常返、非常返其中，常返分为正常返、零常返非周期的正常返称为遍历状态到达和互通设马尔可夫链的状态空间I={1,2,3,4,5,6,7,8,9}，状态转移图如下图896527431观察状态1定义4.6如集合{n:n≥1,pii(n)0}非空，则称该集合的最大公约数d=d(i)=G.C.D{n:pii(n)0}为状态i的周期。如d1就称i为周期的，如d=1就称i为非周期的。由定义知,当n不能被d整除时,pii(n)=0引理4.1如i的周期为d，则存在正整数M，对一切n≥M，有pii(nd)0。例题:设有4个状态的马尔可夫链,它的一步转移概率矩阵为:画出其状态传递图,该过程是否具有周期性?解:001/21/2001/21/21/21/2001/21/200001/21/2001/21/21/21/2001/21/200所有状态周期为2123411/21/211状态转移图状态2和3具有相同的周期,但是状态2,3有区别.为此引入常返性的概念。首中概率它表示质点由i出发，经n步首次到达j的概率，表示为)|,11,()(iXjXnvjXPfmnmvmnij同时我们令表示质点由i出发，经有限步终于到达j的概率。1)(nnijijff定义4.7称状态i为常返的，如fii=1；称状态i为非常返的(滑过态)，如fii1。对于常返态i，由定义知{fii(n),n≥1}构成一概率分布，此分布的期望值1)(nniiinf表示由i出发再返回的i的平均返回时间。定义4.8如ui∞，则称常返态i为正常返的；如ui=∞，则称常返态i为零常返的。定理4.4对任意的状态i,j以及,有：1n()()()1nnknkijijjjkpfpC-K方程与定理4.4都是马尔可夫链的关键公式,因为他们都可以把分解成较低步的转移概率之和的形式.()nijpIklnkjliknijppp)()()(C-K方程01()0010()()1(,11,,|)(|)(|,,11,).(,11,|)nvknnijnnnvkkvknnkkjjikkjpPXjXiPXjXiXjvkXjPXjvkXjXPXjvkXipfjXjXi证明：定义：到达如果对状态i和j存在某个n（n≥1），使得pij(n)0,即由状态i出发，经过n次转移以正的概率达到状态j，则称自状态i可到达状态j,并记为