马尔可夫链状态空间的分解（实验报告+源代码）.docx-资料库

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第1页.png

第1页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第2页.png

第2页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第3页.png

第3页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第4页.png

第4页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第5页.png

第5页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第6页.png

第6页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第7页.png

第7页 / 共9页

qq_38144634-10635547-92080cef3ad0986c12a9d99399488e54.docx.pdf-第8页.png

第8页 / 共9页

马尔可夫链状态空间的分解一、实验内容生成一个状态个数大于 100 的马尔可夫链，状态之间的转移关系随机设定（例如某状态可以一步到达其他状态的比例为 10%） 1）将状态空间按常返性和互通性进行分解 2）在 1）的基础上对周期不可约马尔可夫链进行分解二、理论基础设 C 为状态空间 I 的非空子集，若对任意 Ci  及 Ck  都有 0ikp ，则称 C 为（随机）闭集，若 C 中所有状态是互通的，称 C 是不可约的闭集。若马尔可夫链 } { nX 的状态空间 I 是不可约的闭集，则称 } { nX 为不可约的马尔可夫链。 1. 按常返性和互通性进行状态空间的分解任一马尔可夫链的状态空间 I，可唯一地分解成有限个或可列个不相交的集 D，C1，C2，……之和，使得 1）每一 Cn，n=1，2，…是常返态组成的不可约闭集； 2）Cn，n=1，2，…中的状态同类，即或全是正常返，或全是零常返，它们有相同的周期，且 1ikf , nCkj , ; 3）D 是由全体非常返状态组成，自 Cn 中的状态不能到达 D 中的状态。 2. 按对周期不可约马尔可夫链进行分解周期为 d 的不可约马氏链，其状态空间 C 可唯一地分解为 d 个互不相交的子集之和，即 C 1 d   0  r GGG  , , r r r s s 且使自 Gr 中任一状态出发，经一步必转移进入 Gr+1 中（其中 Gd=G0）。三、具体步骤 1. 按常返性和互通性进行状态空间的分解 1）生成马尔可夫链的转移矩阵 P，即生成 100*100 的随机矩阵，行向量元素之和为 1；

2）筛选出吸收态，即为单点闭集，存储在 C1 中的行向量中； 3）筛选出各状态所有的可能路径，路径不重复，每一条路径只返回第一个状态，不返回中间状态，存储在 T1 中； 4）从 T1 中提取可能的常返闭集，（不包括单点闭集），即在 T1 的路径中筛选出首尾相同状态的路径，存储在 T2 中；

5）从 T2 中筛选出真正的常返闭集，自该闭集的内部不能到达它的外部，存储在 Cn 的行向量中； 6）根据 C1 和 Cn，去掉状态空间所有的常返态，即为全体非常返态，存储在 D 中。 2. 按对周期不可约马尔可夫链进行分解 1）以教材例 4.14 生成不可分马尔可夫链的转移矩阵 P，其状态空间 C= （1,2,3,4,5,6）；

2）筛选出每一状态能一步到达的状态，从 T1 的第二列开始存储； 3）提取 T1 的 2-6 列为 T2，筛选出相同的行向量，或是有从属于关系的行向量，然后返回它们所在行，即为一个子集（自这些子集中的任一状态出发，经一步必转移到下一个子集），存储在 Gn 的行向量中；四、结论程序基本满足实验要求，按常返性和互通性可将马尔可夫链的状态空间分解为 nCCDI  U 1 U ，其中 1C 的每一个行向量都是一个吸收态， nC 的每一个行向量是由常返状态组成的不可约的闭集，D 为非常返状态全体；按周期对不可约的马尔可夫链进行分解为 U GGC  1 2 U ... ，自 rG 中的任一状态出发，经一步转移必进入 1rG 中。五、分析总结尽管程序已基本完成实验内容，但还是有一些不尽人意的地方，还存在如下问题： 1）生成 100*100 的 0,1 随机矩阵时，我为了使后面观察效果更明显，设置了 1 出现的概率小于 5%，这有极小的可能导致转移矩阵某一行全为 0，从而使

得生成的转移矩阵不满足要求； 2）顺序遍历各状态的可能的不重复路径时，由于算法限制，极小可能不能全部遍历完所有的路径，尚未解决这个问题； 3）从可能的常返闭集中提取真正的 Cn 时，其中对矩阵的处理很多，尚未找到更简便的方法； 4）因为状态较多，并且由于随机矩阵导致状态之间的转移错综复杂，极大可能 100 个状态中没有一个基本常返闭集，为了更好的检验算法的正确性，对转移矩阵做了特殊化处理。六、附录 1. 将状态空间按常返性和互通性进行分解 clear all; clc; I=(1:100); %指定状态空间 %生成 100*100 的随机矩阵，行向量元素之和为 1，即为马尔可夫链的转移矩阵 N=100; A=rand(N,N)<0.05; a=sum(A,2); A=A+zeros(N,N); for k=1:N %设置矩阵中出现逻辑 1 的概率小于 5% %计算矩阵行向量元素之和 %将矩阵中的逻辑 1 转换为数值 1 %使矩阵行向量元素之和为 1 A(k,:)=A(k,:)/a(k); %常返闭集（10,30,50,70,90） %P 为转移矩阵 %单点闭集（2） %单点闭集（2） %常返闭集（1,3,5,7,9） end P=A; %验证是否达到效果,举特例观察 P(2,:)=0; P(2,2)=1; P(4,:)=0; P(4,4)=1; P(1,:)=0; P(3,:)=0; P(5,:)=0; P(1,3)=1; P(3,5)=1; P(5,1)=1; P(10,:)=0; 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); C1=zeros(N,1); f1=0; f2=1; f3=1; R=1; for i=1:N; for j=1:N; %过度矩阵 1，存储各状态所有的可能路径 %(路径不重复，只返回第一个状态，不返回中间状态） %单点闭集，存储所有吸收态 if P(i,j)==1&&(i==j) %在单点闭集中存储所有的吸收态 C1(f2,1)=i; f2=f2+1; end if P(i,j)>0&&f1==0&&(i~=j) %在过渡矩阵中存储该状态到达其他状态的起始链，只用一次 T1(R,f3)=i; f3=f3+1; T1(R,f3)=j; f1=1; end if f1==1 for l=1:N; for k=1:N; if (P(l,k)>0)&&(T1(R,f3)==l)&&(l~=k)&&T1(R,f3+1)==0 %从该状态能够到达其他状态的情况 %若能够到达则进行存储 f3=f3+1; T1(R,f3)=k; end end

end f1=0; f3=1; R=R+1; end end end %找出常返和非常返,并分类 f4=1; T2=zeros(N,N); %过渡矩阵 2，用来存储可能的常返闭集（不包括单点闭集） for p=1:N*10 for q=1:N if T1(p,1)==T1(p,q)&&T1(p,q+1)==0&&q~=1 %从 T1 中提取可能的常返 T2(f4,:)=T1(p,:); f4=f4+1; break; end 闭集 end end T3=T2(1:N,:); T4=zeros(N,N); %过渡矩阵 3，用来将 T2 转变为 N*N 的矩阵，减少计算量 %过渡矩阵 4 count=0; f5=1; a1=0; for p=1:N for q=2:N m=T3(p,q); n=length(nonzeros(T3(p,:))); if m~=0 for k=1:N if (ismember(k,T3(p,:))==0)&&(P(m,k)==0)&&(count==0) %从 T3 中提取基本常返闭集 a1=a1+1; if a1==N-n+1 count=1; end end

end end if count==1 T4(f5,:)= T3(p,:); f5=f5+1; count=0; a1=0; end end end [T5,b]=unique(T4,'rows'); T6=sortrows([b,T5]); T7=T6(:,2:N+1); [row,col]=size(T6); f6=1; Cn=zeros(N,N); %过度矩阵 5,6,7 %Cn 的每一行即为一个常返闭集 for k=1:row-1 if (T6(k+1,1)-T6(k,1))>1 Cn(f6,:) =T7(k,:); f6=f6+1; end end T8=unique(nonzeros(Cn)); T9=setdiff(I,T8); D=setdiff(T9,C1); %去掉状态空间所有的常返态，即为全体非常返态 disp('C1 的行向量为吸收态，Cn 的行向量即为一个常返闭集，D 由全体非常返态组成'); 2. 对周期的不可约马尔可夫链进行分解 clear all; 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 为不可分马尔可夫链的转移矩阵，C 为其状态空间 N=6; T1=zeros(N,N); f1=1; a1=0; %过渡矩阵，用来存储某状态经一步转移能进入的状态

资料库

马尔可夫链状态空间的分解（实验报告+源代码）.docx

相关推荐

课程资源

热门标签

最新资料