电子科技大学计算机学院

1、电子科技大学计算机学院叶 茂 随机过程与排队论-及其在计算机领域中的应用学习本课程的必要性计算机领域必须的数学知识进一深造，科研必须的数学基础本课程目标打下在计算机领域内研究必须的数学基础。本课程介绍的是随机过程与排队论，有非常强的应用背景。学习数学的唯一方法就是扎扎实实学习的一些方法和技巧，及推证和估计能力的训练。由于时间限制，本课程只涉及一些基本知识。更多的需要大家自学本课程安排24学时左右随机过程，16学时左右讲述排队论。我们将尽量涉及到工程应用领域。包括遗传算法，模拟退火算法，图像处理，计算机网络分析等等内容将会不定期布置习题，并作为期末成绩的一部份（具体比例待定)。联系方式若有任何意

2、见和问题可以通过Email sobolevus联系或者电话：81823465 预约时间本课程通过电子科技大学教师主页提供ppt下载。有时候直接板书教学欢迎大家选修这门课，希望这门课程结束后，能成为朋友。参考书随机过程 刘次华 华中科技大学排队论 唐应辉，唐小我 电子科技大学*软计算方法 *遗传算法*Visual C+图象处理工程实践 概率的数学理论是本课程的基础之一，不清楚的请自己找一本这方面的书自学，现仅介绍几个概念。以后遇到相关概念我们会再讲。第一章随机过程的基本概念随机过程的引入随机过程的定义随机过程的分布随机过程的数字特征几种重要的随机过程随机过程产生于二十世纪初，起源于统计物理学领域

3、，布朗运动和热噪声是随机过程的最早例子。随机过程理论社会科学、自然科学和工程技术的各个领域中都有着广泛的应用。例如：现代电子技术、现代通信、自动控制、系统工程的可靠性工程、市场经济的预测和控制、随机服务系统的排队论、储存论、生物医学工程、人口的预测和控制等等。只要研究随时间变化的动态系统的随机现象的统计规律，就要用到随机过程的理论。一、随机过程的定义电话问题设X(t)表示某电话台在0,t)时间内收到用户的呼唤次数。对某个固定的t(0t)，X(t)是一个随机变量，它可以是任意非负整数，一个随机过程。布朗运动悬浮在液体中的微粒由于分子的随机碰撞而作布朗运动。设X(t)表示时刻t微粒所处位置的横座标

4、，对某个固定的t(0t)，X(t)是一族随机变量，即一个随机过程。热噪声电子元件或器件由于内部电子的随机热运动所引起的端电压X(t)称为热噪声电压。对于固定的t0，X(t)是一个随机变量，一个随机过程。设(,F,P)是一个概率空间，T是一个参数集(TR)，X(t,)，tT，是T上的函数，如果对于每一个tT，X(t,)是(,F,P)上的随机变量，则称随机变量族X(t,)，tT为定义在(,F,P)上的随机过程(或随机函数)。简记为X(t)，tT，其中t称为参数，T称为参数集。显然，随机过程X(t,)是定义在T上的二元函数：一方面，当tT固定时，X(t,)是定义在上的随机变量；另一方面，当固定时，X

5、(t,)是定义在T上的函数，称为随机过程的样本函数。随机过程在时刻t所取的值X(t)=x称为时刻t时随机过程X(t),tT处于状态x，随机过程X(t),tT所有状态构成的集合称为状态空间，记为E，即：Ex：X(t)=x,tT随机过程的分类：根据参数T及状态空间I是可列集或不可列集，可以把随机过程分为以下四种类型：1、T和I都是可列的2、T非可列，I可列3、T可列，I非可列4、T和I都非可列1，3可称为随机序列或时间序列，1，2也可称为可列过程二 随机过程的分布和数字特征设X(t),tT是一个随机过程，对任意t1,t2,tnT，n维随机变量(X(t1),X(t2),X(tn)的联合分布函数F(t

6、1,t2,tn;x1,x2,xn)t1,t2,tnT，PX(t1)x1,X(t2)x2,X(tn)0称为随机过程X(t),tTn维分布函数族显然，随机过程X(t),tT分布函数族F有如下性质（1）对称性 对于t1,t2,tn的任意排列ti1,ti2,tin F(t1,t2,tn;x1,x2,xn)= F(ti1,ti2,tin;xi1,xi2,xin)相容性 当mn时 F(t1,t2,tm)= F(t1,tm,tn;x1,x2,xm,).反之，对给定的满足对称性和相容性条件的分布函数族F，是否一定存在一个以F作为分布函数族的随机过程呢？Kolmogorov已经证明其存在随机过程X(t),tT的

7、n维特征函数定义为(t1,t2,tm;u1,u2,un)我们称(t1,t2,tm;u1,u2,un)，t1,t2,tmT，n1为随机过程X(t),tT的有限维特征函数族。例1利用投掷一枚硬币的试验，定义随机过程假定“出现正面”和“出现反面”的概率各为0.5，试求：X(t)的一维分布函数F(0.5,x)和F(1,x)；X(t)的二维分布函数F(0.5,1;x,y)。解：(1)由X(t)的定义求得概率分布为：X(0.5)01X(1)-12P0.50.5P0.50.5所以一维分布函数为：(2)由于掷硬币试验是相互独立的，故(X(0.5),X(1)的联合概率密度为：X(1)X(0.5)-1200.25

8、0.2510.250.25所以二维分布函数为：给定随机过程X(t),tT，称m(t)EX(t)，tT为随机过程X(t),tT的均值函数(数学期望)。若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)为，则给定随机过程X(t),tT， 如果EX2(t)存在称X(t)为二阶矩过程。称D(t)DX(t)EX(t)m(t)2，tT为随机过程X(t),tT的方差函数。显然，D(t)EX(t)m(t)2EX2(t)m2

9、(t)。称为随机过程X(t),tT的均方差函数(标准方差函数)。若X(t),tT是离散型随机变量，X(t)的概率分布为pk(t)PX(t)=Xk，k=1,2,，则若X(t),tT是连续型随机变量，X(t)的一维概率密度为f(t,x)为，则协方差函数和相关函数给定随机过程X(t),tT，称B(s,t)cov(X(s),X(t)EX(s)m(s)X(t)m(t)为随机过程X(t),tT的协方差函数。显然，B(s,t)EX(s)X(t)m(s)m(t)，B(t,t)D(t)EX(t)m(t)2。给定随机过程X(t),tT，称R(s,t)EX(s)X(t)为随机过程X(t),tT的相关函数。显然，B(

10、s,t)R(s,t)m(s)m(t)，R(s,t)B(s,t)m(s)m(t)。为随机过程X(t),tT的相关系数。均值函数m(t)是随机过程在时刻t的平均值，方差函数D(t) 是随机过程在时刻t对均值的偏离程度，而协方差函数B(s,t)和R(s,t)相关函数反映随机过程在时刻s,t时的线性相关程度。给定两个随机过程X(t),tT和Y(t),tT，称BXY(s,t)EX(s)mX(s)Y(t)mY(t)，s,tT为随机过程X(t),tT和Y(t),tT的互协方差函数。其中：mX(s)EX(s)，mY(t)EY(t)。称RXY(s,t)EX(s)Y(t)为随机过程X(t),tT和Y(t),tT的

11、互相关函数。显然，BXY(s,t)RXY(s,t)mX(s)mY(t)。如果BXY(s,t)0，等价地RXY(s,t)mX(s)mY(t)，即EX(s)Y(t)EX(s)EY(t)，则称X(t),tT和Y(t),tT互不相关。如果随机过程X(t),tT和Y(t),tT相互独立，则它们一定互不相关；反之，如果随机过程X(t),tT和Y(t),tT互不相关，一般不能推出它们相互独立。三、几种重要的随机过程1、独立增量过程2、马尔可夫过程3、正态过程和维纳过程4、平稳过程1. 独立增量过程设随机过程X(t),tT，T0,+)，如果对任意正整数n2，t1,t2,tnT且t1t20,s+h,t+hTX(

12、t+h)-X(s+h)与X(t)-X(s)有相同的概率分布，则称X(t),tT为平稳独立增量过程。平稳独立增量过程X(t),tT的增量X(t+)-X(t)，tT,t+T的概率分布仅依赖于而与t无关，即仅与时间区间的长度有关，而与起点无关，具有平稳性，即增量具有平稳性。例：X(t)表示悬浮在液面上微粒位置的横坐标，则X(t)是随机过程。由于微粒的运动是大量分子的随机碰撞引起的，因此X(t)是平稳独立增量过程。后面提到的微纳过程和泊松过程都是平稳独立增量过程2马尔可夫过程给定随机过程X(t),tT，如果对于参数中任意n个时刻ti,i=1,2,n，t1t2tn有PX(tn)xn|X(t1)x1,X(

13、t2)x2,X(tn-1)xn-1PX(tn)xn|X(tn-1)0，W(t)N(0,2t)，0；则称随机过程W(t),t0是参数为2的维纳过程(布朗运动)。如果一个试验E满足下列条件：在相同的条件下可以重复进行；每次试验的结果不止一个，并且能事先明确知道试验的所有结果；一次试验结束之前，不能确定哪一个结果会出现则称此试验为随机试验。随机试验E的每一个最简单的试验结果，称为样本点，记为。全体样本点构成的集合，称为样本空间，记为。样本空间的子集组成的集类F，如果满足：F；若AF，则F;若AiF(i=1,2,)，则 ；那么称F为随机事件体(域)或代数。随机事件体F 的任意元素A成为随机事件；近含一

14、个样本点的事件成为基本事件；样本空间和F的二元体( ,F)称为可测空间。设(,F)是可测空间，如果定义随机事件体F上的实值集函数P(A)，AF满足：0P(A)1，AF；(非负性)P()1；(规范性)AiF(i=1,2,)，AiAj(ij)，则等式成立。(完全可加性)则称P为(,F)上的概率测度，简称概率。对任意AF，P(A)称为随机事件A的概率。样本空间 、随机事件体F和概率P组成的三元体(,F,P)称为概率空间。掷一枚均匀的骰子，观察出现点数的随机试验E。样本空间1,2,3,4,5,6；ii，i1,2,6，含有6个样本点；随机事件体F由的全体子集(共2664个)构成；F上的概率定义为P(A)，k为随机事件A包含的样本点数；(,F,P)为概率空间 。随机变量及其分布一、随机变量设(,F,P)为概率空间，如果定义样本空间上的一个单值实函数XX()， ，满足：X()xF-x+则称X()为随机变量。随机变量缩写为R.V.。二、分布函数设XX()是概率空间(,F,P)上的随机变量，对任意实数x，定义函数F(x)PXx-x+称为R.V.X的概率分布函