中科院研究生院《随机过程》讲稿：第二章 Markov 过程（2-9）应用问题

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 第二章 Markov过程 9.应用问题 (一)几种重要的纯不连续马氏过程 (1) Poission过程(专门讲解) (2)纯增殖过程(人口问题) 纯增殖过程的转移概率为: (t)△t+o(△), k=n+1 PX(+△)=kX()=n}={o(△ k≠n,n+1,k>n 1-元(D)△+O(△),k=n 即在纯不连续增殖过程中,如果在[0,1)内出现n个个体X()=n的 条件下,在[+△)内出现一个新个体的概率为x()△+o(△), 出现二个或二个以上新个体的概率为o(△t),没有出现新个体的 概率为1-,(1)△t+o(△r) 纯增殖过程的状态空间为S={0,1,2,…} 关心的问题是:在t时刻,系统具有n个个体的概率是多少, 即要求 P{X(1)=n}=pn(1)=? 假定初始(t=0)时系统有m个个体,m∈S,即 P{X(0)=m}=pn(0)=1,并假定A(1)=(与t无关),我们来求 pn(D)=P{X(1)=n}。 我们注意到:在0,t+M)内出现n(n>m)个个体可以等价于下 列不相容的情况之和:(a)在[0,1)内出现n个个体,在t,t+△1)内

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 第二章 Markov 过程 9．应用问题 （一） 几种重要的纯不连续马氏过程 （1） Poission 过程（专门讲解） （2） 纯增殖过程（人口问题） 纯增殖过程的转移概率为：      −  +  =   +   +  = + +  = = = t t t k n t k n n k n t t t k n P X t t k X t n n n 1 ( ) ( ) , ( ) , , 1, ( ) ( ) , 1 { ( ) ( ) }      即在纯不连续增殖过程中，如果在 [0,t) 内出现 n 个个体 X(t) = n 的 条件下，在 [t,t + t) 内出现一个新个体的概率为 (t) t ( t)  n  +   ， 出现二个或二个以上新个体的概率为 (t) ，没有出现新个体的 概率为 1 (t) t ( t) −  n  +   。 纯增殖过程的状态空间为 S ={0,1,2, } 关心的问题是：在 t 时刻，系统具有 n 个个体的概率是多少， 即要求： P{X (t) = n} = p (t) = ? n 假定初始（ t = 0 ）时系统有 m 个个体， mS ， 即 P{X (0) = m} = pm (0) =1 ，并假定 n n  (t) =  （与 t 无关），我们来求 p (t) P{X (t) n} n = = 。 我们注意到：在 [0,t + t) 内出现 n (n  m) 个个体可以等价于下 列不相容的情况之和：（a）在 [0,t) 内出现 n 个个体，在 [t,t + t) 内

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 出现0个个体;(b)在[0,)内出现n-1个个体,在[+△1)内出 现1个个体;(c)在[0,1)内出现n-2个个体或n-2个体以下,在 t+△)内出现2个个体或2个个体以上,因此有: pn(t+△)=pn(D)p0(△t)+pn1(O1)p2(△)+o(△) =Pn()1-2A]+pn(1)△)+o(△)(n>m) 因此有 dp(t) dt Pn(1)+ 同理,有: P0(t+△t)=p0(m)1-AA]+o(△)(m=0) pn(t+△)=pn()1-A]+o(A)(m≠0) 即有 dp(t) 1P0(1) dp (t) dt npn(),m≠0 用 Laplace变换解此微分方程可得: P ∏(4-,) (3)生灭过程 定义:纯不连续马氏过程{X(,t≥0}如果满足 (a)过程中状态转移仅限于从一个状态向其邻近状态转 移 (b)若X()=n,则在[t,t+△)内产生由n状态转移到

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 出现 0 个个体；（b）在 [0,t) 内出现 n −1 个个体，在 [t,t + t) 内出 现 1 个个体；（c）在 [0,t) 内出现 n − 2 个个体或 n − 2 个体以下，在 [t,t + t) 内出现 2 个个体或 2 个个体以上，因此有： ( )[1 ] ( ) ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 0 1 1 p t t p t t t n m p t t p t p t p t p t t n n n n n n n = −  +  +   +  =  +  +  − − −     因此有： p t p t n m dt d p t n n n n n = − ( ) + − − ( )  ( )   1 1 同理，有： ( ) ( )[1 ] ( ) ( 0) ( ) ( )[1 ] ( ) ( 0) 0 0 0 +  = −  +   +  = −  +  = p t t p t t t m p t t p t t t m m m  m    即有：        = −  = − = ( ) , 0 ( ) ( ) , 0 ( ) 0 0 0 p t m dt d p t p t m dt d p t m m m   用 Laplace 变换解此微分方程可得：   = =  − − − − = − n i m n j m j i i j t m n n m n e p t , 1 ( ) ( ) ( 1) 1       （3） 生灭过程 定义：纯不连续马氏过程 {X(t), t  0} 如果满足： （a） 过程中状态转移仅限于从一个状态向其邻近状态转 移； （b） 若 X(t) = n ，则在 [t,t + t) 内产生由 n 状态转移到

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (n+1)状态的概率为:(1)M+o(A1);产生由n状态转移 到(n-1状态的概率为:()△+O(△); (c)若X(1)=n,则在[t,t+△)内转移二个或二个以上状 态的概率为o(At) 则称此纯不连续马氏过程{X(1),t≥0}为生灭过程。 状态空间为S={0,1,2,} 由定义,可得生灭过程的Q(生灭矩阵)矩阵为 000 0 (2+2)2 0 (n+4n)0 0 在条件λ>0,1≥0,>0,1≥1,(=0)下,有: i-1>i<>i+1(i≥1) 因此,可知对,j∈S,有i<>j,从而这样的生灭过程是不可约 的 由生灭矩阵可以写出K一F前进方程: d po(t) dt, po()+u, Por() dt=an, Pon()-(, +A )Pon(0)+un+Pon(t)n21 d po(t) (A) -1p0(t)+P1P1() dp (t) =an-pin(t)-(n+u,P ()+upim(t)n2 dt

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 (n +1) 状态的概率为： (t) t ( t)  n  +   ；产生由 n 状态转移 到 (n −1) 状态的概率为： (t) t ( t) n  +   ； （c） 若 X(t) = n ，则在 [t,t + t) 内转移二个或二个以上状 态的概率为 (t)。 则称此纯不连续马氏过程 {X(t), t  0} 为生灭过程。 状态空间为 S ={0,1,2, } 由定义，可得生灭过程的 Q （生灭矩阵）矩阵为：                       − + − + − + − =                           0 0 0 0 0 ( ) 0 0 ( ) 0 0 ( ) 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 0 0 n n n n Q               在条件 i  0 , i  0 ， i  0 , i 1 ，（  0 = 0 ）下，有： i −1i i +1(i 1) 因此，可知对  i, jS ，有 i  j ，从而这样的生灭过程是不可约 的。 由生灭矩阵可以写出 K－F 前进方程：             = − + +  = − + = − + +  = − + − − + + − − + + ( ) ( ) ( ) ( ) 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 ( ) ( ) ( ) ( ) 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 p t p t p t n dt d p t p t p t dt d p t p t p t p t n dt d p t p t p t dt d p t n i n n n i n n i n i n i i i n n n n n n n n             (A)

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 Fokker-Planck方程: ∫p()=-p(0)+Ap1() P(1)=1P1-()-(x,+H1)P,(t)+H1P 其中i=0,1,2,…,j=1,2,…。以上的λ,n(n=012,…)均可以 是t的函数。 如果{X()t≥0的极限分布存在,即p=mp,(1),且与i无 关,则有p(1)=0(→>∞),因此在 Fokker-Planck方程中令t→, 有: 1P0+H1P1=0 P=1-(41+H)P1+HmP+1=0j2 解以上代数方程组得: PI P0,P2 P,…,p2=xx…1- 1112x…k 利用:∑p=1,我们有: 1+ 1142… 由此可知,当 0,1≥0,>0,≥1, =0,则{X(t),t≥0}存在唯一的平稳分布(它就等于极限分布 的充要条件为 < 1142

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 Fokker-Planck 方程：     = − + +  = − + −1 −1 +1 +1 0 0 1 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) j j j j j j j pj p t p t p t p t p t p t       其中 i = 0,1,2,  , j =1,2,  。以上的  n  n , （ n = 0,1,2,  ）均可以 是 t 的函数。 如果 {X(t), t  0} 的极限分布存在，即 p lim p (t) i j t j → = ，且与 i 无 关，则有 p (t) = 0 (t →) j ，因此在 Fokker-Planck 方程中令 t →  ， 有：    − + + =  − + = − − ( ) + + 0 1 0 1 1 1 1 0 0 1 1 p p p j p p  j j  j  j j  j j   解以上代数方程组得： 0 1 2 0 1 1 0 1 2 0 1 0 2 1 0 1 p p , p p , , p p k k k                − = = = 利用：  =1 kS pk ，我们有： 1 1 1 2 0 1 1 0 1 −  = −         = +  k k k p         由此可知，当     = − 1 1 2 0 1 1 k k k         时， 0 1, 0 1 ( 1)  p0   pk  k  ，因此可得以下定理： 定理：设 {X(t), t  0} 时生灭过程， i  0 , i  0 ， i  0 , i 1 ，  0 = 0 ，则 {X(t), t  0} 存在唯一的平稳分布（它就等于极限分布） 的充要条件为：     = − 1 1 2 0 1 1 k k k        

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 且 Pk P k=1112…k 12…… 给定起始状态X(0)=i∈S,就可以求得过程在t时刻处于状态 n的概率p(1)=P{X()=m},初始条件为: 1.n=i P(O)=0 0.n≠ 如果λn,p均是t的函数,则上述过程称为非齐次生灭过程; 如果λ,μ均是t的线性函数,则称为非齐次线性生灭过程 如果,μ均与t的无关,则上述过程称为齐次生灭过程 特别地,假设λn=n2(),n=n(1),此时过程是非齐次线性生 灭过程,关于此情况时的微分方程(A)的解法(用母函数求解 法)可以看P179(课后阅读)。 当n=n,An=m(与1无关),此时过程是齐次线性生灭过程 对于此时,我们可以求E{Y(t)},具体求法如下: 此时的生灭矩阵为 0 02 2(+p)2元 0 0 nu -n(n 0 0 写出福克一普朗克方程:

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 且 0 1 2 0 1 1 1 1 1 2 0 1 1 p0 1 p p k k k k k k                 − −  = − =         = +  给定起始状态 X(0) = iS ，就可以求得过程在 t 时刻处于状态 n 的概率 p (t) P{X (t) n} n = = ，初始条件为：     = = n i n i pin 0 , 1, (0) 如果  n  n , 均是 t 的函数，则上述过程称为非齐次生灭过程； 如果  n  n , 均是 t 的线性函数，则称为非齐次线性生灭过程； 如果  n  n , 均与 t 的无关，则上述过程称为齐次生灭过程。 特别地，假设 n (t), n (t)  n =  n =  ，此时过程是非齐次线性生 灭过程，关于此情况时的微分方程（A）的解法（用母函数求解 法）可以看 P179（课后阅读）。 当  n = n, n = n （与 t 无关），此时过程是齐次线性生灭过程， 对于此时，我们可以求 E{X(t)} ，具体求法如下： 此时的生灭矩阵为                       − + − + − + =                           0 0 0 0 0 ( ) 0 0 2 2( ) 2 0 0 ( ) 0 0 0 0 0 0 0 0 0             n n n Q 写出福克－普朗克方程：

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 dpo(t) P() dp1(1) =-(+A)P(1)+21p2(1) dp,(t) =(n-1)Apn1(1)-n(+)pn(D)+(n+1)Pn1(t) 令:M2()=E{X(}=∑np()=∑np() 则有 dMx(t)d「 dp(t) =∑m(n-1)pn()-(4+A)∑n2p,()+∑m(n+1)pn() 由于 ∑m(n-1pn(0)=∑m(m+1)p()=∑m(m+1Dpn(0) n(n+1)pn(m)=∑(m-1)mpn(1)=∑(m-1)mpn(t) 因此 dM(t) a=A2mn+p)-(+2np(O)+2n-1)m2 =(1-)∑mp,(1)=(4-)M2(t) 即有 dM1() =(2-)Mx(t) dt 利用初始条件:M1(0)=1×1=i,即可求得: M,(t=E(X(t t≥0 由上面求解过程可以看到,一般来说,解前进方程、后退方

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞            = − − + + + = − + + = − + ( 1) ( ) ( ) ( ) ( 1) ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) ( ) 1 1 1 2 1 1 0 n p t n p t n p t dt d p t p t p t dt d p t p t dt d p t n n n n          令：    =  = = = = 0 1 ( ) { ( )} ( ) ( ) n n n X n M t E X t n p t n p t 则有：       = +  =  = −  =  = = − − + + + = =     = 1 1 1 2 1 1 1 1 ( 1) ( ) ( ) ( ) ( 1) ( ) ( ) ( ) ( ) n n n n n n n n n n X n n p t n p t n n p t dt d p t n p t n dt d dt dM t     由于：     =  =  = − − = + = + 1 0 1 1 ( 1) ( ) ( 1) ( ) ( 1) ( ) m m m m n n n n p t m m p t m m p t     =  =  = + + = − = − 1 2 1 1 ( 1) ( ) ( 1) ( ) ( 1) ( ) m m m m n n n n p t m mp t m mp t 因此： ( ) ( ) ( ) ( ) ( 1) ( ) ( ) ( ) ( 1) ( ) ( ) 1 1 1 2 1 n p t M t n n p t n p t n n p t dt dM t X n n n n n n n n X         = − = − = + − + + −      =  =  =  = 即有： ( ) ( ) ( ) M t dt dM t X X =  −  利用初始条件： M i i X (0) = 1= ，即可求得： ( ) { ( )} 0 ( ) = =  − M t E X t ie t t X   由上面求解过程可以看到，一般来说，解前进方程、后退方

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 程和福克一普朗克方程是比较困难的,有时根本无法求得。但是, 如果只要研究t→∞时的极限情况,我们就可以利用上面8(二) 中提到的方法,将微分方程求极限后,转化为解线性代数方程组, 下面通过例子说明具体的求法。 例:(电话交换问题)某电话总机有n条线路。在某一呼唤来 到时如有空闲线路,则该呼唤占用其中某一条空闲线路,并开始 通话。如果通话结束,则该线路使用完毕而称为空闲线路,等待 下一次呼唤。如果呼唤来到时遇到n条线路均被占用,则该呼唤 招到拒绝而消失。设有按 poission分布的呼唤流,即在[t+△)内 来到一次呼唤的概率为A+o(A1),来到二次或二次以上的呼唤 的概率为o(△n);并设如果某一线路在某时刻t被占用,而在 [t+△)内这条线路空闲出来的概率为M+o(△),即通话时间 按负指数分布。求总机在t时刻有k条线路被占用的概率?以及 当t→∞时,有k条线路被占用的概率? 解:此时的状态空间为S={0,1,2…,n,k=01,2,…;n,并且是 一生灭过程,生灭矩阵为: 0 -(+p)2 00元 +24) 000: 1)-[2+(m-1) 0 0 np n 写出福克一普朗克方程:

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 程和福克－普朗克方程是比较困难的，有时根本无法求得。但是， 如果只要研究 t →  时的极限情况，我们就可以利用上面 8（二） 中提到的方法，将微分方程求极限后，转化为解线性代数方程组， 下面通过例子说明具体的求法。 例：（电话交换问题）某电话总机有 n 条线路。在某一呼唤来 到时如有空闲线路，则该呼唤占用其中某一条空闲线路，并开始 通话。如果通话结束，则该线路使用完毕而称为空闲线路，等待 下一次呼唤。如果呼唤来到时遇到 n 条线路均被占用，则该呼唤 招到拒绝而消失。设有按 poission 分布的呼唤流，即在 [t,t + t) 内 来到一次呼唤的概率为 t +(t) ，来到二次或二次以上的呼唤 的概率为 (t) ；并设如果某一线路在某时刻 t 被占用，而在 [t,t + t) 内这条线路空闲出来的概率为 t +(t) ，即通话时间 按负指数分布。求总机在 t 时刻有 k 条线路被占用的概率？以及 当 t →  时，有 k 条线路被占用的概率？ 解：此时的状态空间为 S ={0,1,2,  ,n} ， k = 0,1,2,  ,n ，并且是 一生灭过程，生灭矩阵为：                     − − − + − − + − + − =                 n n n n Q 0 0 0 0 0 0 0 ( 1) [ ( 1) ] 0 2 ( 2 ) 0 ( ) 0 0 0 0 0          写出福克－普朗克方程：

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 dpo(t) d=-p()+up() P2(t=AP()-(+u)P()+24p2(t) dp,(t) M=Ap2(t)-(+mD2()+(k+1)P(1)(0<k<n) dp,(t) ap,(0)-nup (1) 令: 我们有: po tup, 0 P4-(+k)p4+(k+1)4pD1=0(0<k<n) Ap _-nup,=0 设:g4=Ap1-kp,则有 84=凡p41-kp4=Ap4-(k+1)PD1=g g 因此g,=0i=012, 故有 P po P:ku Pi- Klu po p po 利用:∑P=1→p1421(A+…+/=1 可得

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞                = − = − + + +   = − + + = − + − − + ( ) ( ) ( ) ( ) ( ) ( ) ( 1) ( ) (0 ) ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) ( ) ( ) 1 1 1 0 1 2 1 0 1 0 p t n p t dt d p t p t k p t k p t k n dt d p t p t p t p t dt d p t p t p t dt d p t n n n k k k k               令： t →  ，我们有：      − = − + + + =   − + = − − + 0 ( ) ( 1) 0 (0 ) 0 1 1 1 0 1 n n k k k p n p p k p k p k n p p         设： k k pk g =  p −1 − k ，则有： 0 0 ( 1) 0 1 1 1 = = = − − = − + + = + n k k k k k k g g g  p k p  p k  p g 因此 gi = 0 i = 0,1,2,  ,n 故有：                   =       = = = − 0 1 0 1 0 ! 1 ! 1 p n p p k p k p p p n n k k k           利用： 1 ! 1 2! 1 1 1 2 0 0 =                + +       =  + + = n n k k n p p        可得：

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 0<k≤n 画出转移率转移图,注意用极限平衡原理求解。 几种特殊的生灭过程: ●有迁入的线性增长模型:此时λ=n+a,n=m,(见习题 纯生过程(Yule过程):此时xn=2,pn=0; ·纯灭过程:此时λ1=0,n=,(见习题18); (二)排队和服务问题 任何排队过程都由3个历程组成:到达过程、排队和服务过 程。根据这三个历程不同可以建立不同的概率模型,如M/M/1 和M/M/s及一般的G1/G2/s模型,对于排队和服务问题,我 们所关心的是 (1)服务系统中顾客的平均数 (2)排队等候的顾客平均数 (3)顾客在系统中所花费时间的平均数 (4)顾客化在排队等候的时间平均值 下面通过例子讨论以上几个问题。 例无容量限制的M/M/1排队系统,该系统的顾客到达服 从 Poission分布,只有一个服务员,服务时间服从负指数分布

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 k n i k p n i i k k               = = 0 ! 1 ! 1 0     画出转移率转移图，注意用极限平衡原理求解。 几种特殊的生灭过程： ⚫ 有迁入的线性增长模型：此时  n = n + a , n = n ，（见习题 17）； ⚫ 纯生过程（Yule 过程）：此时  n =  ,  n = 0 ； ⚫ 纯灭过程：此时  n = 0 , n =  ，（见习题 18）； （二） 排队和服务问题 任何排队过程都由 3 个历程组成：到达过程、排队和服务过 程。根据这三个历程不同可以建立不同的概率模型，如 M / M / 1 和 M / M / s 及一般的 G1 /G2 / s 模型，对于排队和服务问题，我 们所关心的是： （1） 服务系统中顾客的平均数 （2） 排队等候的顾客平均数 （3） 顾客在系统中所花费时间的平均数 （4） 顾客化在排队等候的时间平均值 下面通过例子讨论以上几个问题。 例 无容量限制的 M / M / 1 排队系统，该系统的顾客到达服 从 Poission 分布，只有一个服务员，服务时间服从负指数分布

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 且都是独立的。 解:考虑系统进入平稳分布情况。此时是=2,An=情况的 生灭过程。 根据上面的解法,我们有: 当λ<∠时,有平稳分布,且平稳分布为: P (1)系统中顾客的平均数为 L=∑mPn (2)排队等候的顾客平均数为 当系统中有n个人,其中一人被服务,n-1人排队等候,排队 等候的顾客平均数为 L=∑n-1)pn=∑mn-∑pn= (y-2 (3)顾客在系统中所花费时间的平均数: 若顾客A到达服务点时系统中已有n人,其中一人在被服务, n-1人在排队等候;由服务时间是负指数分布(无记忆性)和每 个顾客的服务时间之间的独立性,故顾客A到达服务点后需要 等候平均时间n/4后才能得到服务,本人的平均服务时间为/u, 因此有:

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 且都是独立的。 解：考虑系统进入平稳分布情况。此时是  n =  , n =  情况的 生灭过程。 根据上面的解法，我们有： 当    时，有平稳分布，且平稳分布为：        −      = = −       1 0 1 n pn p （1） 系统中顾客的平均数为：    =  = −  =       −      = = 0 1 1 n n n L n pn n        （2） 排队等候的顾客平均数为： 当系统中有 n 个人，其中一人被服务， n −1 人排队等候，排队 等候的顾客平均数为： ( ) ( 1) 2 1 1 1     − =  − =  −  =  =  =  = n n n n n LQ n pn np p （3） 顾客在系统中所花费时间的平均数： 若顾客 A 到达服务点时系统中已有 n 人，其中一人在被服务， n −1 人在排队等候；由服务时间是负指数分布（无记忆性）和每 个顾客的服务时间之间的独立性，故顾客 A 到达服务点后需要 等候平均时间 n/ 后才能得到服务，本人的平均服务时间为 1/ ， 因此有：