《随机过程与排队论》知识点复习.ppt

《《随机过程与排队论》知识点复习.ppt》由会员分享，可在线阅读，更多相关《《随机过程与排队论》知识点复习.ppt（140页珍藏版）》请在三一办公上搜索。

1、随机过程与排队论,计算机科学与工程学院顾小丰Email：2023年8月9日星期三,2023/8/9,计算机科学与工程学院顾小丰,教学内容,概率论的基本知识随机过程的基本概念随机过程的定义及分类随机过程的分布及数字特征独立过程与独立增量过程泊松过程更新过程,1402,2023/8/9,计算机科学与工程学院顾小丰,教学内容,马尔可夫过程马尔可夫过程的概念离散参数马氏链齐次马氏链状态的分类连续参数马氏链生灭过程,1403,2023/8/9,计算机科学与工程学院顾小丰,教学内容,排队系统概述M/M/1/排队M/M/排队系统M/M/c/排队系统M/M/c/K混合制排队系统M/M/c/m/m系统及损失制系

2、统有备用品的M/M/c/m+K/m系统一般服务的M/G/1/排队系统,1404,2023/8/9,计算机科学与工程学院顾小丰,一、概率论的基本知识,概率空间及其基本概念,随机试验、样本点、样本空间、随机事件体随机事件、基本事件和可测空间概率、概率空间、概率的性质条件概率、乘法公式、事件的独立性、全概率公式与贝叶斯公式,1405,2023/8/9,计算机科学与工程学院顾小丰,1、条件概率空间,设概率空间(,F,P)，AF，BF，且P(A)0，在事件A已经发生的条件下，事件B发生的条件概率定义为：,给定概率空间(,F,P)，AF，且P(B)0，对任意BF有P(B|A)对应，则条件概率P(B|A)是

3、(,F)上的概率，记P(B|A)PA，则(,F,PA)也是一个概率空间，称为条件概率空间。,1406,2023/8/9,计算机科学与工程学院顾小丰,2、乘法公式,设概率空间(,F,P)，如果A,BF，且P(AB)0，则下述乘法公式成立：P(AB)P(A)P(B|A)P(B)P(A|B),推广：,设概率空间(,F,P)，如果AiF，i=1,2,n且P(A1A2An)0，则下述推广的乘法公式成立：P(A1A2An)P(A1)P(A2|A1)P(A3|A1A2)P(An|A1A2An-1),1407,2023/8/9,计算机科学与工程学院顾小丰,3、全概率公式与贝叶斯公式,设事件组B1,B2,Bn两

4、两互不相容，即BiBj(1ijn)，且，P(Bi)0，i=1,2,n，则对任意事件A，有,全概率公式：,贝叶斯公式：,j=1,2,n。,1408,2023/8/9,计算机科学与工程学院顾小丰,4、随机变量及其分布,一、随机变量设(,F,P)为概率空间，如果定义样本空间上的一个单值实函数XX()，满足：X()xF-x+则称X()为随机变量。随机变量缩写为r.v.。,二、分布函数 设XX()是概率空间(,F,P)上的随机变量，对任意实数x，定义函数F(x)PXx-x+称为的概率分布函数，简称分布函数。,1409,2023/8/9,计算机科学与工程学院顾小丰,5、离散型随机变量及其分布律,若至多只取

5、可列无穷多个数值：x1,x2,xn,，令pkPXxk，它满足：(1)pk0，(2)1，则称X为离散型随机变量，并称PXxkpk，k=1,2,为X的分布律或概率分布。离散型的分布函数：,它是左连续单调不减的阶梯函数，在xxk处有第一类跳跃型间断点，其跳跃度为pk。,14010,2023/8/9,计算机科学与工程学院顾小丰,6、连续型随机变量,若存在非负可积函数f(x)，对任意实数x，使得的分布函数满足：,则称X为连续型随机变量，称f(x)为连续型随机变量的概率密度函数，简称概率密度。,14011,2023/8/9,计算机科学与工程学院顾小丰,7、常见的随机变量及其分布,如果的分布律为,则称服从参

6、数为的泊松分布，记为X()。,1)泊松(S.D.Poisson)分布,14012,2023/8/9,计算机科学与工程学院顾小丰,2)(负)指数分布(寿命分布),如果的概率密度为,则称服从参数为的（负）指数分布(寿命分布)，X的分布函数为,14013,2023/8/9,计算机科学与工程学院顾小丰,3)正态分布(高斯分布),如果的概率密度为,则称服从参数为和2的正态分布(高斯分布)，记为XN(,2)，X的分布函数为,特别地，=0,2=1时的正态分布称为标准正态分布，记为N(0,1)，其概率密度和分布函数特别记为：,14014,2023/8/9,计算机科学与工程学院顾小丰,4)k阶爱尔朗(Erlan

7、g)分布,如果的概率密度为,则称服从参数为（0）的k阶爱尔朗分布，记为XEk，其分布函数为,14015,2023/8/9,计算机科学与工程学院顾小丰,8、二维随机变量（向量）,如果X和Y是定义在同一概率空间(,F,P)上的两个随机变量，则称(X,Y)为二维随机变量(向量)，记为二维r.v.(X,Y)。,设(X,Y)是二维随机变量，定义函数F(x,y)PXx,Yy，-x+，-y+为r.v.(X,Y)的二维联合分布函数。,14016,2023/8/9,计算机科学与工程学院顾小丰,9、离散型二维随机变量,如果二维若随机变量(X,Y)至多只取可列无穷多对数值(xi,yj)，i,j=1,2,，令pijP

8、Xxi,Yyj，它满足：(1)pij0，(2)1，则称(X,Y)为离散型二维随机变量。称 pijPXxi,Yyj，i,j=1,2,为(X,Y)的联合分布律。称,为(X,Y)的联合分布函数。,14017,2023/8/9,计算机科学与工程学院顾小丰,边缘分布律、条件分布律,为的边缘分布律。称,为的边缘分布律。称,为在已知Y=yj的条件下，的条件分布律。称,为在已知X=xi的条件下，的条件分布律。,如果pijpi.p.j，i,j=1,2,，则称与Y相互独立,称,14018,2023/8/9,计算机科学与工程学院顾小丰,10、连续型二维随机变量,若存在非负可积函数f(x,y)，使得二维r.v.(X,

9、Y)的联合分布函数满足：,则称(X,Y)为连续型二维随机变量，并称f(x,y)为连续型二维随机变量的联合概率密度函数，简称联合概率密度。,14019,2023/8/9,计算机科学与工程学院顾小丰,11、边缘分布函数,设二维r.v.(X,Y)的联合分布函数为F(x,y)，FX(x)F(x,+)，-x+称为的边缘分布函数。FY(y)F(+,y)，-y+称为的边缘分布函数。,设二维r.v.(X,Y)的联合概率密度为f(x,y)，-x+称为的边缘概率密度函数。，-y+称为的边缘概率密度函数。,14020,2023/8/9,计算机科学与工程学院顾小丰,12、条件概率密度与条件分布函数,fY|X(y|x)

10、f(x,y)fX(x)，-x+,-y+称为已知X=x的条件下，的条件概率密度。fX|Y(x|y)f(x,y)fY(y)，-x+,-y+称为已知Y=y的条件下，的条件概率密度。,称为已知X=x的条件下，的条件分布函数。,称为已知Y=y的条件下，的条件分布函数。,14021,2023/8/9,计算机科学与工程学院顾小丰,13 随机变量的数字特征,1）数学期望,若离散型的分布律为pkPX=Xk，k=1,2,，当时，称,为的数学期望(均值),若连续型的概率密度函数为f(x),x(-,+)，当 时，称,为的数学期望(均值),14022,2023/8/9,计算机科学与工程学院顾小丰,2）方差,设X是随机变

11、量，若EX-E(X)2存在，称D(X)EX-E(X)2为的方差(或记为Var(X)，称为的均方差或标准差。,事实上有：D(X)EX-E(X)2E(X22XE(X)E2(X)E(X2)-E2(X),14023,2023/8/9,计算机科学与工程学院顾小丰,3）常见随机变量的数学期望和方差,泊松分布X()：E(X)D(X)；(负)指数分布：E(X)1/，D(X)1/2；正态分布XN(,2)：E(X)，D(X)2；爱尔朗分布XEk：E(X)k/，D(X)k/2。,14024,2023/8/9,计算机科学与工程学院顾小丰,3）k阶矩,设有E(|X|k)+，E|X-E(X)|k+，则称kE(Xk)为X的

12、k阶原点矩；称kE(|X|k)为X的k阶绝对矩；称kEX-E(X)k为X的k阶中心矩；称kE|X-E(X)|k为X的k阶绝对中心矩。,14025,2023/8/9,计算机科学与工程学院顾小丰,4）协方差,若EX-E(X)Y-E(Y)，称cov(X,Y)EX-E(X)Y-E(Y)E(XY)-E(X)E(Y)为随机变量X和Y的协方差，称,为随机变量X和Y的相关系数，称XY0为随机变量X和Y不相关。,14026,2023/8/9,计算机科学与工程学院顾小丰,5）协方差矩阵,设n维r.v.(X1,X2,Xn)，若cijcov(Xi,Xj)EXi-E(Xi)Xj-E(Xj)i,j1,2,n存在，则称,为

13、n维随机变量(X1,X2,Xn)的协方差矩阵。,14027,2023/8/9,计算机科学与工程学院顾小丰,6）特征函数,随机变量X的特征函数定义为X(u)=E(eiuX)，i,当为离散型随机变量时，,当为连续型随机变量时，,14028,2023/8/9,计算机科学与工程学院顾小丰,二、随机过程的基本概念,1、随机过程 设(,F,P)是一个概率空间，T是一个参数集(TR)，X(t,)，tT，是T上的二元函数，如果对于每一个tT，X(t,)是(,F,P)上的随机变量，则称随机变量族X(t,)，tT为定义在(,F,P)上的随机过程(或随机函数)。简记为X(t)，tT，其中t称为参数，T称为参数集。,

14、14029,2023/8/9,计算机科学与工程学院顾小丰,2、样本函数与状态空间,随机过程X(t,)是定义在T上的二元函数：一方面，当tT固定时，X(t,)是定义在上的随机变量；另一方面，当固定时，X(t,)是定义在T上的函数，称为随机过程的样本函数。随机过程在时刻t所取的值X(t)=x称为时刻t时随机过程X(t),tT处于状态x，随机过程X(t),tT所有状态构成的集合称为状态空间，记为E，即：Ex：X(t)=x,tT,14030,2023/8/9,计算机科学与工程学院顾小丰,3、随机过程的分类,按状态空间和参数集分类,按概率分布规律分类,独立过程独立增量过程正态过程泊松过程,维纳过程平稳过

15、程马尔可夫过程,14031,2023/8/9,计算机科学与工程学院顾小丰,4、随机过程的分布,设X(t),tT是一个随机过程，对于每一个tT，X(t)是一个随机变量，它的分布函数F(t,x)PX(t)x，tT，xR=(-,+)称为随机过程X(t),tT的一维分布函数。,如果对于每一个tT，随机变量X(t)是连续型随机变量，存在非负可积函数f(t,x)，使得,则称f(t,x)，tT,xR为随机过程X(t),tT的一维概率密度(函数)。此时f(t,x)Fx(t,x)，tT，xR,14032,2023/8/9,计算机科学与工程学院顾小丰,二维分布函数,设X(t),tT是一个随机过程，对任意s,tT，

16、(X(s),X(t)是一个二维随机变量，它的联合分布函数F(s,t;x,y)PX(s)x,X(t)y，tT，xR 称为随机过程X(t),tT的二维分布函数。,14033,2023/8/9,计算机科学与工程学院顾小丰,二维概率密度,如果(X(s),X(t)是连续型二维随机变量，存在非负可积函数f(s,t;x,y)，使得,成立，则称f(s,t;x,y)，s,tT，x,yR为随机过程X(t),tT的二维概率密度(函数)。此时,14034,2023/8/9,计算机科学与工程学院顾小丰,5、随机过程的数字特征,给定随机过程X(t),tT，称m(t)EX(t)，tT为随机过程X(t),tT的均值函数(数学

17、期望)。,若X(t),tT的状态空间是离散的，则X(t),tT是离散型随机变量，X(t)的概率分布为pk(t)PX(t)=Xk，k=1,2,，则,若X(t),tT的状态空间是连续的，则X(t),tT是连续型随机变量，X(t)的一维概率密度为f(t,x)为，则,14035,2023/8/9,计算机科学与工程学院顾小丰,方差函数,给定随机过程X(t),tT，称D(t)DX(t)EX(t)m(t)2，tT为随机过程X(t),tT的方差函数。显然，D(t)EX(t)m(t)2EX2(t)m2(t)。称 为随机过程X(t),tT的均方差函数(标准方差函数)。,若X(t),tT是离散型随机变量，X(t)的

18、概率分布为pk(t)PX(t)=Xk，k=1,2,，则,若X(t),tT是连续型随机变量，X(t)的一维概率密度为f(t,x)为，则,14036,2023/8/9,计算机科学与工程学院顾小丰,协方差函数和相关函数,给定随机过程X(t),tT，称C(s,t)cov(X(s),X(t)EX(s)m(s)X(t)m(t)为随机过程X(t),tT的协方差函数。显然，C(s,t)EX(s)X(t)m(s)m(t)，C(t,t)D(t)EX(t)m(t)2。,给定随机过程X(t),tT，称R(s,t)EX(s)X(t)为随机过程X(t),tT的相关函数。显然，C(s,t)R(s,t)m(s)m(t)，R(

19、s,t)C(s,t)m(s)m(t),给定随机过程X(t),tT，称,为随机过程X(t),tT的相关系数。,14037,2023/8/9,计算机科学与工程学院顾小丰,6、重要随机过程,1）独立过程,给定随机过程X(t),tT，如果对任意正整数n及任意t1,t2,tnT，随机变量X(t1),X(t2),X(tn)相互独立，则称随机过程X(t),tT为独立过程。特别，如果X(n),n=1,2,3,是相互独立的随机变量，则称X(n),n=1,2,3,为独立随机序列。,14038,2023/8/9,计算机科学与工程学院顾小丰,2）独立增量过程,设随机过程X(t),tT，T0,+)，如果对任意正整数n2

20、，t1,t2,tnT且t1t2tn，随机过程的增量X(t2)-X(t1),X(t3)-X(t2),X(tn)-X(tn-1)是相互独立的随机变量，则称X(t),tT为独立增量过程。,14039,2023/8/9,计算机科学与工程学院顾小丰,3）平稳独立增量过程,如果独立增量过程X(t),tT，T0,+)，对所有的s,tT及h0,s+h,t+hTX(t+h)-X(s+h)与X(t)-X(s)有相同的概率分布，则称X(t),tT为平稳独立增量过程。,14040,2023/8/9,计算机科学与工程学院顾小丰,4）正态过程,给定随机过程X(t),tT，如果对任意正整数n及t1,t2,tnT，n维随机变

21、量X(t1),X(t2),X(tn)的联合概率分布为n维正态分布，则称随机过程X(t),tT为正态过程(或高斯过程)。设X(t),tT为正态过程，则其有限维概率分布都是正态分布。,14041,2023/8/9,计算机科学与工程学院顾小丰,正态过程的一维概率分布,均值函数方差函数一维概率分布一维概率密度函数一维特征函数,14042,2023/8/9,计算机科学与工程学院顾小丰,正态过程的二维概率分布,均值函数向量二阶协方差矩阵二维概率分布二维概率密度函数二维特征函数,14043,2023/8/9,计算机科学与工程学院顾小丰,5）维纳过程(Brown运动),如果随机过程W(t),t0满足下列条件：

22、W(0)0；EW(t)0；具有平稳独立增量；t0，W(t)N(0,2t)，(0)则称随机过程W(t),t0是参数为2的维纳过程(或布朗运动)。,14044,2023/8/9,计算机科学与工程学院顾小丰,维纳过程的概率分布及数字特征,一维概率密度函数一维特征函数增量分布协方差函数,14045,2023/8/9,计算机科学与工程学院顾小丰,维纳过程的二维概率分布,均值函数向量二阶协方差矩阵二维概率分布二维概率密度函数二维特征函数,14046,2023/8/9,计算机科学与工程学院顾小丰,维纳过程的性质,维纳过程是平稳独立增量过程。维纳过程是正态过程。维纳过程是马尔可夫过程。,14047,2023/

23、8/9,计算机科学与工程学院顾小丰,6）泊松过程,如果取非负整数值的计数过程N(t),t0满足：N(0)0；具有独立增量；对任意0st,N(t)-N(s)服从参数为(t-s)泊松分布，,则称N(t),t0为参数(或平均率、强度)为的(齐次)泊松过程。,14048,2023/8/9,计算机科学与工程学院顾小丰,泊松过程的定义2,如果取非负整数值得计数过程N(t),t0满足下列条件：N(0)0；具有平稳独立增量；PN(h)=1h+o(h)；PN(h)2o(h)则称N(t),t0为参数(或平均率、强度)为的(齐次)泊松过程。,14049,2023/8/9,计算机科学与工程学院顾小丰,泊松过程的概率分

24、布和数字特征,一维概率分布及均值和方差函数对任意t0,N(t)(t),PN(t)=k,均值函数m(t)EN(t)t；方差函数D(t)DN(t)t。一维特征函数,14050,2023/8/9,计算机科学与工程学院顾小丰,泊松过程的概率分布和数字特征,二维概率分布,PN(s)=j,N(t)=kPN(s)=j,N(t)-N(s)=k-j,ts,PN(s)=jPN(t-s)=k-j,14051,2023/8/9,计算机科学与工程学院顾小丰,泊松过程的概率分布和数字特征,协方差函数和相关函数协方差函数C(s,t)min(s,t)，相关函数R(s,t)min(s,t)2st。,14052,2023/8/9

25、,计算机科学与工程学院顾小丰,泊松过程的性质,泊松过程是平稳独立增量过程；,设N(t),t0是参数为的泊松过程，Tn,n=1,2,为点间间距序列，则Tn,n=1,2,是相互独立同分布的随机变量，且都服从参数为的(负)指数分布。,设N(t),t0是参数为的泊松过程，n,n=1,2,为等待时间序列，则 n(n,)，即概率密度为：,即n阶爱而朗分布。,14053,2023/8/9,计算机科学与工程学院顾小丰,7、马尔可夫过程,定义1 给定随机过程X(t),tT，如果对于参数中任意n个时刻ti,i=1,2,n，t1t2tn有,PX(tn)xn|X(t1)=x1,X(t2)=x2,X(tn-1)=xn-

26、1 PX(tn)xn|X(tn-1)=xn-1(3.1)则称随机过程X(t),tT为马尔可夫过程，简称马氏过程。具有(3.1)式性质称为具有马尔可夫性、无后效性或无记忆性。,14054,2023/8/9,计算机科学与工程学院顾小丰,转移概率,定义2 给定马氏过程X(t),tT，条件概率p(s,t;x,y)PX(t)y|X(s)=x称为马氏过程的转移概率。,若转移概率与s无关，则此过程称为齐次(时)马氏过程。,马氏过程X(t),tT中，X(t)的取值x称为状态，X(t)x表示过程在时刻t处于状态x，过程所取状态的全体Ex：X(t)=x,tT称为状态空间。,14055,2023/8/9,计算机科学

27、与工程学院顾小丰,马尔可夫过程的分类,14056,2023/8/9,计算机科学与工程学院顾小丰,1）离散参数马氏链,设X(n),n=0,1,2,为马氏链，E=0,1,2,，称条件概率pij(m,k)PX(m+k)=j|X(m)=i为马氏链X(n),n=0,1,在m时刻的k步转移概率.,特别地，k=1时，pij(m,1)PX(m+1)=j|X(m)=i称为一步转移概率，简称转移概率。,状态空间E和参数集T都是离散的马尔可夫过程称为离散参数马氏链，简称马氏链。即,14057,2023/8/9,计算机科学与工程学院顾小丰,2）齐次马尔可夫链,若马氏链X(n),n=0,1,2,的转移概率pij(m,k

28、)与m,无关，即pij(m,k)PX(m+k)=j|X(m)=ipij(k)；pij(m,1)PX(m+1)=j|X(m)=ipij(1)pij；则称X(n),n=0,1,2,为齐次马尔可夫链，简称齐次马氏链。,齐次马氏链的k步转移矩阵记为：P(m,k)P(k)(pij(k)i,jE一步转移矩阵，简称转移矩阵，记为：P(m,1)P(1)P(pij)i,jE齐次马氏链的转移概率具有如下性质：0pij(k)1，0pij1，,14058,2023/8/9,计算机科学与工程学院顾小丰,3）齐次马氏链的性质,齐次马氏链X(n),n=0,1,2,的转移概率pij(k)满足C-K方程(Chapman-Kol

29、mogrov)。,采用矩阵记号为：P(k+s)P(k)P(s)。,齐次马氏链X(n),n=0,1,2,的n步转移矩阵等于一步转移矩阵的n次方，即：P(n)Pn。,绝对分布由初始分布和转移概率确定，且满足,或记为,14059,2023/8/9,计算机科学与工程学院顾小丰,3）齐次马氏链的性质（续）,齐次马氏链的有限维分布由初始分布和转移概率确定，且满足,PX(n1)=i1,X(n2)=i1,X(nk)=ik,其中PX(n1)=i1,X(n2)=i1,X(nk)=ik为齐次马氏链的k维概率分布。,14060,2023/8/9,计算机科学与工程学院顾小丰,3）齐次马氏链的性质（续）,设齐次马氏链X(

30、n),n=0,1,2,的状态空间,E=1,2,s为有限，若存在正整数n0,对任意i,jE，有pij(n0)0，则此马氏链是遍历的，且极限分布是方程组,在满足条件,下的唯一解。,14061,2023/8/9,计算机科学与工程学院顾小丰,3）齐次马氏链的性质（续）,设齐次马氏链X(n),n=0,1,2,具有遍历性，则,即遍历的齐次马氏链的绝对分布与转移概率有相同的极限。,遍历的齐次马氏链的极限分布是平稳分布,设X(n),n=0,1,2,的平稳分布为vj,jE，则有VVPn，n=0,1,2,14062,2023/8/9,计算机科学与工程学院顾小丰,3）齐次马氏链的性质（续）,如果齐次马氏链X(n),

31、n=0,1,2,的初始分布pj,jE恰好是平稳分布，则对一切n有pj(n)pj，n=0,1,2,，jE 即,14063,2023/8/9,计算机科学与工程学院顾小丰,3）齐次马氏链的性质（续）,设齐次马氏链X(n),n=0,1,2,的状态空间有,限E=1,2,s，若存在正整数n0,对任意i,jE，n0步转移概率pij(n0)0，则此链是遍历的，且极限分布等于平稳分布。,14064,首返概率,平均返回时间,周期,以三个层次区分状态类型,状态,非常返态,常返态,零常返态,正常返态,有周期,非周期,遍历态,4）齐次马氏链状态的分类,2023/8/9,计算机科学与工程学院顾小丰,14065,2023/

32、8/9,计算机科学与工程学院顾小丰,5）连续参数马尔可夫链,设随机过程X(t),t0，状态空间E=0,1,2,。若对于0t1t2tntn+1及非负整数i1,i2,in,in+1，有PX(tn+1)in+1|X(t1)=i1,X(t2)=i2,X(tn)=inPX(tn+1)in+1|X(tn)=in即马尔可夫性成立，则称X(t),t0为连续参数马尔可夫链。,14066,2023/8/9,计算机科学与工程学院顾小丰,转移概率函数,设X(t),t0为连续参数马氏链，对任意i,jE0,1,2,，任意非负实数s,t，条件概率pij(s,t)PX(t+s)=j|X(s)=i称为此马氏链X(t),t0的转

33、移概率函数，显然,我们称P(s,t)(pij(s,t)i,jE为此马氏链的转移矩阵。,14067,2023/8/9,计算机科学与工程学院顾小丰,连续参数齐次马氏链,若X(t),t0为连续参数马氏链的转移概率pij(s,t)与,时间起点s无关，即pij(s,t)PX(s+t)=j|X(s)=ipij(t)则称X(t),t0为连续参数齐次马氏链。,类似地，,P(t)(pij(t)i,jE称为此齐次马氏链的转移矩阵。0pij(t)1，,14068,2023/8/9,计算机科学与工程学院顾小丰,转移概率函数的性质,0pij(t)1，i,jE；,连续性条件：,pij(t)满足C-K方程,矩阵形式:P(t

34、+s)P(t)P(s),绝对概率满足,如果齐次马氏链X(t),t0是遍历马氏链，则,14069,2023/8/9,计算机科学与工程学院顾小丰,转移概率函数的性质(续1),设齐次马氏链X(t),t0的状态有限，E=0,1,2,s，如果存在t00，使得对任意i,jE，都有pij(t0)0，则此齐次马氏链X(t),t0为遍历的齐次马氏链。即,存在且与i无关，并且极限分布j,jE是唯一的平稳分布：,对固定的i,j，函数pij(t)是t0的一致连续函数。,满足连续性条件的连续参数齐次马氏链X(t),t0存在下列极限,其中qi表示在时刻t时通过状态i的通过速度(或通过强度)；qij表示时刻t时从状态i转移

35、到状态j的速度(或强度)，qij统称转移速度。,14070,2023/8/9,计算机科学与工程学院顾小丰,转移概率函数的性质(续2),设齐次马氏链X(t),t0，状态空间E=0,1,2,s，其转移速度,设X(t),t0为连续参数齐次马氏链，当qi+，qi 时，满足柯尔莫哥洛夫后退微分方程,即P(t)QP(t),设X(t),t0为连续参数齐次马氏链,当qi+,qri 时，则有柯尔莫哥洛夫前进微分方程,即P(t)P(t)Q,14071,2023/8/9,计算机科学与工程学院顾小丰,转移概率函数的性质(续3),绝对概率满足（福克-普朗克方程）,齐次不可约连续参数马氏链X(t),t0存在极限分布，即为

36、平稳分布j,jE,即Q0（零向量）,14072,2023/8/9,计算机科学与工程学院顾小丰,8、生灭过程,设X(t),t0是连续参数齐次马氏链，状态空间E0,1,2,N，如果它的状态转移速度矩阵为,则称X(t),t0为生灭过程。,14073,2023/8/9,计算机科学与工程学院顾小丰,生灭过程的转移概率,上述生灭过程X(t),t0的定义可等价地用转移概率pij(t)表示为：,14074,2023/8/9,计算机科学与工程学院顾小丰,生灭过程满足的柯尔莫哥洛夫方程,柯尔莫哥洛夫后退方程：P(t)QP(t)，P(+0)I(单位阵),柯尔莫哥洛夫前进方程：P(t)P(t)Q，P(+0)I,140

37、75,2023/8/9,计算机科学与工程学院顾小丰,福克普朗克方程,绝对概率满足福克普朗克方程：,(1),推广到无限状态E0,1,2,n,为：,(2),14076,2023/8/9,计算机科学与工程学院顾小丰,福克普朗克方程解的存在性,对有限状态E0,1,2,N的生灭过程，若满足pj(t)0，,，则对任给的初始条件，方程组,(1)的解存在、唯一，而且,对可列无限状态E0,1,2,n,的生灭过程，若,而且满足pj(t)0，,，则对任给的初始条件，,方程组(2)的解存在、唯一，且,14077,2023/8/9,计算机科学与工程学院顾小丰,极限定理,对有限状态E0,1,2,N的生灭过程，j，j=0,

38、1,2,N存在，与初始条件无关，且,即j，j=0,1,N为平稳分布。,对可列无限状态E0,1,2,n,的生灭过程，若有条件,成立，则j，j=0,1,2,存在，与初始条件无关，且,令,j0，,及,，即j，j=0,1,n,为平稳分布。,j0，,14078,2023/8/9,计算机科学与工程学院顾小丰,有限状态生灭过程的平稳分布,有限状态E=0,1,2,N的生灭过程X(t),t0是遍历的齐次连续参数马氏链。生灭过程存在极限分布即为平稳分布j,jE。Q0即,14079,2023/8/9,计算机科学与工程学院顾小丰,有限状态生灭过程的平稳分布的解,解得生灭过程X(t),t0，E=0,1,2,N的平稳分布

39、j,jE为：,当0 1 N-1，1 2 N 时，有,14080,2023/8/9,计算机科学与工程学院顾小丰,无限状态生灭过程的平稳分布,无限状态E=0,1,2,的生灭过程X(t),t0若满足,是遍历的齐次连续参数马氏链。生灭过程存在极限分布即为平稳分布j,jE。Q0即,及,14081,2023/8/9,计算机科学与工程学院顾小丰,无限状态生灭过程的平稳分布的解,解得生灭过程X(t),t0，E=0,1,2,的平稳分布j,jE为：,特别，当0 1=2，1 2 3 时，只要/1，则j,jE存在，且有,14082,2023/8/9,计算机科学与工程学院顾小丰,等待时间：顾客进入系统的时刻起到开始接受

40、服务止这段时间逗留时间：顾客在系统中的等待时间与服务时间之和,三、排队论,队长：系统中的顾客数(包括正在接受服务的顾客)等待队长：系统中的排队等待的顾客数,它们都是随机变量，是顾客和服务机构双方都十分关心的数量指标，应确定它们的分布及有关矩。,系统的忙期：从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲的这段系统连续繁忙的时间系统的闲期：系统连续保持空闲的时间忙期循环：相邻两次忙期开始的时间间隔,输出过程：也称离去过程，指接受服务完毕的顾客相继离开系统的过程。,在假定到达与服务是彼此独立的条件下，等待时间与服务时间是相互独立的。它们是顾客最关心的数量指标，应用中关心的是统计平衡下它们的

41、分布及期望值。,忙期反映了系统中服务员的工作强度。在排队系统中，统计平衡下忙期与闲期是交替出现的。,刻画输出过程的主要指标是相继离去的间隔时间和在一段已知时间内离去顾客的数目，这些指标从一个侧面反映了系统的工作效率。,。,14083,2023/8/9,计算机科学与工程学院顾小丰,1、M/M/1/,问题的叙述顾客到达为参数(0)的泊松过程，即相继到达的间隔时间序列n，n1独立、服从参数为(0)的负指数分布F(t)1-e-t，t0；顾客所需的服务时间序列n,n1独立、服从参数为(0)的负指数分布G(t)1-e-t，t0；系统中只有一个服务台；容量为无穷大，而且到达过程与服务过程彼此独立。,输入过程

42、,服务时间，排队,服务机构,系统容量,14084,2023/8/9,计算机科学与工程学院顾小丰,1)队长,N(t)，t0是可列无限状态E0,1,2,上的生灭过程，其参数为,14085,2023/8/9,计算机科学与工程学院顾小丰,1)队长（续）,在统计平衡的条件下(1)，,平均队长,等待队长的分布,平均等待队长,14086,2023/8/9,计算机科学与工程学院顾小丰,1)队长（续）,在等待条件下的等待队长分布,在等待条件下的平均等待队长,根据队长分布易知：p0=1也是系统空闲的概率，而正是系统繁忙的概率。显然，越大，系统就越繁忙。,14087,2023/8/9,计算机科学与工程学院顾小丰,2

43、）等待时间与逗留时间,假定顾客是先到先服务。,定理 在统计平衡(1)下，顾客的等待时间分布函数Wq(t)PWqt为Wq(t)1e-(1-)t，t0,平均等待时间为,等待时间的方差为,14088,2023/8/9,计算机科学与工程学院顾小丰,3）忙期,忙期长度的概率密度,其中，,为修正贝塞尔(Bessel)函数。,忙期长度的分布函数,14089,2023/8/9,计算机科学与工程学院顾小丰,3）忙期(续),平均忙期长度,一个忙期中所服务的平均顾客数,14090,2023/8/9,计算机科学与工程学院顾小丰,2、具有可变输入率的M/M/1/,顾客到达为参数(0)的泊松过程；顾客到达看到队长为k时，

44、进入系统的概率为ak(0ak1)，1a0a1ak0(k)，即排队越长进入的可能性越小(令ak)；顾客所需的服务时间序列n,n1独立、服从参数为(0)的负指数分布；系统中只有一个服务台；容量为无穷大，而且到达过程与服务过程彼此独立。,14091,2023/8/9,计算机科学与工程学院顾小丰,1）队长,我们仍用N(t)表示在时刻t系统中的顾客数，令,pij(t)PN(t+t)j|N(t)i，i,j0,1,2,于是，N(t)，t0是E0,1,2,上的生灭过程，其参数为,14092,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续）,定理 令pj，j=0,1,2,，则对一切，,pj，j0存在

45、，与初始条件无关，且,构成参数为的泊松概率分布。,14093,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续）,在统计平衡的条件下，有,平均队长,平均等待队长,14094,2023/8/9,计算机科学与工程学院顾小丰,2）等待时间与逗留时间,定理 在统计平衡下，进入系统接受服务的顾客的等待时间分布函数为：Wq(t)PWqt,平均等待时间为：,平均逗留时间为,14095,2023/8/9,计算机科学与工程学院顾小丰,3、具有可变服务率的M/M/1/,顾客到达为参数(0)的泊松过程；顾客所需的服务时间序列n,n1独立、服从负指数分布，具有两个服务率1、2(012)，当队长m（m是一个固

46、定的正整数）时，服务员用速率1工作，当队长m时，服务员用速率2工作；系统中只有一个服务台；容量为无穷大，而且到达过程与服务过程彼此独立。,14096,2023/8/9,计算机科学与工程学院顾小丰,1）队长,用N(t)表示在时刻t系统中的顾客数，令,pij(t)PN(t+t)j|N(t)i,i,j0,1,2,于是，N(t)，t0是E0,1,2,上的生灭过程，其参数为,14097,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续）,令,当21时，pj0，j=01,2,当21时，pj，j0存在，与初始条件无关，且,，则,14098,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续

47、）,在统计平衡的条件下，有,平均队长为,平均等待队长为,14099,2023/8/9,计算机科学与工程学院顾小丰,2）等待时间与逗留时间,在统计平衡下，有pj+pj，j=0,1,2,顾客在系统中的平均逗留时间为,顾客在系统中的平均等待时间为（由Little公式）,顾客在系统中接受的平均服务时间为,140100,2023/8/9,计算机科学与工程学院顾小丰,4、M/M/排队系统,顾客到达为参数(0)的泊松过程；顾客所需的服务时间序列n,n1独立、服从参数为(0)的负指数分布；系统中有无穷多（足够多）服务台，每个服务台是并行独立进行服务的。,140101,2023/8/9,计算机科学与工程学院顾小

48、丰,1）队长,于是，N(t),t0是可列无限状态E0,1,2,上的生灭过程，其参数为,我们用N(t)表示在时刻t系统中的顾客数，,140102,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续）,令，pj(t)PN(t)=j，pj，j0，则,140103,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续）,对于M/M/排队系统，因为有足够多的服务台，所以,平均队长,平均等待队长,平均等待时间,逗留时间服务时间,140104,2023/8/9,计算机科学与工程学院顾小丰,5、M/M/c/排队系统,顾客到达为参数(0)的泊松过程；顾客所需的服务时间序列n,n1独立、服从参数为(

49、0)的负指数分布；系统中有c(c1)个服务台独立并行服务；系统容量为无穷大，而且到达与服务是彼此独立的。,140105,2023/8/9,计算机科学与工程学院顾小丰,1）队长,我们用N(t)表示在时刻t系统中的顾客数，令,pij(t)PN(t+t)j|N(t)i，i,j0,1,2,于是，N(t)，t0是可列无限状态E0,1,2,上的生灭过程，其参数为,140106,2023/8/9,计算机科学与工程学院顾小丰,1）队长（续）,令，c，pj PN(t)=j，j0，,则当c1，有pj，j0存在，与初始条件无关，且,证明 利用生灭过程的极限定理即得。,140107,2023/8/9,计算机科学与工程

50、学院顾小丰,1）队长（续）,正在被服务的顾客数Nc：,平均等待队长：,由于NNqNc，所以平均队长为,140108,2023/8/9,计算机科学与工程学院顾小丰,2）等待时间与逗留时间,当c1，在统计平衡下，,平均等待时间为,平均逗留时间为,140109,2023/8/9,计算机科学与工程学院顾小丰,6、M/M/c/K混合制排队系统,顾客到达为参数(0)的泊松过程；每个顾客所需的服务时间独立、服从参数为(0)的负指数分布，且到达过程与服务过程彼此独立；容量为K，即系统中有K个位置；系统中有c个服务台独立地平行工作，cK；当K个位置已被顾客占用时，新到的顾客就自动离开，当系统中有空位置时，新到的