随机过程与排队论09

随机过程与排队论计算机科学与工程学院顾小丰Email：[e-mail]2019年12月14日星期六2019/12/14计算机科学与工程学院顾小丰30－2上一讲内容回顾离散参数马氏链•齐次马氏链的性质链•初始分布、绝对分布、极限分布•遍历性•平稳性2019/12/14计算机科学与工程学院顾小丰30－3本讲主要内容齐次马氏链状态的分类•互通首达•常返与非常返•正常返与零常返•状态空间分解•不可约马氏链•状态的周期性2019/12/14计算机科学与工程学院顾小丰30－4§3.3齐次马氏链状态的分类一、互通首达如果存在某一个n≥1，使得pij(n)＞0，i,jE，则称从状态i可到达状态j，记为i→j；否则称状态i不能到达状态j，记为i→j，此时对一切n，均有pij(n)＝0。如果i→j且j→i，则称状态i和j互通，或称相通，记为i↔j。容易证明，互通关系具有以下三个性质：(1)自反性：i↔i；(2)对称性：若i↔j则j↔i；(3)传递性：若i↔j且j↔k，则i↔k。2019/12/14计算机科学与工程学院顾小丰30－5首达从状态i出发经过n步首次到达状态j的时刻Tij＝min{n：X(m)=i,X(m+n)=j,nN}称为首达时刻。首达时刻是一个随机变量，它的取值是从状态i出发，使得X(n)＝j的最小正整数n。自状态i出发经过n步首次到达状态j的概率fij(n)＝P{Tij=n|X(m)=i}＝P{X(m+n)=j,X(m+k)j,1kn|X(m)=i}称为首达概率。自状态i出发迟早(最终)到达状态j的概率定义为}T{P}i)m(X|nT{P)n(ffij1nij1nijij2019/12/14计算机科学与工程学院顾小丰30－6返回当j＝i时Tii：表示从状态i出发首次返回i的时刻；fii(n)：表示从状态i出发经过n步首次返回i的概率；fii：表示从状态i出发迟早返回i的概率。1nijijij)n(nf)T(E称为自状态i出发首次到达j的平均时间(平均步数)；1niiiiiii)n(nf)T(E称为自状态i出发首次到达i的平均返回时间(平均返回步数)；2019/12/14计算机科学与工程学院顾小丰30－7定理1对任意i,jE及n1，有n1mjjijij)mn(p)m(f)n(p证明设系统从状态i出发经n步到达状态j，则Tijn，pij(n)＝P{X(n)＝j|X(0)=i}}i)0(Xj)n(X),mT({Pijn1mn1mij}i)0(Xj)n(X,mT{Pn1mijij}mT,i)0(Xj)n(X{P}i)0(XmT{Pn1mij,i)0(Xj)n(X{P}i)0(XmT{P}j)m(X,j)1m(X,,j)2(X,j)1(Xn1mij}j)m(Xj)n(X{P}i)0(XmT{Pn1mjjij)mn(p)m(f2019/12/14计算机科学与工程学院顾小丰30－8定理2fij＞0i→j证明)设fij＞0，因为，所以至少有一个n≥1，使得fij(n)＞0，由定理1得1nijij)n(ff0)n(f)0(p)n(f)mn(p)m(f)n(pijjjijn1mjjijij故i→j。)设i→j，则存在n≥1，使得pij(n)＞0，由定理1得,0)mn(p)m(f)n(pn1mjjijij从而fij(1),fij(2),…,fij(n)中至少有一个大于0，所以0)m(ff1mijij2019/12/14计算机科学与工程学院顾小丰30－9推论i↔jfij＞0且fij＞02019/12/14计算机科学与工程学院顾小丰30－101)状态j常返的充分必要条件是；二、常返如果fii＝1，则称状态i是常返状态；如果fii＜1，则称状态i是非常返状态，或瞬时状态。判别常返状态的准则：1jjj)n(p1jjj)n(p0)n(plimjjn2)状态j非常返的充分必要条件是；3)若状态j是非常返的，则。2019/12/14计算机科学与工程学院顾小丰30－11返回的次数定义随机变量j)n(X,0j)n(X,1)n(Y则随机变量1n)n(YY表示质点到达状态j的次数，有]j)0(X|)n(Y[E]j)0(X|Y[E1n1njj1n1n)n(p}j)0(X|j)n(X{P]j)0(X|)n(Y[E由此可知，1njj)n(p表示由j出发再返回j的平均次数。当j是常返状态时，返回j的次数是无穷多次；当j是非常返状态时，返回j的次数只能是有限多次。2019/12/14计算机科学与工程学院顾小丰30－12正常返与零常返设i是常返状态，fii＝1，1)如果，称状态i是一个正常返状态；2)如果，称状态i是一个零常返状态，或消极常返状态。1niii)n(nf1niii)n(nf平均返回时间有限平均返回时间无限2019/12/14计算机科学与工程学院顾小丰30－13定理1)设i是常返状态，则i是零常返的充分必要条件是0)n(plimiin；如果j也是零常返状态，则。0)n(plimijn2)如果i↔j，则它们同为常返或非常返；如果它们均为常返时，则它们同为正常返或零常返。归纳1)i是非常返2)i是零常返3)i是正常返；，此时0)n(plim)n(piin1nii；，且0)n(plim)n(piin1nii。，且0)n(plim)n(piin1nii2019/12/14计算机科学与工程学院顾小丰30－14三、状态空间分解设C是状态空间E的一个子集，若C外的任一状态不可能从C内的任一状态到达，即对任意的iC,jC，总有pij(n)＝0，则称C为一个闭集。重要结论：1)整个状态空间E是最大的闭集；2)pii＝1的状态i称为吸收状态。任何一个吸收状态构成最小的单点闭集。3)所有常返状态构成一个闭集；4)状态空间E必可分解为E＝N＋C1＋C2＋…＋Ck＋…其中N为非常返状态集合，C1,C2,…,Ck,…是互不相交的常返闭集。这里的“＋”即为集合的并“∪”且两两互不相容2019/12/14计算机科学与工程学院顾小丰30－15不可约马氏链一个马氏链，如果除了整个状态空间E构成闭集外，不可能再分解出较小的闭集来，则称此马氏链为不可约马氏链。结论：1)马氏链为不可约马氏链的充分必要条件是任何两个状态都相通；2)一个不可约马氏链，或者没有非常返状态，或者没有常返状态。3)不可约马氏链是常返的充分必要条件是方程Ei,ypy1jjiji没有非零的有界解。2019/12/14计算机科学与工程学院顾小丰30－16四、有限马尔可夫链状态空间E是有限集合的马氏链称为有限马氏链。有限马氏链具有如下特点：1)所有非常返状态所组成的集合不可能是闭集；2)没有零常返状态；3)必有正常返状态；4)状态空间E必可分解为E＝N＋C1＋C2＋…＋Ck其中，N为非常返状态集合，C1,C2,…,Ck是互不相交的常返闭集。2019/12/14计算机科学与工程学院顾小丰30－17五、状态的周期性称d＝GCD{n：pii(n)＞0}为状态i的周期。这里，GCD表示最大公约数。如果i有周期d＞1，则只有n＝d,2d,…,kd(k为正整数)时，pii(n)＞0；否则，当n不能被d整除时，pii(n)＝0。如果不存在大于1的d，则称状态i是非周期的，记为d=1。对于不可约马氏链，若pii＞0，则此马氏链是非周期的。结论：1)如果i↔j，则状态i和j或者有相同的周期，或者都是非周期的；2)如果C是一个常返闭集，则C中的每一个状态或者都是非周期的，或者都是同周期的；3)如果马氏链是不可约常返链，那么只要有一个是周期为d(d＞1)的状态，则状态空间E都是周期为d的状态。2019/12/14计算机科学与工程学院顾小丰30－18六、极限定理1)如果j是一个非周期常返状态，则ijjijnf1)n(plim2)如果马氏链是不可约非周期常返链，则jijn1)n(plim其中j＝E(Tjj)。由此定理知：1)不可约非周期正常返状态的齐次马氏链是遍历马氏链。即Ej,i,0)n(plimjijn且满足：i)j＝1/j；ii)极限分布{j,jE}是马氏链唯一的平稳分布，且Ej,)n(plimjjn。即绝对分布的极限是平稳分布.2)不可约非周期常返链是遍历链的充分必要条件是存在平稳分布{1/j,jE}，即极限分布。3)不可约非周期有限马氏链必存在平稳分布，且平稳分布就是极限分布。2019/12/14计算机科学与工程学院顾小丰30－19例1两个吸收壁的随机游动状态空间E＝{1,2,3,4}状态转移矩阵1qp1p01000p0q00p0q0001P状态转移图12341qpqp1以状态为结点，以状态转移概率为有向边的权值得到的赋权有向图。2019/12/14计算机科学与工程学院顾小丰30－20例1(续)p11＝1，f11(1)＝1，f11(n)＝0(n1)，f11＝1，1＝1，故状态1为吸收状态、正常返状态；p44＝1，f44(1)＝1，f44(n)＝0(n1)，f44＝1，4＝1，故状态4为吸收状态、正常返状态；p22＝0，f22(1)＝0，f22(2)＝pq，f22(n)＝0(n2)，f22＝pq，故状态2为非常返状态。状态2和3互通，2↔3，具有相同的状态性质，即状态3也为非常返状态。从而N＝{2,3}为非常返集；C1＝{1}、C2＝{4}都为正常返集。状态空间分解为E＝N＋C1＋C2即E＝{1,2,3,4}＝{2,3}＋{1}＋{4}2019/12/14计算机科学与工程学院顾小丰30－21例2设齐次马氏链的状态空间E＝{1,2,3,4}，0210210323100001002121P状态转移图1234121212131转移矩阵21322019/12/14计算机科学与工程学院顾小丰30－22例2(续1)由图可知，对一切n1，f44(n)＝0，从而1)n(ff1n4444，故状态4为非常返状态；f33(1)＝，f33(n)＝0(n1)，从而，故状态3非常返状态；32132)n(ff1n333312121)n(ff1n111123212211)n(nf1n1111121210)n(ff21n2222321n21321201)n(nf1n21n2222019/12/14计算机科学与工程学院顾小丰30－23例2(续2)故状态1和2都是正常返状态，又d＝1，故都是遍历态。状态空间分解为E＝N＋C其中N＝{3,4}为非常返集；C1＝{1,2}为正常返闭集。非周期正常返状态2019/12/14计算机科学与工程学院顾小丰30－24例3设齐次马氏链的状态空间E＝{0,1,2,…}，转移概率为2100021021002100210210002121P状态转移图转移矩阵Ei,21p,21p0i1i,i0123…2121212121212121212019/12/14计算机科学与工程学院顾小丰30－25例3(续)对状态0,21)n(f,,21)2(f,21)1(fn0020000121)n(ff1nn1n00002)211(2121n)n(nf21nn1n000021p)1(p0000故状态0为非周期、正常返、遍历状态