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

1、随机过程与排队论随机过程与排队论计算机科学与工程学院计算机科学与工程学院顾小丰顾小丰Email：TEL:2022年年3月月6日星期日日星期日2022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰教学内容教学内容1.1.概率论的基本知识概率论的基本知识2.2.随机过程的基本概念随机过程的基本概念1)1)随机过程的定义及分类随机过程的定义及分类2)2)随机过程的分布及数字特征随机过程的分布及数字特征3.3.独立过程与独立增量过程独立过程与独立增量过程4.4.泊松过程泊松过程5.5.更新过程更新过程1401402 22022-3-62022-3

2、-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰教学内容教学内容6.6.马尔可夫过程马尔可夫过程1)1)马尔可夫过程的概念马尔可夫过程的概念2)2)离散参数马氏链离散参数马氏链3)3)齐次马氏链状态的分类齐次马氏链状态的分类4)4)连续参数马氏链连续参数马氏链5)5)生灭过程生灭过程1401403 32022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰教学内容教学内容7. 排队系统概述排队系统概述8. M/M/1/排队排队9. M/M/排队系统排队系统10.M/M/c/排队系统排队系统11.M/M/c/K混合制排队系统混合制排队系统12.M/M/c/m/

3、m系统及损失制系统系统及损失制系统13.有备用品的有备用品的M/M/c/m+K/m系统系统14.一般服务的一般服务的M/G/1/ 排队系统排队系统1401404 42022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰一、概率论的基本知识一、概率论的基本知识 概率空间及其基本概念概率空间及其基本概念l随机试验、样本点、样本空间、随机试验、样本点、样本空间、随机事件体随机事件体l随机事件、基本事件和可测空间随机事件、基本事件和可测空间l概率、概率、概率空间、概率空间、概率的性质概率的性质l条件概率、乘法公式、事件的独立性、全概条件概率、乘法公式、事件的独立性、全概率

4、公式与贝叶斯公式率公式与贝叶斯公式1401405 52022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰1、条件概率空间、条件概率空间 设概率空间设概率空间(,F,P)，A F，B F，且，且P(A)0，在事件在事件A已经发生的条件下，事件已经发生的条件下，事件B发生的发生的条件概条件概率率定义为：定义为：)A(P)AB(P)A|B(P 给定概率空间给定概率空间(,F,P)，A F，且，且P(B)0，对，对任意任意B F有有P(B|A)对应，则条件概率对应，则条件概率P(B|A)是是(,F)上的概率，记上的概率，记P(B|A)PA，则，则(,F,PA)也是也是一

5、个概率空间，称为一个概率空间，称为条件概率空间条件概率空间。1401406 62022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2、乘法公式、乘法公式 设概率空间设概率空间(,F,P)，如果，如果A,B F，且，且P(AB)0，则下述乘法公式成立：，则下述乘法公式成立：P(AB)P(A)P(B|A)P(B)P(A|B)推广：推广： 设概率空间设概率空间(,F,P)，如果，如果Ai F，i=1,2,n且且P(A1A2An)0，则下述推广的乘法公式成立：，则下述推广的乘法公式成立： P(A1A2An)P(A1)P(A2|A1)P(A3|A1A2)P(An|A1A2

6、An-1)1401407 72022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3、全概率公式与贝叶斯公式、全概率公式与贝叶斯公式 设事件组设事件组B1,B2,Bn两两互不相容，即两两互不相容，即BiBj (1ijn)，且，且 ，P(Bi)0，i=1,2,n，则对，则对任意事件任意事件A，有，有n1iiB 1. 全概率公式全概率公式：2. 贝叶斯公式贝叶斯公式：； n1iii)B|A(P)B(P)A(P， n1iiijjj)B|A(P)B(P)B|A(P)B(P)A|B(Pj=1,2,n。1401408 82022-3-62022-3-6计算机科学与工程学院顾小

7、丰计算机科学与工程学院顾小丰4、随机变量及其分布、随机变量及其分布一、随机变量一、随机变量设设(,F,P)为概率空间，如果定义样本空间为概率空间，如果定义样本空间上的一个单上的一个单值实函数值实函数XX( )，满足，满足 ：X( )x F -x+则称则称X( )为为随机变量随机变量。随机变量缩写为。随机变量缩写为r.v.。二、分布函数二、分布函数 设设XX()是概率空间是概率空间(,F,P)上的随机变量，对上的随机变量，对任意实数任意实数x，定义函数，定义函数F(x)PXx -x0）的的k阶爱尔朗阶爱尔朗分布分布，记为记为XEk，其分布函数为，其分布函数为 0 x, 00 x,! i)x(e1

8、)x(F1k0iix14014015152022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰8、二维随机变量（向量）、二维随机变量（向量） 如果如果X和和Y是定义在同一概率空间是定义在同一概率空间(,F,P)上的两个随机变上的两个随机变量，则称量，则称(X,Y)为为二维随机变量二维随机变量(向量向量) ，记为，记为二维二维r.v.(X,Y)。 设设(X,Y)是二维随机变量，定义函数是二维随机变量，定义函数F(x,y)PXx,Yy，-x+，-y+为为r.v.(X,Y)的的二维联合分布函数二维联合分布函数。14014016162022-3-62022-3-6计算机科

9、学与工程学院顾小丰计算机科学与工程学院顾小丰9 9、离散型二维随机变量、离散型二维随机变量 如果二维若随机变量如果二维若随机变量(X,Y)(X,Y)至多只取可列无穷多对数至多只取可列无穷多对数值值(x(xi i,y,yj j) )，i,j=1,2,i,j=1,2,，令，令p pijijPXPXx xi i,Y,Yy yj j ，它满足：，它满足：(1) p(1) pijij00， (2) (2) 1 1，则称则称(X,Y)(X,Y)为为离散型二维随机变量离散型二维随机变量。称称 p pijijPXPXx xi i,Y,Yy yj j ，i,j=1,2,i,j=1,2,为为(X,Y)(X,Y)的

10、的联合分布律联合分布律。称。称 1i1jijp为为(X,Y)(X,Y)的的联合分布函数联合分布函数。 xxyyijxxyyjiiiiip)yY,xXP)y, x(F14014017172022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰边缘分布律、条件分布律边缘分布律、条件分布律为为r.v.X的的边缘分布律边缘分布律。称。称, 2 , 1ipxXPp1jijii ，为为r.v.Y的的边缘分布律边缘分布律。称。称, 2 , 1jpyYPp1iijjj ，为在已知为在已知Y=yj的条件下，的条件下，r.v.X的的条件分布律条件分布律。称。称, 2 , 1j , ip

11、ppjijj | i ，为在已知为在已知X=xi的条件下，的条件下，r.v.Y的的条件分布律条件分布律。, 2 , 1j , ipppiiji | j ，如果如果pijpi. p.j，i,j=1,2,，则称，则称r.v.X与与Y相互独立相互独立称称14014018182022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰10、连续型二维随机变量、连续型二维随机变量 若存在非负可积函数若存在非负可积函数f(x,y)，使得二维，使得二维r.v.(X,Y)的联合分的联合分布函数满足：布函数满足： yxdudv)v,u( f)y, x(Fxy则称则称(X,Y)为为连续型二

12、维随机变量连续型二维随机变量，并称，并称f(x,y)为为连续型二维随机变量的连续型二维随机变量的联合概率密度函数联合概率密度函数，简称，简称联合概率密度联合概率密度。14014019192022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰11、边缘分布函数、边缘分布函数设二维设二维r.v.(X,Y)的联合分布函数为的联合分布函数为F(x,y)，FX(x)F(x,+)，-x+称为称为r.v.X的的边缘分布函数边缘分布函数。FY(y)F(+,y)，-y+称为称为r.v.Y的的边缘分布函数边缘分布函数。设二维设二维r.v.(X,Y)的联合概率密度为的联合概率密度为f(

13、x,y)， ，-x+称为称为r.v.X的的边缘概率密度函数边缘概率密度函数。 ，-y+称为称为r.v.Y的的边缘概率密度函数边缘概率密度函数。 dy)y, x( f)x(fX dx)y, x( f)y(fY14014020202022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰12、条件概率密度与条件分布函数、条件概率密度与条件分布函数fY|X(y|x)f(x,y)fX(x)，-x+,-y+称为已知称为已知X=x的条件下，的条件下，r.v.Y的的条件概率密度条件概率密度。fX|Y(x|y)f(x,y)fY(y)，-x+,-y+称为已知称为已知Y=y的条件下，的条

14、件下，r.v.X的的条件概率密度条件概率密度。 dy)y, x( fdy)y, x( fdy)x|y(f)x|y(FyyX|YX|Y dx)y, x( fdx)y, x( fdx)y|x(f)y|x(FxxY|XY|X称为已知称为已知X=x的条件下，的条件下，r.v.Y的的条件分布函数条件分布函数。称为已知称为已知Y=y的条件下，的条件下，r.v.X的的条件分布函数条件分布函数。14014021212022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰13 随机变量的数字特征随机变量的数字特征1）数学期望）数学期望若离散型若离散型r.v.X的分布律为的分布律为pk

15、PX=Xk，k=1,2,，当，当时，称时，称 k1kkpx 1kkkpx)X(E为为r.v.X的的数学期望数学期望(均值均值)若连续型若连续型r.v.X的概率密度函数为的概率密度函数为f(x),x (-,+)，当，当 时，称时，称 dx)x( fxdx)x(xf)X(E为为r.v.X的的数学期望数学期望(均值均值)14014022222022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2）方差）方差设设X是随机变量，若是随机变量，若EX-E(X)2存在，称存在，称D(X)EX-E(X)2为为r.v.X的的方差方差(或记为或记为Var(X)，称，称为为r.v.X的

16、的均方差均方差或或标准差标准差。)X(DX 事实上有：事实上有：D(X)EX-E(X)2E(X22XE(X) E2(X)E(X2)-E2(X)14014023232022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3）常见随机变量的数学期望和方差）常见随机变量的数学期望和方差1) 泊松分布泊松分布X ( )：E(X)D(X) ；2) (负负)指数分布：指数分布：E(X)1/ ，D(X)1/ 2；3) 正态分布正态分布XN( , 2)：E(X) ，D(X) 2；4) 爱尔朗分布爱尔朗分布XEk：E(X)k/ ，D(X)k/ 2。 14014024242022-3-

17、62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3）k阶矩阶矩设设r.v.X有有E(|X|k)+ ，E|X-E(X)|k+ ，则，则称称 kE(Xk)为为X的的k阶原点矩阶原点矩；称称 kE(|X|k)为为X的的k阶绝对矩阶绝对矩；称称 kEX-E(X)k为为X的的k阶中心矩阶中心矩；称称 kE|X-E(X)|k为为X的的k阶绝对中心矩阶绝对中心矩。14014025252022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰4）协方差）协方差若若EX-E(X)Y-E(Y)，称，称cov(X,Y)EX-E(X)Y-E(Y)E(XY)-E(X)E(

18、Y)为随机变量为随机变量X和和Y的的协方差协方差，称，称)Y(D)X(D)Y,Xcov(XY 为随机变量为随机变量X和和Y的的相关系数相关系数，称，称 XY0为随机变量为随机变量X和和Y不相关不相关。14014026262022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰5）协方差矩阵）协方差矩阵设设n维维r.v.(X1,X2,Xn)，若，若cijcov(Xi,Xj)EXi-E(Xi)Xj-E(Xj)i,j1,2,n存在，则称存在，则称为为n维随机变量维随机变量(X1,X2,Xn)的的协方差矩阵协方差矩阵。 nn2n1nn22221n11211nnijccccc

19、cccc)c (C14014027272022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰6）特征函数）特征函数随机变量随机变量X的的特征函数特征函数定义为定义为 X(u)=E(eiuX)，i1当当r.v.X为离散型随机变量时，为离散型随机变量时， 1kkiuXXpe)u(k当当r.v.X为连续型随机变量时，为连续型随机变量时， dx)x(fe)u(XiuxX14014028282022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰二、二、随机过程的基本概念随机过程的基本概念v 1、随机过程、随机过程 设设(,F,P)是一个概率空间

20、，是一个概率空间，T是一个参数集是一个参数集(T R)，X(t, )，t T，是是T 上的二元函上的二元函数，如果对于每一个数，如果对于每一个t T，X(t, )是是(,F,P)上的上的随机变量，则称随机变量，则称随机变量族随机变量族X(t, )，t T为定为定义在义在(,F,P)上的上的随机过程随机过程(或或随机函数随机函数)。简记。简记为为X(t)，t T，其中，其中t称为称为参数参数，T称为称为参数集参数集。14014029292022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2、样本函数与状态空间、样本函数与状态空间v 随机过程随机过程X(t, )是定

21、义在是定义在T 上的二元函数上的二元函数：一：一方面，方面，当当t T固定时，固定时，X(t, )是定义在是定义在上的随上的随机变量机变量；另一方面，；另一方面，当当固定时，固定时，X(t, )是是定义在定义在T上的函数上的函数，称为随机过程的，称为随机过程的样本函数样本函数。v 随机过程在时刻随机过程在时刻t所取的值所取的值X(t)=x称为时刻称为时刻t时随时随机过程机过程X(t),t T处于处于状态状态x，随机过程，随机过程X(t),t T所有状态构成的集合称为所有状态构成的集合称为状态空间状态空间，记为记为E，即：，即：Ex：X(t)=x,t T14014030302022-3-6202

22、2-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3、随机过程的分类、随机过程的分类1) 按状态空间和参数集分类按状态空间和参数集分类2. 按概率分布规律分类按概率分布规律分类独立过程独立过程独立增量过程独立增量过程正态过程正态过程泊松过程泊松过程参数集参数集T 离散离散连续连续状态空间状态空间E 离散离散(离散参数离散参数)链链(连续参数连续参数)链链 连续连续随机序列随机序列随机过程随机过程维纳过程维纳过程平稳过程平稳过程马尔可夫过程马尔可夫过程14014031312022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰4、随机过程的分布、随机过程的

23、分布 设设X(t),t T是一个随机过程，对于每一个是一个随机过程，对于每一个t T，X(t)是一个随机变量，它的分布函数是一个随机变量，它的分布函数F(t,x)PX(t)x，t T，x R=(- ,+ )称为称为随机过程随机过程X(t),t T的的一维分布函数一维分布函数。 如果对于每一个如果对于每一个t T，随机变量，随机变量X(t)是连续型是连续型随机变量，存在非负可积函数随机变量，存在非负可积函数f(t,x)，使得，使得Rx,Tt ,dy)y, t ( f)x, t (Fx 则称则称f(t,x)，t T,x R为随机过程为随机过程X(t),t T的的一一维概率密度维概率密度(函数函数)

24、。此时。此时f(t,x)Fx(t,x)，t T，x R14014032322022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰二维分布函数二维分布函数 设设X(t),t T是一个随机过程，对任意是一个随机过程，对任意s,t T，(X(s),X(t)是一个二维随机变量，它的联合分布是一个二维随机变量，它的联合分布函数函数F(s,t;x,y)PX(s)x,X(t)y，t T，x R 称为称为随机过程随机过程X(t),t T的的二维分布函数二维分布函数。14014033332022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰二维概率密度

25、二维概率密度 如果如果(X(s),X(t)是连续型二维随机变量，是连续型二维随机变量，存在非负可积函数存在非负可积函数f(s,t;x,y)，使得，使得Ry, xTt , s,dvdu)v,u; t , s ( f)y, x; t , s (Fxy 成立，则称成立，则称f(s,t;x,y)，s,t T，x,y R为随机为随机过程过程X(t),t T的的二维概率密度二维概率密度(函数函数)。此。此时时yx)y, x; t , s (F)y, x; t , s ( f2 14014034342022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰5、随机过程的数字特征、随

26、机过程的数字特征给定随机过程给定随机过程X(t),t T，称，称m(t)EX(t)，t T为随机过程为随机过程X(t),t T的的均值函数均值函数(数学期望数学期望)。 若若X(t),t T的状态空间是离散的，则的状态空间是离散的，则X(t),t T是离散型随机变量，是离散型随机变量，X(t)的概率分布为的概率分布为pk(t)PX(t)=Xk，k=1,2,，则，则 1kkk) t (px)t (XE) t (m dx)x, t (xf)t (XE) t (m 若若X(t),t T的状态空间是连续的，则的状态空间是连续的，则X(t),t T是连续型随机变量，是连续型随机变量，X(t)的一维概率密

27、度为的一维概率密度为f(t,x)为，则为，则14014035352022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰方差函数方差函数给定随机过程给定随机过程X(t),t T，称，称D(t)DX(t)EX(t)m(t)2，t T为随机过程为随机过程X(t),t T的的方差函数方差函数。显然，。显然，D(t)EX(t)m(t)2EX2(t)m2(t)。称称 为随机过程为随机过程X(t),t T的的均方差函数均方差函数(标准方差函数标准方差函数)。 若若X(t),t T是离散型随机变量，是离散型随机变量，X(t)的概率分布为的概率分布为pk(t)PX(t)=Xk，k=

28、1,2,，则，则 1kk2k2) t (p)t (mx()t (m) t (XE) t (D dx)x, t ( f)t (mx()t (m) t (XE) t (D22 若若X(t),t T是连续型随机变量，是连续型随机变量，X(t)的一维概率密度为的一维概率密度为f(t,x)为，则为，则) t (D) t ( 14014036362022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰协方差函数和相关函数协方差函数和相关函数给定随机过程给定随机过程X(t),t T，称，称C(s,t)cov(X(s),X(t)EX(s)m(s)X(t)m(t)为随机过程为随机过程

29、X(t),t T的的协方差函数协方差函数。显然，。显然，C(s,t)EX(s)X(t)m(s)m(t)，C(t,t)D(t)EX(t)m(t)2。 给定随机过程给定随机过程X(t),t T，称，称R(s,t)EX(s)X(t)为随机过程为随机过程X(t),t T的的相关函数相关函数。显然，。显然，C(s,t)R(s,t)m(s)m(t)，R(s,t)C(s,t)m(s)m(t) 给定随机过程给定随机过程X(t),t T，称，称) t (D) s (D)t (X),s (Xcov() t () s () t , s (C) t , s ( 为随机过程为随机过程X(t),t T的的相关系数相关系数

30、。14014037372022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰6、重要随机过程、重要随机过程1）独立过程）独立过程 给定随机过程给定随机过程X(t),t T，如果对，如果对任意正整数任意正整数n及及任意任意t1,t2,tn T，随机变量，随机变量X(t1),X(t2),X(tn)相互独立，则称随机过程相互独立，则称随机过程X(t),t T为为独立过程独立过程。 特别，如果特别，如果X(n),n=1,2,3,是是相互独立的相互独立的随机随机变量变量，则称，则称X(n),n=1,2,3,为为独立随机序列独立随机序列。 14014038382022-3-6

31、2022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2）独立增量过程）独立增量过程 设随机过程设随机过程X(t),t T，T0,+ )，如果对任意正整数如果对任意正整数n 2，t1,t2,tn T且且t1t20,s+h,t+h TX(t+h)-X(s+h)与与X(t)-X(s)有相同的概率分布，则称有相同的概率分布，则称X(t),t T为为平稳独立增量过程平稳独立增量过程。14014040402022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰4）正态过程）正态过程给定随机过程给定随机过程X(t),t T，如果对任意正整数，如果对任意正整数n及及

32、t1,t2,tn T，n维随机变量维随机变量X (t1),X(t2),X(tn)的联合概率分布为的联合概率分布为n维正态分布，则称随机过程维正态分布，则称随机过程X(t),t T为为正态过程正态过程(或或高斯过程高斯过程)。设设X(t),t T为正态过程，则其有限维概率分为正态过程，则其有限维概率分布都是正态分布。布都是正态分布。14014041412022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰正态过程的一维概率分布正态过程的一维概率分布均值函数均值函数方差函数方差函数一维概率分布一维概率分布一维概率密度函数一维概率密度函数一维特征函数一维特征函数)t (

33、XE) t (m )t (XD) t (D )t (D),t (m(N) t (XRx,Tt ,e) t (D21)x, t ( f) t (D2)t (mx2 Ru,Tt ,e)u, t (u) t (imu) t (D212 22()2X1( ),2xfxetT xR2 212X( ),ui uuet T uR14014042422022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰正态过程的二维概率分布正态过程的二维概率分布均值函数向量均值函数向量二阶协方差矩阵二阶协方差矩阵二维概率分布二维概率分布二维概率密度函数二维概率密度函数二维特征函数二维特征函数 T

34、) t (m) s (m ) t (D) t , s (C) t , s (C) s (DC)C,(N)t (X),s (X(T yxx,eC21)y, x; t , s ( f)x( f)x(C)x(21211T vuu,e)v,u; t , s ()u(uuiuCu21TT14014043432022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰5） 维纳过程维纳过程(Brown运动运动)如果随机过程如果随机过程W(t),t0满足下列条件：满足下列条件：(1)W(0)0；(2)EW(t)0；(3)具有平稳独立增量；具有平稳独立增量；(4)t0，W(t)N(0,

35、2t)，(0)则 称 随 机 过 程则 称 随 机 过 程 W ( t ) , t 0 是 参 数 为是 参 数 为2的的 维 纳 过维 纳 过程程(或或布朗运动布朗运动)。14014044442022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰维纳过程的概率分布及数字特征维纳过程的概率分布及数字特征一维概率密度函数一维概率密度函数一维特征函数一维特征函数增量分布增量分布协方差函数协方差函数Rx, 0t,et21)x, t ( ft2x22 Ru, 0t,e)u, t (22tu21 )st, 0(N) s (W) t (W2 ) t , smin() t ,

36、s (C2 设设ts ，因因W(0)=0, 且且W( t )是平稳独立增量是平稳独立增量过程，故过程，故有相同分布有相同分布N(0,2(ts).)()()()(sWsstWsWtW )()0()(stWWstW 与与14014045452022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰维纳过程的二维概率分布维纳过程的二维概率分布均值函数向量均值函数向量二阶协方差矩阵二阶协方差矩阵二维概率分布二维概率分布二维概率密度函数二维概率密度函数二维特征函数二维特征函数 T00O st,tsssC2222 st),C,O(N)t (W),s (W(T )sysxy2tx(

37、)st ( s212222e) st ( s21)y, x; t , s ( f ts,e)v,u; t , s ()tvsuv2su(2222 14014046462022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰维纳过程的性质维纳过程的性质1) 维纳过程是平稳独立增量过程。维纳过程是平稳独立增量过程。2) 维纳过程是正态过程。维纳过程是正态过程。3) 维纳过程是马尔可夫过程。维纳过程是马尔可夫过程。14014047472022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰6）泊松过程）泊松过程如果取非负整数值的计数过程如果取非

38、负整数值的计数过程N(t),t 0满足：满足：1) N(0)0；2) 具有独立增量；具有独立增量；3) 对任意对任意0 s0,N(t) ( t),PN(t)=k；tke!k) t( 0ktkiuk) t (iuNe!k) t(ee E)u(2)均值函数均值函数m(t)EN(t) t；3)方差函数方差函数D(t)DN(t) t。2.一维特征函数一维特征函数)1e( ttte0ktkiuiuiueeee!k)te( 14014050502022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰泊松过程的概率分布和数字特征泊松过程的概率分布和数字特征3.二维概率分布二维概率

39、分布PN(s)=j, N(t)=kPN(s)=j,N(t)-N(s)=k-jts)st (jksje)!jk()st (e! j) s( ts0,e)!jk( ! j) st (stjkjk PN(s)=jPN(t-s)=k-j14014051512022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰泊松过程的概率分布和数字特征泊松过程的概率分布和数字特征4.协方差函数和相关函数协方差函数和相关函数协方差函数协方差函数C(s,t) min(s,t)，相关函数相关函数R(s,t) min(s,t) 2st。14014052522022-3-62022-3-6计算机科

40、学与工程学院顾小丰计算机科学与工程学院顾小丰泊松过程的性质泊松过程的性质 泊松过程是平稳独立增量过程；泊松过程是平稳独立增量过程； 设设N(t),t 0是是参数为参数为 的泊松过程，的泊松过程，Tn,n=1,2,为点间间距序列，则为点间间距序列，则Tn,n=1,2,是相互独立同分是相互独立同分布的随机变量，且都服从参数为布的随机变量，且都服从参数为 的的(负负)指数分布。指数分布。 设设N(t),t 0是是参数为参数为 的泊松过程，的泊松过程， n,n=1,2,为等待时间序列，则为等待时间序列，则 n (n, )，即概率密度，即概率密度为：为： 。0t, 0, 0t,et)n() t ( ft

41、1nn即即n阶爱而朗分布。阶爱而朗分布。14014053532022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰7、马尔可夫过程、马尔可夫过程定义定义1 给定随机过程给定随机过程X(t),t T，如果对于参数，如果对于参数中任意中任意n个时刻个时刻ti,i=1,2,n，t1t2tn有有PX(tn)xn|X(t1)=x1,X(t2)=x2,X(tn-1)=xn-1 PX(tn)xn|X(tn-1)=xn-1(3.1)则称则称随机过程随机过程X(t),t T为为马尔可夫过程马尔可夫过程，简称，简称马氏过程马氏过程。具有具有(3.1)式性质称为具有式性质称为具有马尔可

42、夫性马尔可夫性、无后效性无后效性或或无记忆性无记忆性。14014054542022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰转移概率转移概率定义定义2 给定马氏过程给定马氏过程X(t),t T，条件概率，条件概率p(s,t;x,y)PX(t)0，则此马氏链是遍历的，且极限，则此马氏链是遍历的，且极限分布是方程组分布是方程组s , 2 , 1j,ps1iijij 在满足条件在满足条件1, 0s1jjj 下的唯一解。下的唯一解。14014061612022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3）齐次马氏链的性质（续）齐次马氏

43、链的性质（续） 设设齐次马氏链齐次马氏链X(n),n=0,1,2,具有遍历性，则具有遍历性，则Ej,)n(plimjjn 即遍历的齐次马氏链的绝对分布与转移概率有相即遍历的齐次马氏链的绝对分布与转移概率有相同的极限。同的极限。 遍历的齐次马氏链的极限分布是平稳分布遍历的齐次马氏链的极限分布是平稳分布 设设X(n),n=0,1,2,的平稳分布为的平稳分布为vj,j E，则，则有有VVPn，n=0,1,2,14014062622022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3）齐次马氏链的性质（续）齐次马氏链的性质（续） 如果齐次马氏链如果齐次马氏链X(n),n

44、=0,1,2,的初始分布的初始分布pj,j E恰好是平稳分布，则对一切恰好是平稳分布，则对一切n有有pj(n)pj， n=0,1,2,，j E 即即0nPP 14014063632022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3）齐次马氏链的性质（续）齐次马氏链的性质（续） 设设齐次马氏链齐次马氏链X(n),n=0,1,2,的状态空间有的状态空间有限限E=1,2,s，若存在正整数，若存在正整数n0,对任意对任意i,j E，n0步转移概率步转移概率pij(n0)0，则此链是遍历的，且极限，则此链是遍历的，且极限分布等于平稳分布。分布等于平稳分布。 1, 0Pp

45、EjjjEiijij或记或记1401406464首返首返概率概率平均返平均返回时间回时间周期周期以三个层次区分状态类型以三个层次区分状态类型状态状态非常返态非常返态常返态常返态零常返态零常返态正常返态正常返态有周期有周期非周期非周期遍历态遍历态4）齐次马氏链状态的分类）齐次马氏链状态的分类2022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰14014065652022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰5）连续参数马尔可夫链）连续参数马尔可夫链 设设随机过程随机过程X(t),t 0，状态空间，状态空间E=0,1,2,。若对

46、于。若对于0t1t2tn0，使得对任意，使得对任意i,j E，都有，都有pij(t0)0，则此齐次马氏链，则此齐次马氏链X(t),t 0为遍历的齐次马氏链。为遍历的齐次马氏链。即即Ej,) t (plimjijt 存在且与存在且与i i无关，并且极限分布无关，并且极限分布 j j, ,j j EE是唯一的平稳是唯一的平稳分布：分布：。 EiijijEjjj) t (p, 1, 05.5. 对固定的对固定的i,ji,j，函数，函数p pijij(t)(t)是是t0t0的一致连续函数。的一致连续函数。6.6. 满足连续性条件的连续参数齐次马氏链满足连续性条件的连续参数齐次马氏链X(t),tX(t)

47、,t 0 0 存存在下列极限在下列极限ji,qt) t (plim)2(,qqt) t (p1lim)1(ijij0tiiiii0t 其中其中q qi i表示在时刻表示在时刻t t时通过状态时通过状态i i的的通过速度通过速度( (或或通过强通过强度度) )；q qijij表示时刻表示时刻t t时从状态时从状态i i转移到状态转移到状态j j的的速度速度( (或或强强度度) )，q qijij统称统称转移速度转移速度。14014070702022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰转移概率函数的性质转移概率函数的性质(续续2)7.设齐次马氏链设齐次马氏链

48、X(t),t 0，状态空间，状态空间E=0,1,2,s，其转移速度，其转移速度 ij ,Ejijiiijqq, 0q8.设设X(t),t 0为连续参数齐次马氏链，当为连续参数齐次马氏链，当qi+ ， qi 时，满足柯尔莫哥洛夫后退微分方程时，满足柯尔莫哥洛夫后退微分方程 ij ,Ejijq ik,Ekkjikijiij) t (pq) t (pqdt) t (dp即即P(t)QP(t)9.设设X(t),t 0为连续参数齐次马氏链为连续参数齐次马氏链,当当qi0，及及 j11jj211j10011，即，即 j，j=0,1,n,为平稳分布。为平稳分布。10jj j0，14014078782022-

49、3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰有限状态有限状态生灭过程的平稳分布生灭过程的平稳分布 有限状态有限状态E=0,1,2,N的生灭过程的生灭过程X(t),t 0是是遍历的齐次连续参数马氏链。生灭过程存在极限遍历的齐次连续参数马氏链。生灭过程存在极限分布即为平稳分布分布即为平稳分布 j,j E。 Q0即即 11N, 2 , 1j ,)(Ejj1N1NNN1j1j1j1jjjj110014014079792022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰有限状态有限状态生灭过程的平稳分布的解生灭过程的平稳分布的解解得生灭过程解

50、得生灭过程X(t),t 0，E=0,1,2,N的平稳分布的平稳分布 j,j E为：为： N, 2 , 1k,11kk1k0k211k10k1N1jj211j100 当当 0 1 N-1 ， 1 2 N 时，有时，有 N, 2 , 1k,0jk1jN0j014014080802022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰无限状态无限状态生灭过程的平稳分布生灭过程的平稳分布无限状态无限状态E=0,1,2,的生灭过程的生灭过程X(t),t 0若满足若满足 1, 2 , 1j ,)(Ejj1j1j1j1jjjj1100是遍历的齐次连续参数马氏链。生灭过程存在极限分

51、布是遍历的齐次连续参数马氏链。生灭过程存在极限分布即为平稳分布即为平稳分布 j,j E。 Q0即即 1jj211j101及及 j11jj211j1001114014081812022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰无限状态无限状态生灭过程的平稳分布的解生灭过程的平稳分布的解 解得生灭过程解得生灭过程X(t),t 0，E=0,1,2,的平稳分布的平稳分布 j,j E为：为： , 3 , 2 , 1k,11kk1k0k211k10k11jj211j100特别，当特别，当 0 1 = 2 ， 1 2 3 时，只要时，只要 / 1，则，则 j,j E存在，且

52、存在，且有有, 2 , 1 , 0k,1kk 14014082822022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰 等待时间等待时间：顾客进入系统的时刻起到开始接受服务止这：顾客进入系统的时刻起到开始接受服务止这段时间段时间 逗留时间逗留时间：顾客在系统中的等待时间与服务时间之和：顾客在系统中的等待时间与服务时间之和三、三、 排队论排队论队长队长：系统中的顾客数：系统中的顾客数(包括正在接受服务的顾客包括正在接受服务的顾客)等待队长等待队长：系统中的排队等待的顾客数：系统中的排队等待的顾客数它们都是随机变量，是顾客和服务它们都是随机变量，是顾客和服务机构双方

53、都十分关心的数量指标，机构双方都十分关心的数量指标，应确定它们的分布及有关矩。应确定它们的分布及有关矩。 系统的忙期系统的忙期：从顾客到达空闲的系统，服务立即开始，：从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲的这段系统连续繁忙的时间直到系统再次变为空闲的这段系统连续繁忙的时间 系统的闲期系统的闲期：系统连续保持空闲的时间：系统连续保持空闲的时间 忙期循环忙期循环：相邻两次忙期开始的时间间隔：相邻两次忙期开始的时间间隔 输出过程输出过程：也称：也称离去过程离去过程，指接受服务完毕的顾客相继，指接受服务完毕的顾客相继离开系统的过程。离开系统的过程。在假定到达与服务是彼此独立的条在假定

54、到达与服务是彼此独立的条件下，等待时间与服务时间是相互件下，等待时间与服务时间是相互独立的。它们是顾客最关心的数量独立的。它们是顾客最关心的数量指标，应用中关心的是统计平衡下指标，应用中关心的是统计平衡下它们的分布及期望值。它们的分布及期望值。忙期反映了系统中服务员的工作强忙期反映了系统中服务员的工作强度。在排队系统中，统计平衡下忙度。在排队系统中，统计平衡下忙期与闲期是交替出现的。期与闲期是交替出现的。刻画输出过程的主要指标是相继离刻画输出过程的主要指标是相继离去的间隔时间和在一段已知时间内去的间隔时间和在一段已知时间内离去顾客的数目，这些指标从一个离去顾客的数目，这些指标从一个侧面反映了系

55、统的工作效率。侧面反映了系统的工作效率。14014083832022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰1、M/M/1/ 1) 问题的叙述问题的叙述v 顾客顾客到达为参数到达为参数 ( 0)的泊松过程的泊松过程，即相继到达的，即相继到达的间隔间隔时间序列时间序列 n，n 1独立、独立、服从参数为服从参数为 ( 0)的负指数分的负指数分布布F(t)1-e- t，t 0；v 顾客顾客所需的服务时间序列所需的服务时间序列 n,n 1独立、独立、服从参数为服从参数为 ( 0)的负指数分布的负指数分布G(t)1-e- t，t 0；v 系统中只有一个服务台；系统中只

56、有一个服务台；v 容量为无穷大，而且到达过程与服务过程彼此独立。容量为无穷大，而且到达过程与服务过程彼此独立。输入过程输入过程服务时间，排服务时间，排队队服务机构服务机构系统容量系统容量14014084842022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰1) 队长队长 2| ji |) t(o1i , 1ij) t(ot0i , 1ij) t(ot) t(pijN(t)，t 0是可列无限状态是可列无限状态E0,1,2,上的生灭过程，上的生灭过程，其参数为其参数为 1i,0i,ii14014085852022-3-62022-3-6计算机科学与工程学院顾小丰计

57、算机科学与工程学院顾小丰1) 队长（续）队长（续）在统计平衡的条件下在统计平衡的条件下( 1)，1,1)1( jjp)N(ENj0j0jj 平均队长平均队长 1j,p0j,pp jNP1j10q等待队长的分布等待队长的分布1,1)1( jjpN20j0j1jq1j 平均等待队长平均等待队长14014086862022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰1) 队长（续）队长（续）1j , 1,)1()1(1NP jNP1NP1N, jNP1N| jNP1j21jqqqqqqq 在等待条件下的等待队长分布在等待条件下的等待队长分布1,11)1N|N(Eqq

58、在等待条件下的平均等待队长在等待条件下的平均等待队长根据队长分布易知：根据队长分布易知： p0=1 也是也是系统空闲的概率系统空闲的概率，而，而 正是正是系系统繁忙的概率统繁忙的概率。显然，。显然， 越大，系统就越繁忙越大，系统就越繁忙。14014087872022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2）等待时间与逗留时间）等待时间与逗留时间1) 假定顾客是先到先服务。假定顾客是先到先服务。 定理定理 在统计平衡在统计平衡( 0)的泊松过程的泊松过程 ；v 顾客到达看到队长为顾客到达看到队长为k时，进入系统的概率为时，进入系统的概率为ak(0ak1)，1

59、a0a1ak0(k )，即排队越长进入的，即排队越长进入的可能性越小可能性越小(令令ak )；v 顾客所需的服务时间序列顾客所需的服务时间序列 n,n 1独立、服从参数为独立、服从参数为 ( 0)的负指数分布；的负指数分布；v 系统中只有一个服务台；系统中只有一个服务台；v 容量为无穷大，而且到达过程与服务过程彼此独立。容量为无穷大，而且到达过程与服务过程彼此独立。1k1 14014091912022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰1）队长）队长我们仍用我们仍用N(t)表示在时刻表示在时刻t系统中的顾客数，系统中的顾客数，令令pij( t)PN(t+

60、 t)j|N(t)i，i,j0,1,2, 2| ji |),t(o1i , 1ij),t(ot0i , 1ij),t(ot1i) t(pij于是，于是，N(t)，t 0是是E0,1,2,上的生灭过程，其参数上的生灭过程，其参数为为 1i,0i,1iii14014092922022-3-62022-3-6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰1）队长（续）队长（续）定理定理 令令pj ，j=0,1,2,，则对一切，则对一切 ，pj，j 0存在，与初始条件无关，且存在，与初始条件无关，且 ) t (plimjt , 2 , 1 , 0j ,e! jpjj 构成参数为构成参数为 的泊松