1、马尔可夫链状态空间的分解一、实验内容生成一个状态个数大于100的马尔可夫链，状态之间的转移关系随机设定（例如某状态可以步到达其他状态的比例为10%）1）将状态空间按常返性和互通性进行分解2）在1）的基础上对周期不可约马尔可夫徒进行分解二、理论基础设C为状态空间I的非空子集，若对任意ieC及大史C都有PM=0,则称C为随机）闭桀，若C中所有状态是互通的，称C是不可约的闭集。若马尔可夫链XJ的状态空间I是不可约的闭集，则称XJ为不可约的马尔可夫链。1.按常返性和互通性进行状态空间的分解任一马尔可夫链的状态空间I,可唯一地分解成有限个或可列个不相交的集D,C1.,Cif之和,使得1）每一G，n=1.
2、2,是常返态组成的不可约闭集：2） a，n=1.,2,中的状态同类，即或全是正常返,或全是零常返，它们有相同的周期，且4=IJy；3） D是由全体非常返状态组成，自CC中的状态不能到达。中的状态。2.按对周期不可约马尔可夫链进行分解周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交的子集之和，即J-IC=二田100x1.dcwbWT2一Cn123,4S67S9IO11口3510000002103050709010000C3OO000000004OO000000005OO000000006q00j004g6）根据C1.和Cn.去掉状态空间所有的常返态，即为全体非常返态，存储在D中。
3、2 .按对周期不可约马尔可夫他进行分解1）以教材例4.14生成不可分马尔可夫链的转移矩阵P,其状态空间C=（1,2,3,456）；P0.2500Hd62doub1.e2）筛选出每一状态能一步到达的状态，从T1.的第二列开始存储:3K三T1IP刃TIB66doub1.e*123456Id350Oi022Ii4640332Oj0Oj0*44300dd5S2Oi0Oj0;63503）提取门的2-6列为T2筛选出相同的行向fit,或是有从属丁关系的行向量，然后返回它们所在行，即为一个子集（自这些子集中的任一状态出发，经一步必转移到下个子集），存储在Gn的行向量中:1234561Z3I460002200
4、0003350000400000050000006000000GnJPxiXGn6x6ub1.r四、结论程序基本涧足实验要求，按常返性和互通性可将马尔可夫链的状态空间分解为=oUCuG,其中C1.的每一个行向量都是一个吸收态，C,的每一个行向量是由常返状态组成的不可约的闭集，。为非常返状态全体：按周期对不可约的马尔可夫琏进行分解为C=G1.：G?U.,自G,中的任一状态出发，经一步转移必进入GE中。五、分析总结尽管程序已基本完成实盼内容，但还是有一些不尽人意的地方，还存在如下问题：1）生成100*100的0,1随机矩阵时，我为了使后面观察效果更明显，设置ri出现的概率小丁5%,这有极小的可能导
5、致转移矩阵某一行全为0,从而使得生成的转移矩阵不满足要求：2)顺序遍历各状态的可能的不重电路径时，由于算法限制，极小可能不能全部遍历完所有的路径，尚未解决这个问题；3)从可能的常返闭集中提取真正的Cn时，其中对矩阵的处理很多，尚未找到更简便的方法：4)因为状态较多，并且由于随机矩阵导致状态之间的转移错综更杂，极大可能100个状态中没仃个基本常返团集，为了更好的检验算法的正确性，对转移矩阵做/特殊化处理.六、附录1 .将状态空间按常返性和互通性进行分解c1.eara1.1.;c1.c;1-(1:100);S指定状态空间%生成100*100的随机地阵，行向量元素之和为1,即为马尔可夫链的转移矩阵N
6、100;A-rand(N,NP(2,2)=1.;P(4,:)=0;4i.H1.i1.iP(4,4)-1.;P(1.,:1-0;:常返团集(1,3,5,7,9)P(3,：)=0;P：)=0；PC,3)=1;P(3,5)-1.;考常返闭今(10,30r50,70,90)P1)=1；PdO,：=0;P(30,:)-0;P(50z:-0;P(70,:-0;P(90,:=0;P(1.Oz3O)=1.;P(30,50)-1;P(SO,70)-1;P(70,90)-1;P(90,10)=1.;T1.-zeros(N*10,N);二过度祖阵1郴I各状态所有的可能路径%在电点用佻中存储所仃的吸收态C1.(f2
7、r1.)-i;f2=f2+1.;endifPi,j-O&“j)0在过渡W阵中存储该状态到达其他状态的起始鞋,只用一次T1.(Rjf3)-1;f3-f31.;T10)&(T1.56T1.(p,q+1.)=065q-=1.3从T1.中提取可能的常返闭张T2(f4,:)-T1.p,:);f4=f4+1.;break;endendendT3-T2(1.-b:);S过渡矩阵3.用来符T2/变为NJ的矩阵,减少计算量T4-zeros(NrN);波矩阵4count=0;f5-1.;a1.-0;forp=1.:Nforq2:Nm-T3(p,q);n=1.engthnonzero5(T3)-0)&(P(mrk)
8、0)&cont-0)生从T3中提取基木常返阳泉a1.=a1.+1.;ifa1.三N-n+1.count-1;endendendifcont1.T4(f5z:)=T3(p,:);f5-f5+1.;count-0;1.三0;endendendT5rb-unique(T4,rowa,);“过收矩阵5,6,7T6sortrowsbrT5);T7-T6(:Z2:N1);row,co1.1.-size(T6);6=1;C-zeros(NrN);Cn的每行即为,个常返闭如fork-1:row-1if(T6(k+1.,1.)-T61.Cn(fr:)-T7(k,f6-f1.;endendT8-niqe(non
9、zeros(Cn);T9=setdiff(IzT8);D-setdiff(T9zC1.);Q去抻状春空间所有的常返心即为全体非常返态dsp(ci的疗向量为吸收态.0行向量即为M闭集di.川戊)；2 .对周期的不可约乌尔可夫链进行分解c1.eara1.1.;c1.c;P=0,0,1/2,0,1/2,0;1/3,0,0,1/3,0,1/3;0,1,0,0,0,0;0,0,1,0,0,0;0,1,0,0,0M0,O,1.4,0,34,O;C-(1.三6;%P为不可分马尔可夫链的转移短阵，C为其状态空间N-6;T1.-Zeros(NrN)；:过波矩阵，用来存储某状态经一步转移能进入的状态f1.三1.;
10、a1.=0;for1-1:NT1.(i,f1.)-i;forj=1.:NifP(i,j)0f1.-f1.1.;T1.(irf1.)三j;a1.=a1.+1.;endendf1.1.;end%对筛选结果的处理T2-T1.(：r2:6);1过及提取T1.的2-6列Gn=Zeros(NrN);*Gn中的树-行即为一个子巢*自该子佻中的任-状态出发,经步必转移到下一个子集2-1;forp=1.:NTGn(p,f2)三p;forq-p41：Nifis11ember(T2(qr：)rT2(r：)三1.IIsmember(T2(,：),T2(qr：)三1.f2-f21.;Gn(pzf2)-q;1返回它们所在行即为一个子集endifi$member(Gn(r1)rGn(1:-1.,：)Gn(prf2=0;endendf2三1.;enddispG;中的行向/为iC）；：*2*4Se-COO.5OOO.5OOOO20.3333OO0.3333O0,3333JO1.OOOO4OO1.OOOS0：1OOOOO.75
免费区 
