随机过程与排队论07.

随机过程与排队论计算机科学与工程学院顾小丰Email：[e-mail]2019年12月14日星期六2019/12/14计算机科学与工程学院顾小丰26－2泊松过程•泊松过程的两个定义及其等价性•泊松过程的概率分布•泊松过程的数字特征•泊松过程的性质•非齐次泊松过程•复合泊松过程更新计数过程上一讲内容回顾,2,1,0k,e!k)t(k}P{N(t)tkP{N(h)=1}＝h+o(h)；P{N(h)2}＝o(h)均值函数m(t)＝E[N(t)]＝t；方差函数D(t)＝D[N(t)]＝t；特征函数；协方差函数C(s,t)＝min(s,t)；相关函数R(s,t)＝min(s,t)＋2st。)1e(tiue)u(平稳独立增量过程；点间间距序列Tn相互独立同分布，服从参数为的指数分布；等待时间序列n服从参数为的n阶爱而朗分布；2019/12/14计算机科学与工程学院顾小丰26－3本讲主要内容马尔可夫过程•马尔可夫过程的概念•马尔可夫过程的分类•离散参数马氏链•k步转移概率、k步转移矩阵•齐次马尔可夫链2019/12/14计算机科学与工程学院顾小丰26－4第三章马尔可夫过程当过程在t=t0时刻所处的状态已知的情况下，过程在时刻t(tt0)所处的状态与过程在t=t0时刻之前的状态无关。这种已知“现在”的条件下，“将来”与“过去”无关的性质，就是直观意义下的马尔可夫性或称为无后效性。具有无后效性的过程称为马尔可夫过程。马尔可夫过程是理论和实际应用都十分重要的一类随机过程。在工程系统中的噪声和信号分析、通信网络和输送现象的模拟、统计物理学、生物学、数字计算方法、经济管理和市场预测等领域中都有十分重要的作用和广泛应用。2019/12/14计算机科学与工程学院顾小丰26－5§3.1马尔可夫过程的概念给定随机过程{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)式性质称为具有马尔可夫性、无后效性或无记忆性。由条件分布函数的定义，(3.1)等价于F(xn;tn|x1,x2,…,xn-1;t1,t2,…,tn-1)＝F(xn;tn|xn-1;tn-1)。如果概率密度函数存在，它等价于f(xn;tn|x1,x2,…,xn-1;t1,t2,…,tn-1)＝f(xn;tn|xn-1;tn-1)。随机过程具有马尔可夫性质是说：当给定X(t1),X(t2),…,X(tn-1)时，X(tn)的条件分布只依赖于X(tn-1)的已知值，而与在tn-1以前X(t)的取值无关。2019/12/14计算机科学与工程学院顾小丰26－6转移概率给定马氏过程{X(t),tT}，条件概率p(s,t;x,y)＝P{X(t)y|X(s)=x}称为马氏过程的转移概率。若转移概率与s无关，则此过程称为齐次(时)马氏过程。马氏过程{X(t),tT}中，X(t)的取值x称为状态，X(t)＝x表示过程在时刻t处于状态x，过程所取状态的全体E＝{x：X(t)=x,tT}称为状态空间。2019/12/14计算机科学与工程学院顾小丰26－7马尔可夫过程的分类参数集T离散连续状态空间E离散离散参数马氏链连续参数马氏链连续离散参数马氏序列连续参数马氏过程2019/12/14计算机科学与工程学院顾小丰26－8例1一维随机游动在直线上非负整数点作随机游动的质点，当时刻n时处于位置i(i0)，时刻n+1时处于i+1的概率为pi，处于i-1的概率为qi，不动的概率为ri(pi+qi+ri=1)，若以X(n)表示时刻n质点的位置，那么{X(n),n=0,1,2,…}离散参数马氏链。这是因为，当X(n)＝i时，X(n+1),X(n+2),…等以后的行为只与X(n)=i有关，而与质点在n以前如何到达i是无关的。它的状态空间E={0,1,2,…}。2019/12/14计算机科学与工程学院顾小丰26－9例2独立过程{X(t),tT}是马尔可夫过程。证明设{X(t),tT}是独立过程，对于t1t2…tnT，X(t1),X(t2),…,X(tn)相互独立，因此P{X(tn)xn|X(t1)=x1,X(t2)=x2,…,X(tn-1)=xn-1}＝P{X(tn)xn}＝P{X(tn)xn|X(tn-1)=xn-1}马氏性成立，故独立过程{X(t),tT}是马尔可夫过程。2019/12/14计算机科学与工程学院顾小丰26－10贝努里随机序列特例贝努里随机序列，即X(n)，n=0,1,2,…是相互独立同分布的贝努里随机变量，X(n)01Pqp0p1,p+q=1n=1,2,…{X(n)，n=0,1,2,…}是离散参数马氏链。2019/12/14计算机科学与工程学院顾小丰26－11例3独立增量过程{X(t),t0}，(X(0)=0)是马尔可夫过程。证明设{X(t),tT}是独立增量过程，X(0)=0，对任意t1t2…tn，有P{X(tn)xn|X(t1)=x1,X(t2)=x2,…,X(tn-1)=xn-1}＝P{X(tn)-X(tn-1)xn-xn-1|X(t1)-X(t0)=x1,X(t2)-X(t1)=x2-x1,…,X(tn-1)-X(tn-2)=xn-1-xn-2}＝P{X(tn)-X(tn-1)xn-xn-1}＝P{X(tn)xn|X(tn-1)=xn-1}马氏性成立，故独立增量过程{X(t),t0}是马尔可夫过程。2019/12/14计算机科学与工程学院顾小丰26－12二项计数过程设{X(n),n=1,2,…}是贝努里随机序列，X(0)=0，X(n),n=1,2,…是相互独立同分布的贝努里随机变量，设称{Y(n),n=0,1,2,…}为二项计数过程(广义随机游动)，它是平稳独立增量过程，因而是离散参数马氏链。0)0(Y,,2,1n,)k(X)n(Yn1k2019/12/14计算机科学与工程学院顾小丰26－13例4泊松过程{N(t),t0}是马尔可夫过程。证明因为泊松过程{N(t),t0}是平稳独立增量过程，因而是马尔可夫过程。2019/12/14计算机科学与工程学院顾小丰26－14§3.2离散参数马氏链状态空间E和参数集T都是离散的马尔可夫过程称为离散参数马氏链，简称马氏链。即设{X(n),n=0,1,2,…}为随机序列，状态空间E={0,1,2,…}。如果对于任意非负整数k、n1n2…njm及in1,in2,…inj,im,im+kE马尔可夫性P{X(m+k)=im+k|X(n1)=in1,X(n2)=in2,…,X(nj)=inj,X(m)=im}＝P{X(m+k)=im+k|X(m)=im}成立，则称{X(n),n=0,1,2,…}为离散参数马尔可夫链，简称马氏链。2019/12/14计算机科学与工程学院顾小丰26－15k步转移概率设{X(n),n=0,1,2,…}为马氏链，E={0,1,2,…}，称条件概率pij(m,k)＝P{X(m+k)=j|X(m)=i}为马氏链{X(n),n=0,1,…}在m时刻的k步转移概率.k步转移概率的直观意义是：质点在时刻m时处于状态i，再经过k步(k个单位时间)处于状态j的条件概率。特别地，k=1时，pij(m,1)＝P{X(m+1)=j|X(m)=i}称为一步转移概率，简称转移概率。2019/12/14计算机科学与工程学院顾小丰26－16k步转移矩阵称矩阵)k,m(p)k,m(p)k,m(p)k,m(p)k,m(p)k,m(p)k,m(p)k,m(p)k,m(p))k,m(p()k,m(Pnn1n0nn11110n00100Ej,iij为马氏链{X(n),n=0,1,…}在m时刻的k步转移矩阵。一步转移矩阵P(m,1)简称转移矩阵。1)k,m(p0)k,m(pEjijij由转移概率的定义，显然有：2019/12/14计算机科学与工程学院顾小丰26－17齐次马尔可夫链若马氏链{X(n),n=0,1,2,…}的转移概率pij(m,k)与m无关，即pij(m,k)＝P{X(m+k)=j|X(m)=i}＝pij(k)；pij(m,1)＝P{X(m+1)=j|X(m)=i}＝pij(1)＝pij；则称{X(n),n=0,1,2,…}为齐次马尔可夫链，简称齐次马氏链。;1)k(pEjij。1pEjij齐次马氏链的k步转移矩阵记为：P(m,k)＝P(k)＝(pij(k))i,jE一步转移矩阵，简称转移矩阵，记为：P(m,1)＝P(1)＝P＝(pij)i,jE齐次马氏链的转移概率具有如下性质：0pij(k)1，0pij1，2019/12/14计算机科学与工程学院顾小丰26－18例1贝努里序列如上节例2所述，贝努里序列是一个齐次马氏链，其转移矩阵为pqpqP一般地，独立同分布的离散随机变量序列{X(n),n=0,1,2,…}都是齐次马氏链。2019/12/14计算机科学与工程学院顾小丰26－19例2随机游动一质点在数轴上的整数点上作随机游动的，以X(n)表示时刻n质点的位置。质点在某一时刻m时处于状态i，即X(m)=i，则下一步以概率q左移到状态i-1，即pi,i-1(m,1)=q；而以概率p右移到状态i+1，即pi,i+1(m,1)=p。因而质点将来所处的状态X(m+1),X(m+2),…,X(m+k)等仅与现在所处的状态X(m)=i有关，而与过去所处的状态无关。因此，随机游动{X(n),n=0,1,2,…}是齐次马氏链。随机游动的统计特征由它在边界的特点决定，下面给出几种特殊的情形。2019/12/14计算机科学与工程学院顾小丰26－201.自由(无限制)随机游动状态空间E＝{…,-2,-1,0,1,2,…}两端无限制。转移概率：pi,i-1＝q，pi,i+1＝p，其余pi,j＝0，ji-1,i+10p0q00000p0q00000p0q0P转移矩阵：2019/12/14计算机科学与工程学院顾小丰26－212.两个吸收壁随机游动状态空间E＝{1,2,3,4,5}。转移概率p11＝p55＝1；p1j＝0，j1；p5j＝0，j5；pi,i-1＝q，pi,i+1＝p，i=2,3,4；pi,j＝0，ji-1,i+1。质点运动到1,5时，永远留在那里，称状态1,5为吸收壁(状态)。10000p0q000p0q000p0q00001P转移矩阵：2019/12/14计算机科学与工程学院顾小丰26－223.带有两个反射壁的随机游动状态空间E＝{1,2,3,4,5}。转移概率：p11＝0，p12＝1，p1j＝0，j=3,4,5；p55＝0，p54＝1，p5j＝0，j=1,2,3；pi,i-1＝q，pi,i+1＝p，i=2,3,4；pij＝0，ji-1,i+1，i=2,3,4。状态1和5永远不能停留，称为反射壁。01000p0q000p0q000p0q00010P转移矩阵：2019/12/14计算机科学与工程学院顾小丰26－233.带有两个弹性壁的随机游动状态空间E＝{1,2,3,4,5}。转移概率：p11＝q，p12＝p，p1j＝0，j=3,4,5；p55＝p，p54＝q，p5j＝0，j=1,2,3；pi,i-1＝q，pi,i+1＝p，i=2,3,4；pij＝0，ji-1,i+1，i=2,3,4。状态1和5称为弹性壁。pq000p0q000p0q000p0q000pqP