马尔可夫链状态空间的分解实验报告.docx
马尔可夫链状态空间的分解一、实验内容生成一个状态个数大于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） a，n=1.,2,中的状态同类，即或全是正常返,或全是零常返，它们有相同的周期，且4=IJy；3） D是由全体非常返状态组成，自CC中的状态不能到达。中的状态。2.按对周期不可约马尔可夫链进行分解周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交的子集之和，即J-IC=<G,.G,cG,=,rs且使自G中任一状态出发，经一步必转移进入Gv中（其中Gd=G。三、具体步骤1 .按常返性和互通性进行状态空间的分解1）生成马尔可夫链的转移矩阵P,即生成100*100的随机矩阵，行向星:元素之和为1;2）筛选出吸收态，即为单点闭集，存储在C1.中的行向量中:3）筛选出各状态所有的可能路径，路径不重更，每一条路径只返回第一个状态，不返回中间状态,存储在TI中：4从TI中提取可能的常返闭集,（不包括单点闭柒），即在T1.的路径中筛选出首尾相同状态的路径，存储在T2中:pcirinOJMZCoOdoub.1.234S7891011U»1=310000600260000e0003WR900000004，00000000S00000000425治0e0000000742他0°000°00074947,0000000009000000000000100000000000001100000000600U0*A0C0C04A00C00A0A00C5）从T2中筛选出久正的常返闭集，自该闭集的内部不能到达它的外部，存储在Cn的行向量中：P>¾二田100x1.dcwbWT2一Cn123,4S67S9IO11口3510000002103050709010000C3OO000000004OO000000005OO000000006q00j004g6）根据C1.和Cn.去掉状态空间所有的常返态，即为全体非常返态，存储在D中。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的行向量中:1234561Z3I4600022000003350000400000050000006000000GnJPxiXGn6x6<!；>ub1.r四、结论程序基本涧足实验要求，按常返性和互通性可将马尔可夫链的状态空间分解为=oUCuG,其中C1.的每一个行向量都是一个吸收态，C,的每一个行向量是由常返状态组成的不可约的闭集，。为非常返状态全体：按周期对不可约的马尔可夫琏进行分解为C=G1.：G?U.,自G,中的任一状态出发，经一步转移必进入GE中。五、分析总结尽管程序已基本完成实盼内容，但还是有一些不尽人意的地方，还存在如下问题：1）生成100*100的0,1随机矩阵时，我为了使后面观察效果更明显，设置ri出现的概率小丁5%,这有极小的可能导致转移矩阵某一行全为0,从而使得生成的转移矩阵不满足要求：2)顺序遍历各状态的可能的不重电路径时，由于算法限制，极小可能不能全部遍历完所有的路径，尚未解决这个问题；3)从可能的常返闭集中提取真正的Cn时，其中对矩阵的处理很多，尚未找到更简便的方法：4)因为状态较多，并且由于随机矩阵导致状态之间的转移错综更杂，极大可能100个状态中没仃个基本常返团集，为了更好的检验算法的正确性，对转移矩阵做/特殊化处理.六、附录1 .将状态空间按常返性和互通性进行分解c1.eara1.1.;c1.c;1-(1:100);S指定状态空间%生成100*100的随机地阵，行向量元素之和为1,即为马尔可夫链的转移矩阵N=100;A-rand(N,N><0.05;M殳灯时阵中出现烫触1的概率小于5«a-3um(A,2;"计疑矩阵行向51元案之和A-A+Zros(NfN);h将矩阵中的1转换为数11fork=1.:N针史矩阵行向依兀索之和为1A(kr三)-A(kr:)a(k);endP三A;f.P为转移矩阵颁证是否达到效果，举特例观察P(2,:)-0;毋点用第(2>P(2,2)=1.;P(4,:)=0;4i.H1.i1.i<2>P(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.-Zeros(NrI);三单也闭集。储所有吸收态f1.-O;f2-1.;f3三1.;R-I;fori三1.:N;forj=1.:N;ifPU,j)-j>>在电点用佻中存储所仃的吸收态C1.(f2r1.)-i;f2=f2+1.;endifP<i,j-O&“j)0在过渡W阵中存储该状态到达其他状态的起始鞋,只用一次T1.(Rjf3)-1;f3-f3÷1.;T1<R,f3)=j;f1.=1.;endiff1.三三1.for1=1:N;fork«1.:N;if(P(1.k>>0)&&(T1.<R,f3)-1)AA(1.*-k)“T1(Rrf3÷1.)-O8从该状态能帔到达其他状态的情况大若能畴到达则迸行存储f3-f3+1.;T1.(Rzf3)-k;OCdendf1.-O;f3三1.;R=R+1;endendendW找出常返和非常返，并分类f4三1.;T2-zeros(NrN);TCM1.，.；/集)forp-1:N*10forq三1.:NifT1.(pr1)=T1(p,q>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.ength<nonzero5(T3<p,:);ifm*=0forke1.:Nif(ismember(krT3(p,:>)-0)&&(P(mrk)-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,7T6sortrows<brT5);T7-T6(:Z2:N¼1);row,co1.1.-size(T6);£6=1;C-zeros(NrN);Cn的每行即为,个常返闭如fork-1:row-1if(T6(k+1.,1.)-T6<k,1.)>1.Cn(fr:)-T7(k,f6-f÷1.;endendT8-niqe(nonzeros(Cn);T9=setdiff(IzT8);D-setdiff(T9zC1.);Q去抻状春空间所有的常返心即为全体非常返态d±sp(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.;a1.=0;for1-1:NT1.(i,f1.)-i;forj=1.:NifP(i,j)>0f1.-f1.÷1.;T1.(irf1.)三j;a1.=a1.+1.;endend
