第十一章马尔科夫链

1、第十一章第十一章 马尔科夫链马尔科夫链11.1 马尔科夫过程及其概率分布马尔科夫过程及其概率分布1. 马尔科夫过程马尔科夫过程 若随机过程若随机过程X(t), t T对于任意的正整数对于任意的正整数n及及 t1 1 t2 2tn T, 其条件分布满足其条件分布满足 PX (tn) xn| X(t1 1) = x1 1, X(tn-1-1) = xn-1-1 = PX (tn) xn| X(tn-1-1) = xn-1-1, xn R 或写成或写成);|,( ),.,;,.,|,(111|1211211.|1 nnnnnttnnnnnttttxtxFtttxxxtxFnn 则称随机过程则称随机过

2、程X(t), t T 为为马尔科夫过马尔科夫过程程. 2. 马尔科夫链马尔科夫链 时间和状态都是离散的马尔科夫过称时间和状态都是离散的马尔科夫过称为为马尔科夫链马尔科夫链，简称马氏链，简称马氏链. 记为记为 Xn=X(n)，n = 0,1,2,. 它可以看作在时间集它可以看作在时间集T1 = 0,1,2, 上的离上的离散状态的马氏过程相继观察的结果散状态的马氏过程相继观察的结果. 链的状态空间：链的状态空间：I = a1 1 ,a2 2 , , ai i R.3. 转移概率转移概率 对任意得正整数对任意得正整数n, r和和0t1 1 t2 2 tr m; ti , m, n+m T1 1有有

3、其中其中ai I. 则称条件概率则称条件概率 Pij(m,m+n) = PXm+n = aj |Xm = ai 为马氏链在时刻为马氏链在时刻m, 处于状态处于状态ai条件下，在时刻条件下，在时刻 m+n转移到状态转移到状态aj的的转移概率转移概率.,| ,|2211imjnmimitititjnmaXaXPaXaXaXaXaXPrr 4. 转移概率矩阵转移概率矩阵 由转移概率组成的矩阵由转移概率组成的矩阵 称为马氏链的称为马氏链的转移概率矩阵转移概率矩阵. 此矩阵的每此矩阵的每一行元素之和等于一行元素之和等于1. 当转移概率当转移概率Pij(m,m+n)只与只与i, j及时间距及时间距n有关时

4、，把它记为有关时，把它记为Pij(n), 即即 并称转移概率具有并称转移概率具有平稳性平稳性，同时也称此链，同时也称此链 是是齐次的或时齐的齐次的或时齐的.)(),(nPnmmPijij ),(),(nmmPnmmPij 5. n步转移概率和步转移概率和n步转移矩阵步转移矩阵 n步转移概率步转移概率 : n步转移概率矩阵步转移概率矩阵: 一步转移概率一步转移概率: 一步转移概率矩阵一步转移概率矩阵 : |)(imjnmijaXaXPnP )()(nPnPij imjmijijaXaXPPp 1)1(的的状状态态1 mXp1111p1212p1j1jp2121p2222p2j2jpi1i1pi2

5、i2pijija1 1 a2 2 aj j a1 1 a2 2 . .ai i .态态状状的的mX.) 1 (PP 例例1. （0-1传输系统）传输系统）在如下图只传输数字在如下图只传输数字0和和1的串联系统中，的串联系统中，1.设每一级的传真率为设每一级的传真率为p，误码率为，误码率为q = 1-p（输出与输入数字（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）相同的概率称为系统的传真率，相反情形称为误码率）;2.设一个单位时间传输一级设一个单位时间传输一级, X0 0是第一级的输入，是第一级的输入，Xn n是第是第n级级的输出的输出(n1), 那么那么 是一随机过程是一随机

6、过程.3.状态空间状态空间I=0,1，而且当，而且当Xn n=i , iI为已知时，为已知时， Xn+1n+1所处所处的状态的概率分布只的状态的概率分布只与与Xn n= i有关，而与时刻有关，而与时刻n以前所处的以前所处的状态无关，所以它是一个马氏链，而且还是齐次的状态无关，所以它是一个马氏链，而且还是齐次的. 它的它的一步转移概率和一步转移概率矩阵分别为一步转移概率和一步转移概率矩阵分别为 ,.2,1 ,0, nXn12nX0 0X1 1Xn nX2 2Xn-1n-1 和和 例例2 一维随机游动一维随机游动 设一醉汉设一醉汉Q在如下图点集在如下图点集I=1,2,3,4,5上上作随机游动，并且

7、仅仅在作随机游动，并且仅仅在1秒、秒、2秒秒等时刻发生游动等时刻发生游动.规律是：规律是：(1) 如果如果Q现在位于点现在位于点i(1i5), 则下一时刻各以则下一时刻各以1/3的概率向左的概率向左或向右移动一格，或以或向右移动一格，或以1/3的概率留在原处；的概率留在原处； (2) 如果如果Q现在位于现在位于1（或（或5）这点上，则下一时刻就以概率）这点上，则下一时刻就以概率1移移动动2（或（或4）这一点上）这一点上. 1和和5这两点称为这两点称为反射壁反射壁. 上面这种游动上面这种游动称为称为带有两个反射壁的随机游动带有两个反射壁的随机游动. 1 ,0, ,1 jiijqijpiXjXpp

8、nnij pqqpp100 1 2 , 0, 4, 52, 1 , 1, 51 , 1, 1,31|1ijjijiiiiijiXjXPpnnij或或 若以若以Xn表示时刻表示时刻n时时Q的位置，不同的位置就是的位置，不同的位置就是Xn的不同状的不同状态，那么态，那么 Xn , n=0,1,2,是一随机过程，状态空间就是是一随机过程，状态空间就是I，而且而且Xn=i, i I为已知时，为已知时， Xn+1+1所处的状态的概率分布只与所处的状态的概率分布只与Xn= i 有关，而与有关，而与Q在时刻在时刻n以前如何达到是完全无关的，所以前如何达到是完全无关的，所以以 Xn , n = 0,1,2,

9、是一马氏链，而且还是齐次的，它的是一马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为一步转移概率和一步转移概率矩阵分别为 如果把一这一点改为吸收壁，即是说如果把一这一点改为吸收壁，即是说Q一旦到达一旦到达1这一这一点，则就永远留在点一上，相应链的转移概率矩阵只点，则就永远留在点一上，相应链的转移概率矩阵只须把须把p中的第一横行改为（中的第一横行改为（1，0，0，0，0）. 总之改变总之改变游动的概率规则，就可得到不同方式的随机游动和相游动的概率规则，就可得到不同方式的随机游动和相应的马氏链应的马氏链. 随机游动的思想在数值计算方法方面有重要应用随机游动的思想在数值计算方法方面有

10、重要应用.010001/31/31/30001/31/31/30001/31/31/3000101 2 3 4 512345例例3 排队模型排队模型 服务系统组成服务系统组成：服务员（：服务员（1个）个）, 等候室（等候室（2人）人）.服务规则服务规则：先到先服务：先到先服务. 假定一顾客到达系统时发现系统假定一顾客到达系统时发现系统内已有内已有3个顾客，则该顾客即离去个顾客，则该顾客即离去.1.设时间间隔设时间间隔t内，有一个顾客进入系统的概率为内，有一个顾客进入系统的概率为q，有一，有一原来被服务的顾客离开系统的概率为原来被服务的顾客离开系统的概率为p.2.设当设当t充分小时，在这个时间间

11、隔内多于一个顾客进入或充分小时，在这个时间间隔内多于一个顾客进入或离开系统实际上是不可能的离开系统实际上是不可能的.3.设有无顾客来到与服务是否完毕是相互独立的设有无顾客来到与服务是否完毕是相互独立的.等候室服务台随机到达者离去者系 统 设设Xn = X(nt )表示时刻表示时刻 nt 时系统内的顾客数，即系统的状时系统内的顾客数，即系统的状态态. 是一随机过程，状态空间是一随机过程，状态空间I=0,1,2,3 ，由前例的分析，由前例的分析, 可知它是一个齐次马氏链可知它是一个齐次马氏链. 下面下面来计算此马氏链的一步转移概率来计算此马氏链的一步转移概率. p00 00 表示在系统内没有顾客的

12、条件下，经表示在系统内没有顾客的条件下，经t 后仍没有顾客后仍没有顾客的概率（此处是条件概率，以下同）的概率（此处是条件概率，以下同） p0000 = 1- -q. p01 01 表示在系统内没有顾客的条件下，经表示在系统内没有顾客的条件下，经t 后有一顾客进后有一顾客进入系统的概率，入系统的概率，p0101 = q. p10 10 系统内恰有一个顾客正在接受服务的条件下，经系统内恰有一个顾客正在接受服务的条件下，经t 后后 .,2 , 1 ,0, nXn 系统内无人的概率，它等于在系统内无人的概率，它等于在t 间隔内顾客因服务完毕而间隔内顾客因服务完毕而离去离去 ，且无人进入系统的概率，且无

13、人进入系统的概率，p1010 = p(1 q) p1111系统内恰有一顾客的条件下，在系统内恰有一顾客的条件下，在t 间隔内，他因服务间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率，顾客将继续要求服务，且无人进入系统的概率， p1111 = pq + (1-p)(1-q). p1212 正在接受服务的顾客继续要求服务，且另一个顾客进正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率入系统的概率, p1212 = (1-p)q. p1313正在接受服务的顾客继续要求服务，且在正在

14、接受服务的顾客继续要求服务，且在t 间隔内有间隔内有两个顾客进入系统的概率两个顾客进入系统的概率 ，由假设，后者实际上是不可能，由假设，后者实际上是不可能发生的，发生的， p1313 =0.类似地，有类似地，有p2121 = p3232 = p(1-q), p2222 = pq + (1-p)(1-q) , p2323 = q(1-p), pij = 0, (|i-j |2).p3333 : : 或者一人将离去且另一人将进入系统，或者无人离开或者一人将离去且另一人将进入系统，或者无人离开的概率，的概率， p3333 = pq + (1-p).于是该马氏链的一步转移概率矩阵为于是该马氏链的一步转

15、移概率矩阵为 1-qq00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p) 在实际问题中，一步转移概率通常可通过统计实验确定在实际问题中，一步转移概率通常可通过统计实验确定. 例例4 某计算机机房的一台计算机经常出故障，研究者每某计算机机房的一台计算机经常出故障，研究者每隔隔15分钟观察一次计算机的运行状态，收集了分钟观察一次计算机的运行状态，收集了24小时的数据小时的数据(共作共作97次观察次观察). 用用1表示正常状态，用表示正常状态，用0表示不正常状态，表示不正常状态，所得的数据序列如下：

16、所得的数据序列如下： 1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111 设设Xn为第为第n (n =1,2,97)个时段的计算机状态，可以认为它个时段的计算机状态，可以认为它是一个马氏链，状态空间是一个马氏链，状态空间I=0, 1. 96次状态转移的情况是：次状态转移的情况是： 0 0, 80 0, 8次；次； 0 1, 180 1, 18次；次； 1 0, 181 0, 18次次; 1 1, 52; 1 1, 52次次. . 因此，一步转移概率可用

17、频率近似地表示为因此，一步转移概率可用频率近似地表示为 ,268188800100 nnXXPp ,26181881801101 nnXXPp ,701852181810110 nnXXPp .705252185211111 nnXXPp6.齐次马氏链的有限维分布齐次马氏链的有限维分布. 马氏链的初始分布为马氏链的初始分布为: 1) 马氏链在任一时刻马氏链在任一时刻 n T1 1 的一维分布：的一维分布：显然，应有显然，应有 由全概率公式得由全概率公式得即即 .1)(1 npjj, |100 iijnijnaXaXPaXPaXP,2,1 ),()0()(1 jnPpnpijiij,2, 1 ,

18、 ,)0(0 jIaaXPpjjj,2, 1 , ,)( jIaaXPnpjjnj一维分布也可用行向量表示成一维分布也可用行向量表示成p(n) = ( p1 1(n), p2 2(n),pj j(n),)这样，利用矩阵乘法（这样，利用矩阵乘法（I是可列无限集时，仍用有限阶）矩是可列无限集时，仍用有限阶）矩阵乘法的规则确定矩阵之积的元素，可写成阵乘法的规则确定矩阵之积的元素，可写成p(n) = p(0)P(n) (矩阵矩阵)结论结论：马氏链在任一时刻：马氏链在任一时刻 n T1 1 时的一维分布由初始分布时的一维分布由初始分布 p(0) 和和 n 步转移概率矩阵所确定步转移概率矩阵所确定. 对于

19、任意对于任意 n 个时刻个时刻 t1 1t2 2 t tn, ti T1 1以及状态以及状态 有：有： 2)马氏链的马氏链的 n维分布维分布：,.,21Iaaaniii 由乘法公式由乘法公式,2211nnitititaXaXaXP )()()(| |,| 1121121111112211112211 nniiiiiitiiitititititititttPttPtpaXaXPaXaXPaXPaXaXaXaXPnnnnnnnnnn结论结论：由此可知，马氏链的有限维分布同样完全由初始分：由此可知，马氏链的有限维分布同样完全由初始分布和转移概率确定布和转移概率确定.总之总之,转移概率决定了马氏链的统

20、计规律转移概率决定了马氏链的统计规律. 因此因此,确定马氏链确定马氏链的任意的任意n步转移概率就成为马氏链理论中的重要问题之一步转移概率就成为马氏链理论中的重要问题之一.,2211nnitititaXaXaXP |112211itititaXaXPaXP 例例5（续例（续例4）若计算机在前一段（）若计算机在前一段（15分钟）的状态为分钟）的状态为0，问从时段起此计算机能连续正常工作一小时（问从时段起此计算机能连续正常工作一小时（4个时段）的个时段）的概率为多少？概率为多少？ 解解 由题意，前一时段的状态为由题意，前一时段的状态为0就是初始分布就是初始分布 p0 0(0) =PX0 0= 0=1

21、. 计算机能连续正常工作计算机能连续正常工作4个时段的概率为个时段的概率为 PX0 0 = 0, X1 1= 1, X2 2 = 1, X3 3 = 1, X4 4 = 1 = PX0 0 = 0PX1 1= 1| X0 0 = 0PX2 2 = 1| X1 1= 1 PX3 3 = 1| X2 2 = 1PX4 4 = 1| X3 3 = 1 = p0 0 (0) P0101 (1) P1111 (1) P1111 (1) P1111 (1) .284.070527052705226181 11.2 多步转移概率的确定多步转移概率的确定 为了确定齐次马氏链的为了确定齐次马氏链的 n 步转移概

22、率步转移概率 首先介绍首先介绍 所满足的基本方程所满足的基本方程. 设设X(n), n T1 1是一齐次马氏链，则对任意的是一齐次马氏链，则对任意的u,v T1 1 ,有有 这就是著名的切普曼这就是著名的切普曼-柯莫哥洛夫柯莫哥洛夫 (Chapman-Kolmogorov)方程，简称方程，简称C-K方程方程.),(nPij)1 . 2( 2 , 1, ),()()(1 jivPuPvuPkjkikij)(nPijC-K方程的实际背景方程的实际背景 C-K方程基于下述事实，即方程基于下述事实，即“从时刻从时刻 s 所处的状态所处的状态 ai，即即 X (s) = ai 出发，经时段出发，经时段

23、u + v 转移转移 到状态到状态 aj , 即即 X(s + u + v) = aj”这一事件可分解成这一事件可分解成“从从X(s) = ai”出发，出发，先经时段先经时段 u 转移到中间状态转移到中间状态 ak k(k = 1,2)，再从，再从 ak 经经时段时段 v 转移转移 到状态到状态 aj”这样一些事件的和事件这样一些事件的和事件.(如下图如下图)aiajOss+us+u+vt 方程（方程（2.1）的证明如下：先固定）的证明如下：先固定 和和 由于事件组由于事件组“X(s + u) = ak”, k = 1,2,构成一划分构成一划分,故有故有 Pij(u+v) = PX(s+u+v

24、)= aj|X(s)=ai又由条件概率定义和乘法定理，有又由条件概率定义和乘法定理，有 (马氏链的齐次性马氏链的齐次性) 将上式代入将上式代入(2.2) ，即得所要证明的，即得所要证明的 C-K 方程方程. ikjasXausXavusXP )()(,)( ).()()(,)()()()(vPuPasXausXavusXPasXausXPkjikikjik Iak 1Ts C-K方程的证明方程的证明(2.2) ,)(|)(,)(1ikjkasXausXavusXP C-K方程也可写成矩阵形式：方程也可写成矩阵形式：P(u+v) = P(u)P (v) 利用利用C-K方程我们容易确定方程我们容易

25、确定 n 步转移概率步转移概率, 事实上事实上, 在在(2.1)式式中令中令u = 1, v = n- -1，得递推关系：，得递推关系： P(n)= P(1) P(n- -1) =P P(n- -1), 从而可得从而可得 P(n)= Pn, 就是说，对齐次马氏链而言，就是说，对齐次马氏链而言， n步转移概率矩阵是步转移概率矩阵是一一步转移步转移概率矩阵的概率矩阵的 n 次方次方. 进而可知，齐次马氏链的有限维分布可进而可知，齐次马氏链的有限维分布可由初始分布与由初始分布与一一步转移概率完全确定步转移概率完全确定. 例例1 设设Xn,n0是具有三个状态是具有三个状态0, 1, 2的齐次马氏链，的

26、齐次马氏链，一一步步转移概率矩阵为转移概率矩阵为 初始分布初始分布pi(0) = PX0 0 = i = 1/3, i = 0,1,2. 试求试求 (i) PX0 0 = 0, X2 2 = 1; (ii) PX2 2 = 1 解解 先求出二步转移概率矩阵先求出二步转移概率矩阵于是于是(i) PX0 0= 0 ,X2 2=1 = PX0 0=0 PX2 2=1| X0 0=0 = p0 0(0) P0101(2)0120123/41/401/41/21/403/41/4P=0 1 25/85/161/165/161/23/63/169/161/4P(2) = P2 =0 1 2.4851653

27、1 3/4 1/401/4 1/2 1/403/4 1/43/4 1/401/4 1/2 1/403/4 1/4=(ii) 由由(1.7)式，式，p1 1(2) = PX2 2=1 = p0 0(0) P0101(2) + p1 1(0)P1111(2) + p2 2(0) P2121(2) = 例例2 在在1例例2中中, (i) 设设 p = 0.9, 求系统二级传输后的传真率求系统二级传输后的传真率与三级传输后的误码率；与三级传输后的误码率； (ii) 设初始分布设初始分布 p1 1(0) = PX0 0 = 1 = , p0 0 (0) = P X0 0 = 0 = 1 - ，又已知系统

28、经，又已知系统经 n 级传输后级传输后输出为输出为 1，问原发字符也是，问原发字符也是1的概率是多少？的概率是多少？ 解解 先求出先求出n步转移概率矩阵步转移概率矩阵P(n) = Pn . 由于由于 则令则令 得得 1 1 = 1， 2 2 = p- -q 则可将则可将P表示成对角矩阵表示成对角矩阵 的相似矩阵的相似矩阵. 0124111692116531 P=0 1 qp001, 00 ,11 0| pqqpPE pqqp 求出求出1 1， 2 2 的特征向量是的特征向量是 方法是令方法是令(1 1E-P)X = 0及及(2 2E- -P)X = 0,就可以求得就可以求得 e1 1, e2

29、2 令令H=e1 1,e2 2 则有则有 2/12/11e 2/12/12e,2/ 12/ 12/ 12/ 1 2/12/12/12/10012/12/12/12/1)(11nnnnqpHHHHP 2/ 12/ 12/ 12/ 11H nnnnnnnqpqpqpqpqpqpqp)(2121)(2121)(2121)(21212/12/12/12/1)(2121)(21212/12/12/12/1)(0012/12/12/12/1(i) 由此可知，当由此可知，当 p = 0.9时，系统经二级传输后的传真率与时，系统经二级传输后的传真率与三级传输的误码率发表分别为三级传输的误码率发表分别为 P11

30、11(2) = P0000 (2) = P1010(3) = P0101(3) = (ii) 根据贝叶斯公式，当已知系统经根据贝叶斯公式，当已知系统经 n 级传输后输出为级传输后输出为1，原发字符也是原发字符也是1的概率为的概率为,820.0)1.09.0(21212 ;244.0)1 .09 .0(21213 111111000 nnnXPXXPXPXXPnnqpqpnPpnPpnPp)(12(1)()()0()()0()()0(111010111 对于只有两个状态的马氏链，一步转移概率矩阵一般可表示为：对于只有两个状态的马氏链，一步转移概率矩阵一般可表示为： 利用类似于例利用类似于例2的方

31、法，可得的方法，可得 n 步转移概率矩阵为步转移概率矩阵为 11.3 遍历性遍历性 对于一般的两个状态的马氏链，当对于一般的两个状态的马氏链，当0a, b1 时就可得到时就可得到 n 步转移概率步转移概率的近似值：的近似值： 遍历性和极限分布的意义遍历性和极限分布的意义：设齐次马氏链的状态空间为：设齐次马氏链的状态空间为 I , 如果对于所有如果对于所有ai ajI, 转移概率转移概率Pij (n)存在极限存在极限 (不依赖于不依赖于i)jp110 p pp pp pp pp p ),(10.)(jijnPp p jijnnPp p )(lim 则称此链具有则称此链具有遍历性遍历性，又若，又若

32、 则同时称则同时称 为链的为链的极限分布极限分布. 齐次马氏链在什么条件下才具有遍历性？齐次马氏链在什么条件下才具有遍历性？ 如何求出它的极限分布？如何求出它的极限分布？ 这问题在理论上已经完满解决，下面仅就只有有限个这问题在理论上已经完满解决，下面仅就只有有限个状态的链，即有限的遍历性给出一个充分条件状态的链，即有限的遍历性给出一个充分条件. .)(212121)(jjjnnPnPp pp pp pp pp pp pp pp pp p,1 jjp p,.),(21p pp pp p 定理定理 设齐次马氏链设齐次马氏链Xn,n 1的状态空间为的状态空间为I= a1 1, a2 2,aN , P

33、是它的一步转移概率矩阵，如果存在正整数是它的一步转移概率矩阵，如果存在正整数 m ，使对任意，使对任意的的ai i ,ajI，都有，都有 Pij(m) 0, i, j = 1, 2, , N, 则此链具有遍历性；且有极限分布则此链具有遍历性；且有极限分布 它是方程组它是方程组 = P 或即或即 的满足条件的满足条件 的唯一解的唯一解. 依照定理，为证有限链是遍历的，只需要找一正整数依照定理，为证有限链是遍历的，只需要找一正整数m，使，使m步转移概率矩阵步转移概率矩阵 Pm无零元无零元. 而求极限分布而求极限分布的问题，化为求的问题，化为求解方程组的问题解方程组的问题. 注意，方程组中仅注意，方

34、程组中仅N-1个未知数，是独立的，个未知数，是独立的，而唯一解可用归一条件而唯一解可用归一条件 确定确定.),(21Np pp pp pp p NjpijNiij, 2 , 1 ,1 p pp p1, 01 Njjjp pp p11 njjp p 在定理的条件下，马氏链的极限分布又是在定理的条件下，马氏链的极限分布又是平稳分布平稳分布.即，即，若用若用作为链的初始分布，即作为链的初始分布，即p(0) = , 则链在任一时刻则链在任一时刻n T1 1的分布的分布p(n)永远与永远与一致一致. 事实上事实上, 有有 p(n) = p(0)P(n) = Pn = Pn-1 = = P = 例例1 试

35、说明试说明 1例例2中，带有两个放射壁的随机游中，带有两个放射壁的随机游动是遍历的，并求其极限分布动是遍历的，并求其极限分布(平稳分布平稳分布). 解解 为简便计，以符号为简便计，以符号“”代表转移概率矩阵代表转移概率矩阵 的的正元素，于是，由正元素，于是，由 1例例2中的一步转移概率矩阵中的一步转移概率矩阵 P，得得 000000000000)4(0000000000000000000000000000000000)2(42PPPP 即即p(4)无零元无零元. 由定理，链是遍历的由定理，链是遍历的. 写出极限分布写出极限分布 = (1 1，2 2, 5)5)满足的方程组满足的方程组 先由前四

36、个方程，解得：先由前四个方程，解得： 将它们将它们代入归一条件，得唯一解：代入归一条件，得唯一解： 所以极限分布为所以极限分布为 = (1/11, 3/11, 3/11, 3/11, 1/11), 这个这个分布表明：经过长时间游动之后，醉汉分布表明：经过长时间游动之后，醉汉Q位于点位于点i(1i5)的概率约为的概率约为3/11, 位于点位于点1或或5的概率约为的概率约为1/11. .1,)3/1(,)3/1()3/1()3/1()3/1()3/1(,)3/1()3/1(,)3/1(54321455434,4323321221p pp pp pp pp pp pp pp pp pp pp pp

37、pp pp pp pp pp pp pp pp pp p,3354321p pp pp pp pp p .11/3 ,11/143251 p pp pp pp pp p11.1 例例3 排队模型排队模型 服务系统组成服务系统组成：服务员（：服务员（1个）个）, 等候室（等候室（2人）人）.服务规则服务规则：先到先服务：先到先服务. 假定一顾客到达系统时发现系统假定一顾客到达系统时发现系统内已有内已有3个顾客，则该顾客即离去个顾客，则该顾客即离去.1.设时间间隔设时间间隔t内，有一个顾客进入系统的概率为内，有一个顾客进入系统的概率为q，有一，有一原来被服务的顾客离开系统的概率为原来被服务的顾客离

38、开系统的概率为p.2.设当设当t充分小时，在这个时间间隔内多于一个顾客进入或充分小时，在这个时间间隔内多于一个顾客进入或离开系统实际上是不可能的离开系统实际上是不可能的.3.设有无顾客来到与服务是否完毕是相互独立的设有无顾客来到与服务是否完毕是相互独立的.等候室服务台随机到达者离去者系 统 设设Xn = X(nt )表示时刻表示时刻 nt 时系统内的顾客数，即系统的状时系统内的顾客数，即系统的状态态. 是一随机过程，状态空间是一随机过程，状态空间I=0,1,2,3 ，由前例的分析，由前例的分析, 可知它是一个齐次马氏链可知它是一个齐次马氏链. 下面下面来计算此马氏链的一步转移概率来计算此马氏链

39、的一步转移概率. p00 00 表示在系统内没有顾客的条件下，经表示在系统内没有顾客的条件下，经t 后仍没有顾客后仍没有顾客的概率（此处是条件概率，以下同）的概率（此处是条件概率，以下同） p0000 = 1- -q. p01 01 表示在系统内没有顾客的条件下，经表示在系统内没有顾客的条件下，经t 后有一顾客进后有一顾客进入系统的概率，入系统的概率，p0101 = q. p10 10 系统内恰有一个顾客正在接受服务的条件下，经系统内恰有一个顾客正在接受服务的条件下，经t 后后 .,2 , 1 ,0, nXn 系统内无人的概率，它等于在系统内无人的概率，它等于在t 间隔内顾客因服务完毕而间隔内

40、顾客因服务完毕而离去离去 ，且无人进入系统的概率，且无人进入系统的概率，p1010 = p(1 q) p1111系统内恰有一顾客的条件下，在系统内恰有一顾客的条件下，在t 间隔内，他因服务间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率，顾客将继续要求服务，且无人进入系统的概率， p1111 = pq + (1-p)(1-q). p1212 正在接受服务的顾客继续要求服务，且另一个顾客进正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率入系统的概率, p1212 = (1-p)q

41、. p1313正在接受服务的顾客继续要求服务，且在正在接受服务的顾客继续要求服务，且在t 间隔内有间隔内有两个顾客进入系统的概率两个顾客进入系统的概率 ，由假设，后者实际上是不可能，由假设，后者实际上是不可能发生的，发生的， p1313 =0.类似地，有类似地，有p2121 = p3232 = p(1-q), p2222 = pq + (1-p)(1-q) , p2323 = q(1-p), pij = 0, (|i-j |2).p3333 : : 或者一人将离去且另一人将进入系统，或者无人离开或者一人将离去且另一人将进入系统，或者无人离开的概率，的概率， p3333 = pq + (1-p)

42、.于是该马氏链的一步转移概率矩阵为于是该马氏链的一步转移概率矩阵为 1-qq00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p) 例例2 试说明试说明 1例例3中的链是遍历的，并求其极限分布中的链是遍历的，并求其极限分布. 解解 依照例依照例1， 由由 1例例3中的一步转移概率矩阵中的一步转移概率矩阵P，可算得，可算得P(3)= P3无零元无零元. 根据定理，链是遍历的，根据定理，链是遍历的， 而极限分布而极限分布 满足下列方程组满足下列方程组 解之解之 ，得唯一解，得唯一解),(3210p p

43、p pp pp pp p . 1,)1()1(,)1()1)(1()1(,)1()1)(1(,)1()1(321032332122101100p pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pppqpqqpqppqpqqpqppqqqpqCqqpCqp/)1 ( ,/)1 (221330 p pp pCpqCpqpq/)1( ,/ )1)(1(23322 p pp p 其中其中 假若在此例中，设假若在此例中，设p = q = 1/2,则可算得则可算得 0 0 = 1/7 0.14, 1 1 = 2 2 = 3 3 = 2/7 0.29, 即此时极限分布为即此时极限分布为 =(1/7，2/7，2/7，2/7). 这就这就是说，经过相当长的时间后，系统中无人的情形约占是说，经过相当长的时间后，系统中无人的情形约占14%的时间，的时间，而系统中有一人，二人，三人的情形各占而系统中有一人，二人，三人的情形各占29%的时间的时间. 例例3 设一马氏链的一步转移概率矩阵为设一马氏链的一步转移概率矩阵为 试讨论它的遍历性试讨论它的遍历性 解解 先算得先算得2322233)1 ()1)(1 ()1 ()1 (pqpqpqqqpqpC 02/ 102/ 12/ 102/ 1002/ 102/ 12/ 102/ 10P 2/ 1