北大随机过程课件：第-2-章-第-3-讲-马尔可夫状态分析

马尔可夫链状态分类1马尔可夫链中状态的分类：1.1到达和相通：定义1：状态i可到达状态j，如果对状态i和j存在某个)1(≥nn使得0njip，即由状态i出发，经过n步状态转移，以正的概率到达状态j，则称自状态i可到达状态j，并记为ji→。反之，如状态i不能到达状态j，记为ij+→，此时对于一切0,=njipn。定义2：状态i和状态j互通，有两个状态i和j，如果由状态i可以到达状态j，且由状态j可以到达状态i，则称状态i状态j相通，记作ji←→定理1：到达的传递性，如果由状态i可以到达状态k，由状态k可以到达状态j，则由状态i可以到达状态j，即到达具有传递性。定理2：相通具有传递性。如果由状态i和状态k相通，状态k和状态j相通，则由状态i和状态j相通，即相通具有传递性。1.2状态空间的分解：定义1，状态空间的类，如果两个状态相通，则称两个状态处于同一类中。可以按照相通的概念把状态空间分成一些隔离的类。状态空间分解成隔离的类，对于每个类都有相应的状态转移矩阵。定义2，状态空间的闭集，设C为状态空间的一个子集，如果从C中的任何一个状态i不能到达C以外的任何状态，则称C是闭集。如果单个状态构成一个闭集，则称这个状态为吸收态。整个状态空间必定构成一个闭集。闭集的充分必要条件是，CjCipji∉∈=,0。定义3，不可约的马尔可夫链如果除了整个状态空间以外，没有别的闭集的马尔可夫链称为不可约的，这时所有的状态是相通的。定理1，在m步转移概率矩阵中，如果只保留闭集中各状态间的转移概率，而把其他所有行和列的元素删去，则留下的概率矩阵满足∑∈∈=CkkiCip,1。1.3状态的常返态和滑过态定义1，对于任意两个状态i，j，设jiT代表从状态i出发首次进入状态j的最早时刻,即{}1,)(,)0(:min)(≥===njninTjiξξω。定义2，从状态i经过n步第一次到达状态j的概率，{}inTPfjirnji===)0(/)(ξ。定义3，从状态i迟早到达状态j的概率，{}∑∑∞≤∞≤====njirnnjijiinTPff11)()0(/ξ。定理1，对于任意的∞≤∈nIji1,,，有)(1)()(rnjjnrrjinjipfp−=∑=。定理2，0jif的充要条件，ji→推论，i，j相通的充要条件是0,0ijjiff定义4，如果1=iif，则称状态i是常返的。定义5，如果1iif，则称状态i是非常返的,是滑过态。定理3状态i是常返的的充要条件是，∞=∑∞=1)(nniip，如果状态i是非常返的，则∞−=∑∞=iinniifp111)(证明：引入系统从状态i出发经过n步，到达状态j的概率)(njip对应的母函数，∑∑∞=∞=+==1)(0)()(nnnjijinnnjijispspsPδ同时引入从状态i第一次到达状态j的概率)(njif对应的母函数∑∞==0)()(nnnjijisfsF考虑到)(1)()(rnjjnrrjinjipfp−=∑=，有()()()()()())()()(01)()(1)(11)()(1)(1)(1)(sPsFspsfspsfspsfspfspsPjjjijimmmjjrrrjijirnrnrnjjrrrjijinnrrnrnjjrrjijinnrnjjnrrjijinnnjijiji+=⋅+=⋅+=⋅+=⎟⎠⎞⎜⎝⎛+=+=∑∑∑∑∑∑∑∑∑∞=∞=∞=−−∞=∞==−−∞=−=∞=δδδδδδ令j=i有)(11)()()(1)(sFsPsPsFsPiiiiiiiiii−=+=注意到()0(1)niiiinPp∞==∑，iinniiiiffF∑∞===0)()1(状态i是常返的1=iif，()1(1)niiiinPp∞===∞∑，状态i是非常返的1iif，()1(1)niiiinPp∞==∞∑，定理4，两个相通的状态、若一个是常返的，另一个必是常返的。定理5，如果状态j是非常返的，则对每一个状态i，()1nijnp∞=∞∑，0lim)(=∞→njinp。1.4周期的状态和非周期的状态定义1，周期性的状态，只有当转移步数n是整数d的正倍数时，相应的转移概率为非零值，定义2，遍历态非周期的常返态定义为遍历态。2马尔可夫链的状态空间举例绘出各个状态之间的转移图。研究状态的到达和相通，进行状态空间的分解。研究状态空间的周期性。研究状态的常返性和非常返性。例1设有三个状态（0，1，2）的马尔可夫链，它的一步转移概率矩阵是，⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=3/23/104/14/12/102/12/1P，求各个状态之间的关系。解：绘出各个状态之间的转移图。研究状态的到达和相通，进行状态空间的分解。系统中的状态是相通的。例2设有四个状态（0，1，2，3）的马尔可夫链，它的一步转移概率矩阵是，⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=10004/14/14/14/1002/12/1002/12/1P，求各个状态之间的关系。解：绘出各个状态之间的转移图。研究状态的到达和相通，进行状态空间的分解。状态（0，1）是一个闭集，状态（2）是一个滑过态，是非常返的，状态（3）是一个吸收态，也是一个闭集。例3设有9个状态（0，1，2，3，4，5，6，7，8）的马尔可夫链，它的一步转移概率矩阵如下，其中*表示正概率元素，试对它的状态进行分类。⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎛=00*000000***00000000*0*00**00000*000000**0000000**00000000000*0000000*0000000000*P绘出各个状态之间的转移图。研究状态的到达和相通，进行状态空间的分解。状态0是一个吸收态，状态1，2；3，4，5分别组成两个闭集。状态6；7，8都是滑过态。例4设有四个状态（0，1，2，3）的马尔可夫链，它的一步转移概率矩阵是，⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=0010001000012/12/100P，求各个状态之间的关系。解：绘出各个状态之间的转移图。研究状态的到达和相通，进行状态空间的分解。这是一个有限状态的马尔可夫链，所有状态都是相通的，都是常返的。例5设有五个状态（0，1，2，3，4）的马尔可夫链，它的一步转移概率矩阵是，⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎝⎛=2/1004/14/102/12/10002/12/1000002/12/10002/12/1P，求各个状态之间的关系。解：绘出各个状态之间的转移图。研究状态的到达和相通，进行状态空间的分解。（0，1）是一个闭集，这两个状态是常返的，（2，3）是一个闭集，这两个状态是常返的，（4）是一个非常返的滑过态。例6试研究无限制随机游动各状态的性质。解：它的一步转移概率是，⎪⎩⎪⎨⎧−+≠===−+1,1,011iijifpqpppjiiiii由于无限制随机游动各状态都相通，则所有状态或全部是常返的或全部是非常返的。研究状态0的常返和非常返的性质，可以计算∑∞=1)(00nnp。如果∑∞=1)(00nnp是有限的，则0状态是非常返的，如果∑∞=1)(00nnp是无限的，则0状态是常返的。研究状态0的常返和非常返的性质，也可以计算()001nnf∞=∑。如果()001nnf∞=∑小于1，则0状态是非常返的，如果()001nnf∞=∑等于1，则0状态是常返的。从0状态出发，经过偶数次转移，它所取的状态一定是偶数状态。因此，只有经过偶数次转移，才能到达0状态。nnnppnnp)1(2)(00−⎟⎟⎠⎞⎜⎜⎝⎛=利用公式：nennnnπ2!−=()()ππnppnpqpnnn)1(44)(00−==()∑∑∞=∞=−=11)(00)1(4nnnnnpppπ考虑到1)1(4≤−pp，等式成立的条件是p=1/2。当p=1/2时，∞=⎟⎟⎠⎞⎜⎜⎝⎛+++=∑∞=L31211111)(00πnnp，状态0和所有状态是常返的。当p≠1/2时，∞≤∑∞=1)(00nnp，状态0和所有状态都是非常返的。研究状态、首先是0状态的常返和非常返性。引用以前研究随机游动的矩生成函数：考虑随机游动，迟早返回原点的概率，2()114Vzpqz=−−2121(1)1,1/2(1)1,1/2nnnnvVzpqvVzpq∞=∞========≠≠∑∑考虑随机游动，返回原点的概率之和，21()14Uzpqz=−2121(1),1/2(1),1/2nnnnuVzpquVzpq∞=∞====∞====∞≠≠∑∑例7设有四个状态（0，1，2，3）的马尔可夫链，它的一步转移概率矩阵是，⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=002/12/1002/12/12/12/1002/12/100P，求各个状态之间的关系。解：绘出各个状态之间的转移图。研究状态空间的周期性。状态有两个字类，（0，1）和（2，3）。该过程有确定性的周期状态转移，（0，1）→（2，3）→（0，1）→（2，3）…。周期是2。例8设有8个状态的马尔可夫链，它的一步状态转移概率矩阵给定，给出它的状态转移图，分析它状态的周期性。⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎛=0000000100000001212100000001000000001000000032310000002121000000004121410P绘出各个状态之间的转移图。研究状态空间的周期性。