随机过程与排队论.ppt

随机过程与排队论,计算机科学与工程学院顾小丰Email：2023年6月26日星期一,2023/6/26,计算机科学与工程学院顾小丰,282,上一讲内容回顾,独立增量过程正态过程维纳过程,2023/6/26,计算机科学与工程学院顾小丰,283,本讲主要内容,泊松过程泊松过程的两个定义及其等价性泊松过程的概率分布泊松过程的数字特征泊松过程的性质非齐次泊松过程复合泊松过程更新计数过程,2023/6/26,计算机科学与工程学院顾小丰,284,3.泊松过程,泊松过程是一种很重要的计数过程，它在随机过程的理论和应用方面都起着重要的作用，特别在运筹学和排队论中的作用更为显著。泊松过程的实例很多，例如：在0,t)时间内，到达某超级市场的顾客数N(t)；某电话交换台的呼唤数N(t)；某车间发生故障的机器数N(t)；某计数器接受到的粒子数N(t)；某通信系统出现的误码数N(t)；等等，N(t),t0都是泊松过程的典型实例。,2023/6/26,计算机科学与工程学院顾小丰,285,泊松过程的定义1,如果取非负整数值的计数过程N(t),t0满足：N(0)0；具有独立增量；对任意0st,N(t)-N(s)服从参数为(t-s)泊松分布，即,则称N(t),t0为参数(或平均率、强度)为的(齐次)泊松过程。,2023/6/26,计算机科学与工程学院顾小丰,286,泊松过程的定义2,如果取非负整数值得计数过程N(t),t0满足下列条件：N(0)0；具有平稳独立增量；PN(h)=1h+o(h)；PN(h)2o(h)则称N(t),t0为参数(或平均率、强度)为的(齐次)泊松过程。,2023/6/26,计算机科学与工程学院顾小丰,287,等价定理,定理 泊松过程的定义1与定义2是等价的。,证明 12：条件a)与1)相同。条件b)可由2)和3)直接得到。PN(h)=1PN(h)-N(0)=1,即d)。,h1-h+o(h)h+o(h)即c)。,2023/6/26,计算机科学与工程学院顾小丰,288,证明,21：条件1)与a)相同。条件2)由b)直接得到。只要证明：N(t)(t0)服从参数为t泊松分布。设pk(t)PN(t)=k，利用归纳法证明：,(1)k=0，p0(t+h)PN(t+h)=0PN(t)=0,N(t+h)-N(t)=0PN(t)=0PN(t+h)-N(t)=0,解得：p0(t)e-t。,独立增量过程,平稳性,PN(t)=0PN(h)=0 p0(t)1-h+o(h),因为,2023/6/26,计算机科学与工程学院顾小丰,289,证明(续1),(2)k1,pk(t+h)PN(t+h)=k,pk(t)1-h+o(h)+pk-1(t)h+o(h)+o(h)，,2023/6/26,计算机科学与工程学院顾小丰,2810,证明(续2),k=1时,解得：p1(t)te-t，所以k=1时结论成立。,假设k-1时结论成立，,解,得,结论成立。由归纳法知，对一切k=0,1,2,，结论成立。得证,再由平稳独立增量性质，对一切0st,得出3)。,2023/6/26,计算机科学与工程学院顾小丰,2811,泊松过程的概率分布和数字特征,一维概率分布及均值和方差函数对任意t0,N(t)(t),PN(t)=k,均值函数m(t)EN(t)t；方差函数D(t)DN(t)t。一维特征函数,2023/6/26,计算机科学与工程学院顾小丰,2812,泊松过程的概率分布和数字特征,二维概率分布,PN(s)=j,N(t)=kPN(s)-N(0)=j,N(t)-N(s)=k-j,ts,PN(s)=j PN(t-s)=k-j,独立增量过程,2023/6/26,计算机科学与工程学院顾小丰,2813,泊松过程的概率分布和数字特征,协方差函数和相关函数协方差函数C(s,t)min(s,t)，相关函数R(s,t)min(s,t)2st。,证明 R(s,t)EN(s)N(t)EN(s)N(t)-N(s)+N(s)stEN(s)EN(t)-N(s)+EN2(s)s(t-s)+s+(s)2s+2stC(s,t)R(s,t)-m(s)m(t)s+2st-sts一般地，C(s,t)min(s,t)，R(s,t)min(s,t)2st。,2023/6/26,计算机科学与工程学院顾小丰,2814,泊松过程的性质1,泊松过程是平稳独立增量过程；,设N(t)表示区间0,t)内事件出现的次数，N(t),t0是参数为的泊松过程，设1,2,n分别表示事件第1、2、n次出现的时间，称k为事件第k次出现的等待时间；Tk(k1)表示事件第k-1次出现到第k次出现的点间间距。Tkk-k-1，k=1,2,n，0=0kT1+T2+Tk，k=1,2,n,2023/6/26,计算机科学与工程学院顾小丰,2815,泊松过程的性质2,设N(t),t0是参数为的泊松过程，Tn,n=1,2,为点间间距序列，则Tn,n=1,2,是相互独立同分布的随机变量，且都服从参数为的(负)指数分布。,证明 因为T1表示事件第1次出现以前所需要的时间，所以事件T1t表示在0,t)内泊松事件还没有出现，因此，事件T1t的发生当且仅当没有泊松事件在在0,t)内出现，于是对t0，有P T1tPN(t)=0e-tP T1t1-P T1t 1-e-t对tt0因此，T1的分布函数为,2023/6/26,计算机科学与工程学院顾小丰,2816,T1的概率密度为,即T1服从参数为的（负）指数分布。T2表示事件第1次出现至第2次出现的点间间距 P T2t|T1=s1P在(s1,s1+t)内没有事件出现|T1=s1 P在(s1,s1+t)内没有事件出现P N(s1+t)N(s1)=0P N(t)=0e-t,2023/6/26,计算机科学与工程学院顾小丰,2817,当s0时，可见T2也服从参数为的（负）指数分布且T2与T1独立同分布。类似地，可用数学归纳法证明当n2时，Tn，n=1,2,相互独立，都参数为的（负）指数分布。,2023/6/26,计算机科学与工程学院顾小丰,2818,泊松过程的性质3,设N(t),t0是参数为的泊松过程，n,n=1,2,为等待时间序列，则 n(n,)，即概率密度为：,即n阶爱而朗分布。,2023/6/26,计算机科学与工程学院顾小丰,2819,非齐次泊松过程,如果计数过程N(t),t0满足下列条件：N(0)0；N(t),t0是独立增量过程；PN(t+t)-N(t)=1(t)t+0(t)；PN(t+t)-N(t)20(t)则称N(t),t0为参数(或平均率、强度)为(t)的非齐次泊松过程。特别，当(t)=时，即为齐次泊松过程。,定理 若过程N(t),t0是非齐次泊松过程，则在时间间距t0,t0+t)内事件A出现k次的概率为：,式中,2023/6/26,计算机科学与工程学院顾小丰,2820,例,某镇有一小商店，每日8:00开始营业。从8:00到11:00平均顾客到达率线性增加，在8:00顾客平均到达5人/小时；11:00到达率达最高峰20人/小时。从11:00到13:00平均顾客到达率为20人/小时。从13:00到17:00平均顾客到达率线性下降，17:00顾客到达率为12人/小时。假设在不相交的时间间隔内到达商店的顾客数是相互独立的，试问在8:30到9:30时间内无顾客到达商店的概率为多少？在这段时间机内到达商店的顾客的均值为多少？,2023/6/26,计算机科学与工程学院顾小丰,2821,解,设8:00为t=0，11:00为t=3，13:00为t=5，17:00为t=9，第二天8:00可以为t=9。于是，顾客到达率是周期为9的函数：,(t)(t-9),根据题意，在0,t)内到达的顾客数N(t),t0是一个非齐次泊松过程。在8:30到9:30无顾客到达商店的概率为,在8:30到9:30到达商店的顾客均值为,2023/6/26,计算机科学与工程学院顾小丰,2822,复合泊松过程,设N(t),t0是参数为的泊松过程，Yn，n=1,2,是相互独立同分布的随机变量序列，且N(t),t0与Yn，n=1,2,相互独立，令,称X(t),t0为复合泊松过程。,2023/6/26,计算机科学与工程学院顾小丰,2823,例,某计算机相继两次出现故障的间隔时间为相互独立服从相同指数分布的随机变量。每出现一次故障需要支付费用来维修。设发生在不同时间的故障所花的维修费用是相互独立、同分布的，且维修费和故障时间相互独立，设Yn表示第n次的维修费，N(t)表示0,t)内的故障次数，令,表示0,t)内的总费用，则X(t),t0是一个复合泊松过程。,2023/6/26,计算机科学与工程学院顾小丰,2824,复合泊松过程的数字特征,设X(t),t0为复合泊松过程，。其中N(t),t0是参数为的泊松过程，Yn，n=1,2,，相互独立、与Y同分布的，Y的特征函数为y(u)，则复合泊松过程有：特征函数为X(t,u)=均值函数 mX(t)=EX(t)=EN(t)EY=tEY方差函数 DX(t)=DX(t)=EX2(t)-E2X(t)=tEY2=EN(t)EY2,2023/6/26,计算机科学与工程学院顾小丰,2825,更新计数过程,设N(t),t0是计数过程，如果它的时间间距,T1,T2,Tn,是相互独立同分布的随机变量，则称N(t),t0为更新计数过程，称时间间距为更新间距。,例 电话台呼唤流 设有一个不断受到呼唤的电话台，电话呼唤到达的时间为1,2,n，时间间距T1=1,T2=2-1，Tn=n-n-1是相互独立同分布的随机变量。令N(t)表示在时间0,t)内收到的呼唤数，则N(t),t0是更新过程。,2023/6/26,计算机科学与工程学院顾小丰,2826,更新过程的概率分布,设N(t),t0是更新过程，其到达的时间为1,2,n。时间间距T1=1,T2=2-1,Tn=n-n-1相互独立都与随机变量T同分布。设T的分布函数为FT(t)，故Tk的分布函数为FTk(t)FT(t)，k=1,2,令更新计数过程的分布函数为FN(t)(k)PN(t)k，则,由时间间距T的特征函数T(u)，计算到达时间k 的特征函数：,由k的特征函数k(u)确定k的概率密度fk(t)和分布函数Fk(t)；由Fk(t)确定更新计数过程N(t),t0的分布函数。,由于事件kt与事件N(t)k等价，从而PktPN(t)k1-PN(t)k即Fk(t)1FN(t)(k)故FN(t)(k)1Fk(t),2023/6/26,计算机科学与工程学院顾小丰,2827,更新过程的均值函数,设N(t),t0是更新过程，则,2023/6/26,计算机科学与工程学院顾小丰,2828,本讲主要内容,泊松过程泊松过程的两个定义及其等价性泊松过程的概率分布泊松过程的数字特征泊松过程的性质非齐次泊松过程复合泊松过程更新计数过程,2023/6/26,计算机科学与工程学院顾小丰,2829,下一讲内容预告,马尔可夫过程马尔可夫过程的概念马尔可夫过程的分类离散参数马氏链,2023/6/26,计算机科学与工程学院顾小丰,2830,P9812.15.19.,习 题 三,