馬爾可夫鏈狀態(tài)空間的分解實(shí)驗(yàn)報(bào)告

馬爾可夫鏈狀態(tài)空間的分解實(shí)驗(yàn)內(nèi)容生成一個(gè)狀態(tài)個(gè)數(shù)大于100的馬爾可夫鏈，狀態(tài)之間的轉(zhuǎn)移關(guān)系隨機(jī)設(shè)定（例如某狀態(tài)可以一步到達(dá)其他狀態(tài)的比例為10%）1）將狀態(tài)空間按常返性和互通性進(jìn)行分解2）在1）的基礎(chǔ)上對(duì)周期不可約馬爾可夫鏈進(jìn)行分解理論基礎(chǔ)設(shè)C為狀態(tài)空間I的非空子集，若對(duì)任意及都有，則稱C為（隨機(jī)）閉集，若C中所有狀態(tài)是互通的，稱C是不可約的閉集。若馬爾可夫鏈的狀態(tài)空間I是不可約的閉集，則稱為不可約的馬爾可夫鏈。按常返性和互通性進(jìn)行狀態(tài)空間的分解任一馬爾可夫鏈的狀態(tài)空間I，可唯一地分解成有限個(gè)或可列個(gè)不相交的集D，C1，C2，……之和，使得每一Cn，n=1，2，…是常返態(tài)組成的不可約閉集；Cn，n=1，2，…中的狀態(tài)同類，即或全是正常返，或全是零常返，它們有相同的周期，且,;D是由全體非常返狀態(tài)組成，自Cn中的狀態(tài)不能到達(dá)D中的狀態(tài)。按對(duì)周期不可約馬爾可夫鏈進(jìn)行分解周期為d的不可約馬氏鏈，其狀態(tài)空間C可唯一地分解為d個(gè)互不相交的子集之和，即且使自Gr中任一狀態(tài)出發(fā)，經(jīng)一步必轉(zhuǎn)移進(jìn)入Gr+1中（其中Gd=G0）。具體步驟按常返性和互通性進(jìn)行狀態(tài)空間的分解生成馬爾可夫鏈的轉(zhuǎn)移矩陣P，即生成100*100的隨機(jī)矩陣，行向量元素之和為1；篩選出吸收態(tài)，即為單點(diǎn)閉集，存儲(chǔ)在C1中的行向量中；篩選出各狀態(tài)所有的可能路徑，路徑不重復(fù)，每一條路徑只返回第一個(gè)狀態(tài)，不返回中間狀態(tài)，存儲(chǔ)在T1中；從T1中提取可能的常返閉集，（不包括單點(diǎn)閉集），即在T1的路徑中篩選出首尾相同狀態(tài)的路徑，存儲(chǔ)在T2中；從T2中篩選出真正的常返閉集，自該閉集的內(nèi)部不能到達(dá)它的外部，存儲(chǔ)在Cn的行向量中；根據(jù)C1和Cn，去掉狀態(tài)空間所有的常返態(tài)，即為全體非常返態(tài)，存儲(chǔ)在D中。按對(duì)周期不可約馬爾可夫鏈進(jìn)行分解以教材例4.14生成不可分馬爾可夫鏈的轉(zhuǎn)移矩陣P，其狀態(tài)空間C=（1,2,3,4,5,6）；篩選出每一狀態(tài)能一步到達(dá)的狀態(tài)，從T1的第二列開始存儲(chǔ)；提取T1的2-6列為T2，篩選出相同的行向量，或是有從屬于關(guān)系的行向量，然后返回它們所在行，即為一個(gè)子集（自這些子集中的任一狀態(tài)出發(fā)，經(jīng)一步必轉(zhuǎn)移到下一個(gè)子集），存儲(chǔ)在Gn的行向量中；結(jié)論程序基本滿足實(shí)驗(yàn)要求，按常返性和互通性可將馬爾可夫鏈的狀態(tài)空間分解為，其中的每一個(gè)行向量都是一個(gè)吸收態(tài)，的每一個(gè)行向量是由常返狀態(tài)組成的不可約的閉集，為非常返狀態(tài)全體；按周期對(duì)不可約的馬爾可夫鏈進(jìn)行分解為，自中的任一狀態(tài)出發(fā)，經(jīng)一步轉(zhuǎn)移必進(jìn)入中。分析總結(jié)盡管程序已基本完成實(shí)驗(yàn)內(nèi)容，但還是有一些不盡人意的地方，還存在如下問題：生成100*100的0,1隨機(jī)矩陣時(shí)，我為了使后面觀察效果更明顯，設(shè)置了1出現(xiàn)的概率小于5%，這有極小的可能導(dǎo)致轉(zhuǎn)移矩陣某一行全為0，從而使得生成的轉(zhuǎn)移矩陣不滿足要求；順序遍歷各狀態(tài)的可能的不重復(fù)路徑時(shí)，由于算法限制，極小可能不能全部遍歷完所有的路徑，尚未解決這個(gè)問題；從可能的常返閉集中提取真正的Cn時(shí)，其中對(duì)矩陣的處理很多，尚未找到更簡便的方法；因?yàn)闋顟B(tài)較多，并且由于隨機(jī)矩陣導(dǎo)致狀態(tài)之間的轉(zhuǎn)移錯(cuò)綜復(fù)雜，極大可能100個(gè)狀態(tài)中沒有一個(gè)基本常返閉集，為了更好的檢驗(yàn)算法的正確性，對(duì)轉(zhuǎn)移矩陣做了特殊化處理。附錄將狀態(tài)空間按常返性和互通性進(jìn)行分解clearall;clc;I=(1:100);%指定狀態(tài)空間%生成100*100的隨機(jī)矩陣，行向量元素之和為1，即為馬爾可夫鏈的轉(zhuǎn)移矩陣N=100;A=rand(N,N)<0.05;%設(shè)置矩陣中出現(xiàn)邏輯1的概率小于5%a=sum(A,2);%計(jì)算矩陣行向量元素之和A=A+zeros(N,N);%將矩陣中的邏輯1轉(zhuǎn)換為數(shù)值1fork=1:N%使矩陣行向量元素之和為1A(k,:)=A(k,:)/a(k);endP=A;%P為轉(zhuǎn)移矩陣%驗(yàn)證是否達(dá)到效果,舉特例觀察P(2,:)=0;%單點(diǎn)閉集（2）P(2,2)=1;P(4,:)=0;%單點(diǎn)閉集（2）P(4,4)=1;P(1,:)=0;%常返閉集（1,3,5,7,9）P(3,:)=0;P(5,:)=0;P(1,3)=1;P(3,5)=1;P(5,1)=1;P(10,:)=0;%常返閉集（10,30,50,70,90）P(30,:)=0;P(50,:)=0;P(70,:)=0;P(90,:)=0;P(10,30)=1;P(30,50)=1;P(50,70)=1;P(70,90)=1;P(90,10)=1;T1=zeros(N*10,N);%過度矩陣1，存儲(chǔ)各狀態(tài)所有的可能路徑%(路徑不重復(fù)，只返回第一個(gè)狀態(tài)，不返回中間狀態(tài)）C1=zeros(N,1);%單點(diǎn)閉集，存儲(chǔ)所有吸收態(tài)f1=0;f2=1;f3=1;R=1;fori=1:N;forj=1:N;ifP(i,j)==1&&(i==j)%在單點(diǎn)閉集中存儲(chǔ)所有的吸收態(tài)C1(f2,1)=i;f2=f2+1;endifP(i,j)>0&&f1==0&&(i~=j)%在過渡矩陣中存儲(chǔ)該狀態(tài)到達(dá)其他狀態(tài)的起始鏈，只用一次T1(R,f3)=i;f3=f3+1;T1(R,f3)=j;f1=1;endiff1==1forl=1:N;fork=1:N;if(P(l,k)>0)&&(T1(R,f3)==l)&&(l~=k)&&T1(R,f3+1)==0%從該狀態(tài)能夠到達(dá)其他狀態(tài)的情況%若能夠到達(dá)則進(jìn)行存儲(chǔ)f3=f3+1;T1(R,f3)=k;endendendf1=0;f3=1;R=R+1;endendend%找出常返和非常返,并分類f4=1;T2=zeros(N,N);%過渡矩陣2，用來存儲(chǔ)可能的常返閉集（不包括單點(diǎn)閉集）forp=1:N*10forq=1:NifT1(p,1)==T1(p,q)&&T1(p,q+1)==0&&q~=1%從T1中提取可能的常返閉集T2(f4,:)=T1(p,:);f4=f4+1;break;endendendT3=T2(1:N,:);%過渡矩陣3，用來將T2轉(zhuǎn)變?yōu)镹*N的矩陣，減少計(jì)算量T4=zeros(N,N);%過渡矩陣4count=0;f5=1;a1=0;forp=1:Nforq=2:Nm=T3(p,q);n=length(nonzeros(T3(p,:)));ifm~=0fork=1:Nif(ismember(k,T3(p,:))==0)&&(P(m,k)==0)&&(count==0)%從T3中提取基本常返閉集a1=a1+1;ifa1==N-n+1count=1;endendendendifcount==1T4(f5,:)=T3(p,:);f5=f5+1;count=0;a1=0;endendend[T5,b]=unique(T4,'rows');%過度矩陣5,6,7T6=sortrows([b,T5]);T7=T6(:,2:N+1);[row,col]=size(T6);f6=1;Cn=zeros(N,N);%Cn的每一行即為一個(gè)常返閉集fork=1:row-1if(T6(k+1,1)-T6(k,1))>1Cn(f6,:)=T7(k,:);f6=f6+1;endendT8=unique(nonzeros(Cn));T9=setdiff(I,T8);D=setdiff(T9,C1);%去掉狀態(tài)空間所有的常返態(tài)，即為全體非常返態(tài)disp('C1的行向量為吸收態(tài)，Cn的行向量即為一個(gè)常返閉集，D由全體非常返態(tài)組成');對(duì)周期的不可約馬爾可夫鏈進(jìn)行分解clearall;clc;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,0,0;0,0,1/4,0,3/4,0];C=(1:6);%P為不可分馬爾可夫鏈的轉(zhuǎn)移矩陣，C為其狀態(tài)空間N=6;T1=zeros(N,N);%過渡矩陣，用來存儲(chǔ)某狀態(tài)經(jīng)一步轉(zhuǎn)移能進(jìn)入的狀態(tài)f1=1;a1=0;fori=1:NT1(i,f1)=i;forj=1:NifP(i,j)>0%篩選出每一狀態(tài)能一步到達(dá)的狀態(tài)，從T1的第二列開始存儲(chǔ)f1=f1+1;T1(i,f1)=j;a1=a1+1;endendf1=1;end%對(duì)篩選結(jié)果的處理T2=T1(:,2:6);%過渡矩陣2，提取T1的2-6列Gn=zeros(N,N);%Gn中的每一行即為一個(gè)子集%自該子集中的任一狀態(tài)出發(fā)，經(jīng)一步必轉(zhuǎn)移到下一個(gè)子集f2=1;forp=1:N-1Gn(p,f2)=p;forq=p+1:Nifismember(T2(q,:),T2(p,:))==1|ismember(T2(p,:),T2(q,:)