随机过程与排队论PPT课件

《随机过程与排队论PPT课件》由会员分享，可在线阅读，更多相关《随机过程与排队论PPT课件（30页珍藏版）》请在装配图网上搜索。

1、随机过程与排队论随机过程与排队论计算机科学与工程学院计算机科学与工程学院顾小丰顾小丰Email：20232023年年3 3月月10 10日星期五日星期五2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰282上一讲内容回顾上一讲内容回顾 独立增量过程独立增量过程 正态过程正态过程 维纳过程维纳过程2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰283本讲主要内容本讲主要内容泊松过程泊松过程 泊松过程的两个定义及其等价性泊松过程的两个定义及其等价性 泊松过程的概率分布泊松过程的概率分布 泊松过程的数字特征泊松过程的数字特征 泊松过程的性质泊松过程的性质

2、非齐次泊松过程非齐次泊松过程 复合泊松过程复合泊松过程更新计数过程更新计数过程2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2843.泊松过程泊松过程 泊松过程是一种很重要的计数过程，它在随机过泊松过程是一种很重要的计数过程，它在随机过程的理论和应用方面都起着重要的作用，特别在程的理论和应用方面都起着重要的作用，特别在运筹学和排队论中的作用更为显著。运筹学和排队论中的作用更为显著。泊松过程的实例很多，例如：在泊松过程的实例很多，例如：在0,t)时间内，时间内，到达某超级市场的顾客数到达某超级市场的顾客数N(t)；某电话交换台的呼唤数某电话交换台的呼唤数N(t)；某车间发

3、生故障的机器数某车间发生故障的机器数N(t)；某计数器接受到的粒子数某计数器接受到的粒子数N(t)；某通信系统出现的误码数某通信系统出现的误码数N(t)；等等，等等，N(t),t 0都是泊松过程的典型实例。都是泊松过程的典型实例。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰285泊松过程的定义泊松过程的定义1如果取非负整数值的计数过程如果取非负整数值的计数过程N(t),t 0满足：满足：N(0)0；具有独立增量；具有独立增量；1)对任意对任意0 st,N(t)-N(s)服从参数为服从参数为(t-s)泊松泊松分布，即分布，即,2,1,0k,e!k)st(k)PN(t)-

4、N(s)st(k 则称则称N(t),t 0为为参数参数(或平均率、强度或平均率、强度)为为 的的(齐齐次次)泊松过程泊松过程。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰286泊松过程的定义泊松过程的定义2如果取非负整数值得计数过程如果取非负整数值得计数过程N(t),t 0满足下满足下列条件：列条件：N(0)0；具有平稳独立增量；具有平稳独立增量；PN(h)=1 h+o(h)；PN(h)2o(h)则称则称N(t),t 0为为参数参数(或平均率、强度或平均率、强度)为为 的的(齐齐次次)泊松过程泊松过程。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾

5、小丰287等价定理等价定理定理定理 泊松过程的定义泊松过程的定义1与定义与定义2是等价的。是等价的。证明证明 12：条件条件a)与与1)相同。条件相同。条件b)可由可由2)和和3)直接得到。直接得到。PN(h)=1PN(h)-N(0)=1he!1)h(2khke!k)h(2)h(NP)h(o)h(oh1)h(o!2)h(2 即即d)。h1-h+o(h)h+o(h)即即c)。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰288证明证明21：条件条件1)与与a)相同。条件相同。条件2)由由b)直接得到。只要证明：直接得到。只要证明：N(t)(t 0)服从参数为服从参数为 t

6、泊松分布。泊松分布。设设pk(t)PN(t)=k，利用归纳法证明：，利用归纳法证明：,2,1,0k,e!k)t()t(ptkk (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,h)h(o)t(ph)t(p)ht(p000 10)0(NP)0(p)t(p)t(p0h000得得，令令解得：解得：p0(t)e-t。独立增量独立增量过程过程平稳性平稳性 PN(t)=0PN(h)=0 p0(t)1-h+o(h)因为因为1 i)h(NP0i 2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰289证明证

7、明(续续1)(2)k 1pk(t+h)PN(t+h)=k,h)h(o)t(p)t(ph)t(p)ht(p1kkkk ),3,2,1k(,0k)0(NP)0(p)t(p)t(p)t(p0hk1kkk 得得，令令 k0jjkN(t)h)N(t,jPN(t)k0jjkN(h)P jPN(t)2k0jjkj11k0kk0jjkj(h)(t)pp(h)(t)pp(h)(t)pp(h)(t)pppk(t)1-h+o(h)+pk-1(t)h+o(h)+o(h)，2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2810证明证明(续续2)k=1时时,0)0(pe)t(p)t(p1t11解得

8、：解得：p1(t)te-t，所以，所以k=1时结论成立。时结论成立。假设假设k-1时结论成立，时结论成立，。t1k1ke)!1k()t()t(p ,0)0(p)t(p)t(p)t(pk1kkk解解得得。tkke!k)t()t(p 结论成立。结论成立。由归纳法知，对一切由归纳法知，对一切k=0,1,2,，结论成立。，结论成立。得证得证。,2,1,0k,e!k)t(k)t(NPtk 再由平稳独立增量性质，对一切再由平稳独立增量性质，对一切0 s0,N(t)(t),PN(t)=k；tke!k)t(0ktkiuk)t(iuNe!k)t(ee E)u(均值函数均值函数m(t)EN(t)t；方差函数方差函

9、数D(t)DN(t)t。一维特征函数一维特征函数)1e(ttte0ktkiuiuiueeee!k)te(2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2812泊松过程的概率分布和数字特征泊松过程的概率分布和数字特征 二维概率分布二维概率分布PN(s)=j,N(t)=kPN(s)-N(0)=j,N(t)-N(s)=k-jts)st(jksje)!jk()st(e!j)s(ts0,e)!jk(!j)st(stjkjk PN(s)=j PN(t-s)=k-j独立增量独立增量过程过程2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2813泊松过程的概率分布

10、和数字特征泊松过程的概率分布和数字特征 协方差函数和相关函数协方差函数和相关函数协方差函数协方差函数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)st表示在表示在0,t)内泊松事件还没有出现，因此，事内泊松事件还没有出现，因此，事件件T1t的发生当且仅当没有泊松事件在在的发生当且仅当没有泊松事件在在0,t)内出现，内出现，于是对于是对t0，有，有P T1tPN(t)=0e-tP T1t1-P T1t 1-e-t对对tt0因此，因此，T1的分布函数为的分布函数为 0t,00t,e1)

11、t(FtT12023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2816T1的概率密度为的概率密度为 0t,00t,e)t(ftT1即即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 1)T(E1 ts12dxdy)y,x(fsT,tTP tsT|Tdxdy)y(f)y|x(f12sTPed

12、y)y(fe1tst 21sPTt|Tyf(y)dy sTP tTP12 2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2817当当s0时，可见时，可见T2也服从参数为也服从参数为的（负）指数分布且的（负）指数分布且T2与与T1独立同分布。独立同分布。类似地，可用数学归纳法证明当类似地，可用数学归纳法证明当n2时，时，Tn，n=1,2,相互独立，都相互独立，都参数为参数为的（负）指数分布。的（负）指数分布。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2818泊松过程的性质泊松过程的性质3设设N(t),t 0是是参数为参数为 的泊松过程，的泊松过

13、程，n,n=1,2,为等待时间序列，则为等待时间序列，则 n(n,)，即概率密度，即概率密度为：为：。0t,0,0t,et)n()t(ft1nn即即n阶爱而朗分布。阶爱而朗分布。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2819非齐次泊松过程非齐次泊松过程,2,1,0k,e!k)m(tt)m(tk)t)-N(tPN(t)m(tt)m(tk000000 如果计数过程如果计数过程N(t),t 0满足下列条件：满足下列条件：N(0)0；N(t),t 0是独立增量过程；是独立增量过程；PN(t+t)-N(t)=1(t)t+0(t)；PN(t+t)-N(t)20(t)则称则称

14、N(t),t 0为为参数参数(或平均率、强度或平均率、强度)为为(t)的的非齐次泊非齐次泊松过程松过程。特别，当。特别，当(t)=时，即为时，即为齐次泊松过程齐次泊松过程。定理定理 若过程若过程N(t),t 0是非齐次泊松过程，则在时间间是非齐次泊松过程，则在时间间距距t0,t0+t)内事件内事件A出现出现k次的概率为：次的概率为：式中式中 t0ds)s()t(m2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2820例例某镇有一小商店，每日某镇有一小商店，每日8:00开始营业。从开始营业。从8:00到到11:00平均顾客到达率线性增加，在平均顾客到达率线性增加，在8:0

15、0顾客平均顾客平均到达到达5人人/小时；小时；11:00到达率达最高峰到达率达最高峰20人人/小时。小时。从从11:00到到13:00平均顾客到达率为平均顾客到达率为20人人/小时。从小时。从13:00到到17:00平均顾客到达率线性下降，平均顾客到达率线性下降，17:00顾顾客到达率为客到达率为12人人/小时。假设在不相交的时间间隔小时。假设在不相交的时间间隔内到达商店的顾客数是相互独立的，试问在内到达商店的顾客数是相互独立的，试问在8:30到到9:30时间内无顾客到达商店的概率为多少？在这段时间内无顾客到达商店的概率为多少？在这段时间机内到达商店的顾客的均值为多少？时间机内到达商店的顾客的

16、均值为多少？2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2821解解设设8:00为为t=0，11:00为为t=3，13:00为为t=5，17:00为为t=9，第二天第二天8:00可以为可以为t=9。于是，顾客到达率是周期为。于是，顾客到达率是周期为9的的函数：函数：9t5),5t(2205t3,203t0,t55)t(t)(t-9)根据题意，在根据题意，在0,t)内到达的顾客数内到达的顾客数N(t),t 0是一个非是一个非齐次泊松过程。齐次泊松过程。在在8:30到到9:30无顾客到达商店的概率为无顾客到达商店的概率为10dt)t55(dt)t()5.0(m)5.1(m

17、0eeee)5.1,5.0(p5.15.05.15.0 在在8:30到到9:30到达商店的顾客均值为到达商店的顾客均值为10dt)t55(dt)t55()5.0(m)5.1(m5.005.10 2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2822复合泊松过程复合泊松过程 设设N(t),t 0是是参数为参数为 的泊松过程，的泊松过程，Yn，n=1,2,是相互独立同分布的随机变量序列，且是相互独立同分布的随机变量序列，且N(t),t 0与与Yn，n=1,2,相互独立，令相互独立，令0t,Y)t(X)t(N1nn 称称X(t),t 0为为复合泊松过程复合泊松过程。2023-

18、3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2823例例 某计算机相继两次出现故障的间隔时间为相互某计算机相继两次出现故障的间隔时间为相互独立服从相同指数分布的独立服从相同指数分布的随机变量。每出现一次随机变量。每出现一次故障需要支付费用来维修。故障需要支付费用来维修。设发生在不同时间的设发生在不同时间的故障所花的维修费用是相互独立、同分布的，且故障所花的维修费用是相互独立、同分布的，且维修费和故障时间相互独立，设维修费和故障时间相互独立，设Yn表示第表示第n次的次的维修费，维修费，N(t)表示表示0,t)内的故障次数，内的故障次数，令令0t,Y)t(X)t(N1nn 表示表示

19、0,t)内的总费用，则内的总费用，则X(t),t 0是一个复合泊是一个复合泊松过程。松过程。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2824复合泊松过程的数字特征复合泊松过程的数字特征 设设X(t),t 0为复合泊松过程，为复合泊松过程，。其中。其中N(t),t0是参数为是参数为的泊松过程，的泊松过程，Yn，n=1,2,，相互独立、与，相互独立、与Y同分布的，同分布的，Y的特征函数为的特征函数为y(u)，则复合泊松过程有：，则复合泊松过程有：特征函数为特征函数为X(t,u)=均值函数均值函数 mX(t)=EX(t)=EN(t)EY=tEY方差函数方差函数 DX(t

20、)=DX(t)=EX2(t)-E2X(t)=tEY2=EN(t)EY2N(t)nn 1X(t)Y Yt(u)1e 2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2825更新计数过程更新计数过程 设设N(t),t 0是计数过程，如果它的时间间距是计数过程，如果它的时间间距T1,T2,Tn,是相互独立同分布的随机变量，是相互独立同分布的随机变量，则则称称N(t),t 0为为更新计数过程更新计数过程，称时间间距为，称时间间距为更新更新间距间距。例例 电话台呼唤流电话台呼唤流 设有一个不断受到呼唤的电话台，电话呼唤设有一个不断受到呼唤的电话台，电话呼唤到达的时间为到达的时间为

21、1,2,n，时间间距，时间间距T1=1,T2=2-1，Tn=n-n-1是相互独立同分布的随机变量。是相互独立同分布的随机变量。令令N(t)表示在时间表示在时间0,t)内收到的呼唤数，则内收到的呼唤数，则N(t),t 0是更新过程。是更新过程。2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2826更新过程的概率分布更新过程的概率分布 设设N(t),t 0是更新过程，其是更新过程，其到达的时间为到达的时间为 1,2,n。时间间距。时间间距T1=1,T2=2-1,Tn=n-n-1相互独立都与随机变相互独立都与随机变量量T同分布。设同分布。设T的分布函数为的分布函数为FT(t)

22、，故，故Tk的分布函数为的分布函数为FTk(t)FT(t)，k=1,2,令更新计数过程的分布函数为令更新计数过程的分布函数为FN(t)(k)PN(t)k，则，则由时间间距由时间间距T的特征函数的特征函数 T(u)，计算到达时间，计算到达时间 k 的特征函数：的特征函数：k1iiTk(u)(u)kk 由由 k的特征函数的特征函数 k(u)确定确定 k的概率密度的概率密度f k(t)和分布函和分布函数数F k(t)；由由F k(t)确定更新计数过程确定更新计数过程N(t),t 0的分布函数。的分布函数。由于事件由于事件 kt与事件与事件N(t)k等价，从而等价，从而P ktPN(t)k1-PN(t

23、)k即即F k(t)1FN(t)(k)故故FN(t)(k)1F k(t)2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2827更新过程的均值函数更新过程的均值函数设设N(t),t 0是更新过程，则是更新过程，则 0kk)t(NPk)t(NE)t(m 0k)t(F)t(Fk1kk )t(F)t(F2)t(F)t(F1)t(F)t(F0322110 1k)t(Fk2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2828本讲主要内容本讲主要内容泊松过程泊松过程 泊松过程的两个定义及其等价性泊松过程的两个定义及其等价性 泊松过程的概率分布泊松过程的概率分布 泊松过程的数字特征泊松过程的数字特征 泊松过程的性质泊松过程的性质 非齐次泊松过程非齐次泊松过程 复合泊松过程复合泊松过程更新计数过程更新计数过程2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2829下一讲内容预告下一讲内容预告马尔可夫过程马尔可夫过程 马尔可夫过程的概念马尔可夫过程的概念 马尔可夫过程的分类马尔可夫过程的分类 离散参数马氏链离散参数马氏链2023-3-10计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2830P9812.15.19.习习 题题 三三