电子科技大学计算机学院

电子科技大学计算机学院叶茂随机过程与排队论----------及其在计算机领域中的应用学习本课程的必要性计算机领域必须的数学知识进一深造，科研必须的数学基础本课程目标打下在计算机领域内研究必须的数学基础。本课程介绍的是随机过程与排队论，有非常强的应用背景。学习数学的唯一方法就是扎扎实实学习的一些方法和技巧，及推证和估计能力的训练。由于时间限制，本课程只涉及一些基本知识。更多的需要大家自学本课程安排24学时左右随机过程，16学时左右讲述排队论。我们将尽量涉及到工程应用领域。包括遗传算法，模拟退火算法，图像处理，计算机网络分析等等内容将会不定期布置习题，并作为期末成绩的一部份（具体比例待定)。联系方式若有任何意见和问题可以通过[e-mail]联系或者电话：81823465预约时间本课程通过电子科技大学教师主页提供ppt下载。有时候直接板书教学欢迎大家选修这门课，希望这门课程结束后，能成为朋友。参考书随机过程刘次华华中科技大学排队论唐应辉，唐小我电子科技大学*软计算方法*遗传算法*VisualC++图象处理工程实践概率的数学理论是本课程的基础之一，不清楚的请自己找一本这方面的书自学，现仅介绍几个概念。以后遇到相关概念我们会再讲。随机过程的引入随机过程的定义随机过程的分布随机过程的数字特征几种重要的随机过程随机过程产生于二十世纪初，起源于统计物理学领域，布朗运动和热噪声是随机过程的最早例子。随机过程理论社会科学、自然科学和工程技术的各个领域中都有着广泛的应用。例如：现代电子技术、现代通信、自动控制、系统工程的可靠性工程、市场经济的预测和控制、随机服务系统的排队论、储存论、生物医学工程、人口的预测和控制等等。只要研究随时间变化的动态系统的随机现象的统计规律，就要用到随机过程的理论。一、随机过程的定义电话问题设X(t)表示某电话台在[0,t)时间内收到用户的呼唤次数。对某个固定的t(0t)，X(t)是一个随机变量，它可以是任意非负整数，一个随机过程。布朗运动悬浮在液体中的微粒由于分子的随机碰撞而作布朗运动。设X(t)表示时刻t微粒所处位置的横座标，，对某个固定的t(0t)，X(t)是一族随机变量，即一个随机过程。热噪声电子元件或器件由于内部电子的随机热运动所引起的端电压X(t)称为热噪声电压。对于固定的t0，X(t)是一个随机变量，一个随机过程。设(Ω,F,P)是一个概率空间，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称为参数集。显然，随机过程X(t,)是定义在TΩ上的二元函数：一方面，当tT固定时，X(t,)是定义在上的随机变量；另一方面，当Ω固定时，X(t,)是定义在T上的函数，称为随机过程的样本函数。随机过程在时刻t所取的值X(t)=x称为时刻t时随机过程{X(t),tT}处于状态x，随机过程{X(t),tT}所有状态构成的集合称为状态空间，记为E，即：E＝{x：X(t)=x,tT}随机过程的分类：根据参数T及状态空间I是可列集或不可列集，可以把随机过程分为以下四种类型：1、T和I都是可列的2、T非可列，I可列3、T可列，I非可列4、T和I都非可列1，3可称为随机序列或时间序列，1，2也可称为可列过程二随机过程的分布和数字特征设{X(t),tT}是一个随机过程，对任意t1,t2,…,tnT，n维随机变量(X(t1),X(t2),…,X(tn))的联合分布函数F(t1,t2,…,tn;x1,x2,…,xn)t1,t2,…,tnT，P{X(t1)x1,X(t2)x2,…,X(tn)xn}，x1,x2,…,xnR称为随机过程{X(t),tT}的n维分布函数。这些分布函数的全体F={F(t1,t2,…,tn;x1,x2,…,xn),t1,t2,…,tnT,n0}称为随机过程{X(t),tT}n维分布函数族显然，随机过程{X(t),tT}分布函数族F有如下性质（1）对称性对于t1,t2,…,tn的任意排列{ti1,ti2,…,tin}F(t1,t2,…,tn;x1,x2,…,xn)=F(ti1,ti2,…,tin;xi1,xi2,…,xin)(2)相容性当mn时F(t1,t2,…,tm)=F(t1,…,tm,…,tn;x1,x2,…,xm,,…,).反之，对给定的满足对称性和相容性条件的分布函数族F，是否一定存在一个以F作为分布函数族的随机过程呢？Kolmogorov已经证明其存在随机过程{X(t),tT}的n维特征函数定义为(t1,t2,…,tm;u1,u2,…,un)}E{e)]X(tu)X(tu)X(ti[unn2211我们称{(t1,t2,…,tm;u1,u2,…,un)，t1,t2,…,tmT，n1}为随机过程{X(t),tT}的有限维特征函数族。例1利用投掷一枚硬币的试验，定义随机过程21,t2,tcos),t(X)t(X＝出现反面＝出现正面假定“出现正面”和“出现反面”的概率各为0.5，试求：1.X(t)的一维分布函数F(0.5,x)和F(1,x)；2.X(t)的二维分布函数F(0.5,1;x,y)。解：(1)由X(t)的定义求得概率分布为：X(0.5)01X(1)-12P0.50.5P0.50.5所以一维分布函数为：x111x05.00x0}x)5.0(X{P)x,5.0(Fx212x15.01x0}x)1(X{P)x,1(F(2)由于掷硬币试验是相互独立的，故(X(0.5),X(1))的联合概率密度为：X(1)X(0.5)-1200.250.2510.250.25所以二维分布函数为：y2x11)2y1,1x(or)2y,1x0(5.02y1,1x025.0)1y(or)0x(0}y)1(X,x)5.0(X{P)y,x;1,5.0(F，给定随机过程{X(t),tT}，称m(t)＝E[X(t)]，tT为随机过程{X(t),tT}的均值函数(数学期望)。若{X(t),tT}的状态空间是离散的，则X(t),tT是离散型随机变量，X(t)的概率分布为pk(t)＝P{X(t)=Xk}，k=1,2,…，则1kkk)t(px)]t(X[E)t(mdx)x,t(xf)]t(X[E)t(m若{X(t),tT}的状态空间是连续的，则X(t),tT是连续型随机变量，X(t)的一维概率密度为f(t,x)为，则给定随机过程{X(t),tT}，如果E[X2(t)]存在称{X(t)}为二阶矩过程。称D(t)＝D[X(t)]＝E[X(t)－m(t)]2，tT为随机过程{X(t),tT}的方差函数。显然，D(t)＝E[X(t)－m(t)]2＝E[X2(t)]－m2(t)。称为随机过程{X(t),tT}的均方差函数(标准方差函数)。)t(D)t(若X(t),tT是离散型随机变量，X(t)的概率分布为pk(t)＝P{X(t)=Xk}，k=1,2,…，则1kk2k2)t(p))t(mx()]t(m)t(X[E)t(Ddx)x,t(f))t(mx()]t(m)t(X[E)t(D22若X(t),tT是连续型随机变量，X(t)的一维概率密度为f(t,x)为，则协方差函数和相关函数给定随机过程{X(t),tT}，称B(s,t)＝cov(X(s),X(t))＝E[X(s)－m(s)][X(t)－m(t)]为随机过程{X(t),tT}的协方差函数。显然，B(s,t)＝E[X(s)X(t)]－m(s)m(t)，B(t,t)＝D(t)＝E[X(t)－m(t)]2。给定随机过程{X(t),tT}，称R(s,t)＝E[X(s)X(t)]为随机过程{X(t),tT}的相关函数。显然，B(s,t)＝R(s,t)－m(s)m(t)，R(s,t)＝B(s,t)＋m(s)m(t)。)()())(),(cov()()(),(),(tDsDtXsXtstsBts为随机过程{X(t),tT}的相关系数。均值函数m(t)是随机过程在时刻t的平均值，方差函数D(t)是随机过程在时刻t对均值的偏离程度，而协方差函数B(s,t)和R(s,t)相关函数反映随机过程在时刻s,t时的线性相关程度。给定两个随机过程{X(t),tT}和{Y(t),tT}，称BXY(s,t)＝E[X(s)－mX(s)][Y(t)－mY(t)]，s,tT为随机过程{X(t),tT}和{Y(t),tT}的互协方差函数。其中：mX(s)＝E[X(s)]，mY(t)＝E[Y(t)]。称RXY(s,t)＝E[X(s)Y(t)]为随机过程{X(t),tT}和{Y(t),tT}的互相关函数。显然，BXY(s,t)＝RXY(s,t)－mX(s)mY(t)。如果BXY(s,t)＝0，等价地RXY(s,t)＝mX(s)mY(t)，即E[X(s)Y(t)]＝E[X(s)]E[Y(t)]，则称{X(t),tT}和{Y(t),tT}互不相关。如果随机过程{X(t),tT}和{Y(t),tT}相互独立，则它们一定互不相关；反之，如果随机过程{X(t),tT}和{Y(t),tT}互不相关，一般不能推出它们相互独立。三、几种重要的随机过程1、独立增量过程2、马尔可夫过程3、正态过程和维纳过程4、平稳过程1.独立增量过程设随机过程{X(t),tT}，T＝[0,+)，如果对任意正整数n2，t1,t2,…,tnT且t1t2…tn，随机过程的增量X(t2)-X(t1),X(t3)-X(t2),…,X(tn)-X(tn-1)是相互独立的随机变量，则称{X(t),tT}为独立增量过程。特点：它在任一个时间间隔上过程状态的改变，不影响任一个与它不相重叠的时间间隔上状态的改变。实际中，如服务系统在某段时间间隔内的“顾客”数，电话传呼站电话的“呼叫”数等均可用这种过程来描述。因为在不相重叠的时间间隔内来到的“顾客”数，“呼叫”数都是相互独立。如果独立增量过程{X(t),tT}，T＝[0,+)，对所有的s,tT及h0,s+h,t+hTX(t+h)-X(s+h)与X(t)-X(s)有相同的概率分布，则称{X(t),tT}为平稳独立增量过程。平稳独立增量过程{X(t),tT}的增量X(t+)-X(t)，tT,t+T的概率分布仅依赖于而与t无关，即仅与时间区间的长度有关，而与起点无关，具有平稳性，即增量具有平稳性。例：X(t)表示悬浮在液面上微粒位置的横坐标，则{X(t)}是随机过程。由于微粒的运动是大量分子的随机碰撞引起的，因此{X(t)}是平稳独立增量过程。后面提到的微纳过程和泊松过程都是平稳独立增量过程2马尔可夫过程给定随机过程{X(t),tT}，如果对于参数中任意n个时刻ti,i=1,2,…,n，t1t2…tn有P{X(tn)xn|X(t1)x1,X(t2)x2,…,X(tn-1)xn-1}＝P{X(tn)xn|X(tn-1)xn-1}(3.1)则称随机过程{X(t),tT}为马尔可夫过程，简称马氏过程。具有(3.1)式性质称为具有马尔可夫性、无后效性或无记忆性。随机过程具有马尔可夫性质是说：当给定X(t1),X(t2),…,X(tn-1)时，X(tn)的条件分布只依赖于X(tn-1)的已知值，而与在tn-1以前X(t)的取值无关。3.正态过程(高斯过程)和维纳过程给定随机过程{X(t),tT}，若对任意