5.2马尔科夫状态的分类

5.2 状态的性质和分类{1,2,3},12;3{,0},nnSXnXnMarkov=≥设系统有三种可能状态“”—良好；“”—正常“”—失效。以表示系统在时刻的状态。并设是一链在没有维修及更换条件下,其自然转移概率矩阵为17212020209101010001P⎛⎞⎜⎟⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠定义5.7()0,0,,nijnPij∃≥若使得称状态可达状态.,.ijjiijij→→↔记为若同时这称与互通，记为注：，则意味着不能到达状态若状态ji.0,0)(=≥nijPn有对一切定理5.3：(1);ii↔自反性(2),ij↔对称性(3),,ijjk↔↔传递性.ik↔则;ji↔则(因而互通关系是等价关系)注：不同的类。同时属于两个并且任何一个状态不能都是互通的态归为一类，则同一类状把任何两个相通的状态,定义5.8:是不可约的，否则称为可约的.例1：{0,1,2},MarkovS=设链的状态空间其一步转移概率矩阵为:⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=3231041412102121PMarkov若链只存在一类,则称此马氏链,.试研究各状态的关系并画出状态传递图同一类的状态具有相同的性质定义5.9  (周期性)(){,1,0}().1,1niinnPddiididi≥==若集合非空，则称它的最大公约数为状态的周期若称状态是周期的；若，称状态是非周期的.规定：.的周期为无穷大当该集合是空集时，称i例2注1：的周期。是步长达到，但仍称不能通过显然12211→注2：.0)(ndiiPnd都有是周期，并非所有若.01)1(11==dPn时，如上例中，()110,nP由可能的步长为{4,6,8,10,},T=2,最大公约数为(12dd==所以）11378926541111111/312/3定理5.4：若ij↔，则d(i)=d(j)。证明：若i与j相通，则存在m,n，使得()()()()()()()00,00mnijjimnmnmniiikkiijjikppppppp∞+=∴=≥∑对任意的s，若有，则()0sjjp0nsmmsniiijjjjipppp++≥因为d(i)是i的周期，所以d(i)应同时整除n+m和n+m+s，则d(i)一定整除s，而d(j)是j的周期，所以d(i)整除d(j)。反过来也可证明d(j)整除d(i)，于是d(i)=d(j)。注:   当两个状态的周期相同时，有时其状态之间有显著差异。如：{1,23,4},S=马氏链的状态空间，其一步转移概率矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=010010000210210010P(2),(3),2,3dd求并比较状态的区别.111.从一个状态出发是不是一定能够在有限时间内返问题：回该状态？2.如果能够返回，那么平均返回时间（）一定平均回转时有限吗？正常返，（零常返）3.如果能够返回，那么平均返回时间的精确值是多少？（常返，暂留）（平稳分布）上例：设{1,23,4}S=，，转移概率如图4.4，易见状态2与状态3有相同的周期d=2。状态3经过两步必定返回3，所以状态3是常返的；状态2则不然，当2转移到3后再也不能返回到2，所以2是非常返的。定义5.10:  (常返性)(),,nijijfinj对任何状态以记从出发经步后到次达首的概率,(0)0.ijf=则有1n≥时,()0{,,1,2,1|}nijnkfPXjXjknXi==≠=−=，()1,nijijnff∞==∑令，若1=jjf.为常返状态称状态j，若1jjf为非常返状态称状态j（或瞬过状态、.瞬时状态、滑过状态）)(1∪∞=nnAP∑==ninAP1)(∑=∞=1)(nnijfijf=注2：:,.ijfij表示从出发有限步到达的概率当i为常返1(1)(1),1iiiiiiiififfii=−状态时，以概率从出发，在有限步内过程将重新返回；当为非常返状态时以概率过程不再回到，即从滑过去了.注3：,i对于常返状态()1niiinnfμ∞==∑定义).(时间所需的平均步数出发再返回到表示从则iiiμ0:{,,1,2,,1|},nnkAXjXjknXi==≠=−=含义设1,nnnnAAnnij∞=∪在不同时是不相交的，表示总有一个使得过程经步以后可以从到达所以注1：例3定义5.11,,iiiμ+∞对于常返状态若则称为正常返态;iiμ=+∞若，则称为零常返态;i特别地,若是正常返且是非周期的,.则称之为遍历状态i若是遍历状态,(1)1,iif=且.i则称是吸收状态{,0,1,2}nXn=已知马氏链的状态空间其一步转移概率为⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=00011000010041414141P1,,1.μ试确定其状态的常返性周期性及遍历性并确定状态其平均转回时间{1,23,4},S=，例4{,0,1,2}nXn=已知马氏链的状态空间{1,23,4},S=，其一步转移概率为⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=001002121000013131310P.试确定其状态的常返性，周期性及遍历性可以证明：常返、非常返等）的状态（同正常返、零它们有相同同一类的状态,,ji引理5.1()()nnijijPf（给出了与的关系）ij1n≤+∞，有对任意状态，及()()()1nnlnlijijjjlPfP−==∑()0(i)nijnppXjX===证01010()()1(,11,,)(,,11,)(,11,)nvknknnvkkvknnkkjjijkPXjvkXjXjXiPXjXiXjvkXjPXjvkXjXipf==−==≠≤≤−======≠≤≤−=⋅≠≤≤−===∑∑∑定理：与有如下关系nijp（）nijf（）11,,1,1,,12,,13,04,00nnknkijijjjknikkjnkjijijijijjiijSnpfppfnfpnijfijff−=−≠∀∈≥=⎧⎪=⎨⎪=⎩→⇔↔⇔∑∑（）（）（）（）（）有且定理5.5为常返状态当且仅当状态i)1(∞=∑∞=0)(nniiP⇒⎩⎨⎧0lim.1)(≠∞→niinPi为正常返态0lim.2)(=∞→niinPi为零常返态)0lim()(∞→niinP或为非常返态时，状态i)2(iinniifP-110)(=∑∞=0lim)(=∞→niinP因此有证明：约定，(0)(0)1,0iiiipf==()(0)()01()()11()()()()11()()()100()01111()()111nniiiiiinnnlnliiiinllnllnliiiiiiiilnllnllmmiiiiiiiilmmniiniipppfpfpfpfpfppf∞∞==∞−==∞∞∞∞−−====∞∞∞===∞==+=+=+=+=+=+∴=−∑∑∑∑∑∑∑∑∑∑∑∑∵()()001,1nniiiiiiiinnpfpf∞∞==∴∞⇔=∞⇔=∑∑的含义()0niinp∞=∑1,0nnnXiIXi=⎧=⎨≠⎩令0nnI∞=则∑表示过程到达i的次数。{}()0000000[][]nnnniinnnnEIXiEIXiPXiXip∞∞∞∞===========∑∑∑∑所以()0niinp∞=∑表示过程从i出发返回到i的平均次数。引理5.2为常返态，且若iji,↔1=jif则定理5.6常返性是一个类性质：.,,,1(或非常返状态同为常返状态则若）jiji↔.,,,,2(或同为零常返状态同为正常返则同为常返态且若）jijiji↔⎪⎪⎩⎪⎪⎨⎧⎪⎩⎪⎨⎧⎩⎨⎧非周期（遍历态）有周期正常返态零常返态常返态非常返态状态闭集及状态空间的分解定理,,.MarkovC任意链从一个常返状态出发只能到达常返状态因此状态空间中的常返状态的全体构成一个闭集闭集：,,.SCiCC⊂设C若内的任何一个状态都不能到达外的任何状态则称为一个闭集{},iii如果单个状态构成的集合是闭集则称状态为吸收态.相关性质：是闭集C)1(⇔)0(0,,)(≥=∉∀∈∀nPCjCinij有是闭集C)2(⇔CipCjji∈∀=∑∈,1为吸收态i)3(⇔1=iip齐次马氏链不可约)4(⇔任何两个状态均互通)5(所有常返态构成一个闭集)6(在不可约马氏链中,所有状态具有相同的状态类型.状态空间分解定理：定理5.7：可唯一分解为链的状态空间任意,SMarkov,,,,21之和交的子集有限个或可列个互不相CCD使得;)1(约闭集是常返状态组成的不可每一个nC.,,1,.,,)2(nijnCjifC∈=且它们有相同的周期零常返态或者全是或者全是正常返态中的状态同类..)3(中的状态达中状态出发不能到自由全体非常返态组成DCDnnCCCDS++++=21周期链分解定理：定理5.8：其状态空间链的不可约一个周期为,Markovd，即个互不相交的子集之和可唯一分解为dS,,,1-0srSSSSsrdrr≠∅===∩∪).1,01SSSSdrr=+中（其中步转移必进入经中任意状态出发且使得自例5{1,23,45},S=设马氏链的状态空间，，其一步转移概率矩阵⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡=00010000010010000210210210021P,.试讨论哪些状态是吸收态,闭集和不可约链并将此状态空间进行分解例6：{0,12},S=设马氏链的状态空间，其转移概率00,10111,,,.222iiiPPPiS+===∈将此状态空间进行分解，并指出其常返性和周期.例考虑直线上无限制的随机游动，状态空间为{0,1,2,}E=±±转移概率为,1,1,1iiiiPpPp+−==−则对于状态0，有(21)(2)00002(2)!0,(1)[(1)]!!nnnnnnnnPPCppppnn+==−=−由斯特林(Stirling)公式可知：当n充分大时有12!2nnnneπ+−∼所以(2)00[4(1)]nnppPnπ−∼注意到1(1),4pp−≤11(1)42ppp−=⇔=所以，当时，12p≠()000,nnP∞==∞∑此时，状态0是常返的。当时，12p=()000,nnP∞=∞∑此时，状态0是滑过的。由于过程的各个状态都是相通的，由此可判断其它状态的常返性。•为什么要对马尔可夫链的状态进行分类?对齐次马氏链代表的系统进行研究时要讨论两个问题:(1)在某一固定时刻n时的概率特性即求n步转移概率或绝对概率pj(n)=P{Xn=j}(称瞬态分析);(2)当n→∞后系统的概率特性,即n→∞时,pij(n)的极限是否存在,若存在又与状态的关系如何,极限概率能否构成概率分布.解决此类问题需要对状态(状态空间)进行分类(分解).以Nj(t)记到时刻t为止转移到j的次数。若j是常返的，且X0=j，则因为一旦转移到j，过程在概率上重新从头开始，故{Nj(t),t≥0}是一个来到时间间隔分布为的更新过程。若X0=i，，且j是常返的，则{Nj(t),t≥0}是一个延迟更新过程，其初始来到时间间隔分布为。ij↔{},1njjfn≥{},1nijfn≥常返态表明，过程从常返状态出发能无穷次返回该状态，而滑过状态最多只能有限次地返回，因此，随着时间的发展，滑过状态将逐渐消失。所以，在对Markov链作稳态设计时，滑过状态是不予考虑的，这也说明了区分常返态与滑过状态是十分重要的。为什么要将状态进行分类呢？33互达等价类的同一性质：1()3ijdidjijij↔=如果，则（）（）,(2)常返当且仅当常返（）正常返当且仅当正常返一个互达等价类中各状态具有相同的周期和常返性。判断一个状态的性质时，可以从它的等价类中找出一个容易判断的状态来判断。物以类聚，人以群分例股票价格的马尔科夫性考虑离散时间的股票价格过程，对时间t(t=0,1,2,…),设S(t)表示某一股票在t时刻的价格，每间隔一个单位时间股票价格以概率q上升到前一期的u倍，或以概率1-q下降到前一期的d倍，且各次涨跌是相互独立的，即()(1)()uStStdSt⎧+=⎨⎩以概率q,以概率1-q,设S(0)=S，则SuSdS2uSudS2dSq1q−2q(1)qq−(1)qq−2(1)q−定义独立同分布的随机变量序列{}0tiiX=iuXd