重庆大学：《通信网络中的排队论基础》研究生课程（讲义）第2章 平衡状态下的生灭过程

目录 第2章平衡状态下的生灭过程 1生灭过程 2.1.1生灭过程的定义 21.2生灭过程状态概率的微分差分方程 21.3生灭过程的简单应用 22生灭过程的一般平衡解 221生灭过程在极限情况下的概率分布 222生灭过程平衡状态下的方程 223排队系统的状态转移率图 224平衡方程的解 3M/M/1排队系统 24可变到达率的M/M/1排队系统 2.5应答服务系统M/M/∞ 6具有m个服务者的系统M/M/m 27有限存储系统M/M/1/N

I 目 录 第 2 章 平衡状态下的生灭过程 2.1 生灭过程 2.1.1 生灭过程的定义 2.1.2 生灭过程状态概率的微分差分方程 2.1.3 生灭过程的简单应用 2.2 生灭过程的一般平衡解 2.2.1 生灭过程在极限情况下的概率分布 2.2.2 生灭过程平衡状态下的方程 2.2.3 排队系统的状态转移率图 2.2.4 平衡方程的解 2.3 M / M / 1排队系统 2.4 可变到达率的 M / M / 1排队系统 2.5 应答服务系统 M / M /  2.6 具有m 个服务者的系统 M / M / m 2.7 有限存储系统 M / M / 1 / N

第2章平衡状态下的生灭过程 21生灭过程 21.1生灭过程的定义 顾名思义,生灭过程是起源于描述群体生长消亡的随机过程。生灭过程在排队论中 起着非常重要的作用,是研究排队论的出发点,本节我们将对生灭过程进行较为详细的 讨论。生灭过程理论实际上是研究排队系统最重要的数学工具,在排队系统中,常常将 顾客的到达理解为生灭过程中的“生”,顾客服务完毕离开服务系统理解为“灭”,因此 在一定条件下,排队系统所处状态随着事件变化的进程常可用生灭过程描述。 令N()表示系统t时刻所处的状态,即群体的个数,设状态空间=012,…}或 Ix={0.2…N},即所谓的“生”表示增加了个体,所谓“灭”表示减少了个体。生灭 过程是一种特殊的马尔柯夫链。它的基本特点是:状态的转移只能在相邻状态中进行 即:若在t=t时,N()=1,则当t=1+M时,N(+△M)只能取i-1,i,i+1这三个值 中的一个,而不能取其它值。所谓的生灭过程指的是无穷多个随机变量组成的序列 N(t≥0},它是一个时间参数连续、状态空间离散的随机过程。 1、生灭过程的严格定义(数学定义) 设{N()t≥0}为具有状态空间=012…}或l=01,2…N}的连续参数齐次马 尔柯夫链,如果其转移概率P()满足:对yi,j∈,对任意1≥0,有 (1)P{N(+△)=i+1|N()==1△t+0(△7),1>0为常数。有限状态时, 0,1,2,…,N-1;可数状态时,i=0,1,2, (2)P{N(+△)=1-1|N()=}=+o(△),>0为常数。有限状态时 2,…,N;可数状态时,t=1,2, (3)P(N(+△)=N()=}=0(△),b-小2 则称系统状恋随时间变化的过程{N(t≥0}为一个生灭过程。生灭过程也称为“增 与消”过程。 2、生灭过程比较形象地说明(物理解释) 为形象直观起见,可以把生灭过程作为描述某一城市人口总数的模型。生灭过程处 于状态i,就表示人口数为i,从i到i+1的状态转移称为一个人口出生,从i到1-1的状

464 第 2 章 平衡状态下的生灭过程 2.1 生灭过程 2.1.1 生灭过程的定义 顾名思义，生灭过程是起源于描述群体生长消亡的随机过程。生灭过程在排队论中 起着非常重要的作用，是研究排队论的出发点，本节我们将对生灭过程进行较为详细的 讨论。生灭过程理论实际上是研究排队系统最重要的数学工具，在排队系统中，常常将 顾客的到达理解为生灭过程中的“生”，顾客服务完毕离开服务系统理解为“灭”，因此， 在一定条件下，排队系统所处状态随着事件变化的进程常可用生灭过程描述。 令 N t 表示系统 t 时刻所处的状态，即群体的个数，设状态空间 I    0,1,2, 或 I N    0,1,2,,N ，即所谓的“生”表示增加了个体，所谓“灭”表示减少了个体。生灭 过程是一种特殊的马尔柯夫链。它的基本特点是：状态的转移只能在相邻状态中进行， 即：若在t  t 时， Nt  i ，则当t  t  t 时， Nt  t只能取i 1，i ，i 1这三个值 中的一个，而不能取其它值。所谓的生灭过程指的是无穷多个随机变量组成的序列   N t ，t  0 ，它是一个时间参数连续、状态空间离散的随机过程。 1、生灭过程的严格定义（数学定义） 设  N t ，t  0 为具有状态空间 I  0,1,2,或 I N  0,1,2,,N的连续参数齐次马 尔柯夫链，如果其转移概率 pij t 满足：对 i ， jI ，对任意t  0 ，有 （1） PNt t i Nt i t t           1 |      i   ， i  0 为常数。有限状态时， i  0,1,2,,N 1；可数状态时，i  0,1,2,。 （2） PNt t i Nt i t t           1|      i   ，  i  0 为常数。有限状态时， i 1,2,,N ；可数状态时，i 1,2,。 （3） PNt t jNt i t         |       ， i  j  2 。 则称系统状态随时间变化的过程Nt，t  0为一个生灭过程。生灭过程也称为“增 与消”过程。 2、生灭过程比较形象地说明（物理解释） 为形象直观起见，可以把生灭过程作为描述某一城市人口总数的模型。生灭过程处 于状态i ，就表示人口数为i ，从i 到i 1的状态转移称为一个人口出生，从i 到i 1的状

态转移称为一个人口死亡。41表示为在人口数为i的情况下的出生率,山1表示为在人口 数为i的情况下的死亡率。那么,生灭过程可以形象地比喻成 严格定义中的(1)表示在人口数为i的条件下,在区间(,t+△M)内有一个人口出 生的概率为λ△+O(△n)。 严格定义中的(2)表示在人口数为i的条件下,在区间(,t+△)内有一个人口死 亡的概率为1△M+o(△n 严格定义中的(3)表示在人口数为i的条件下,在区间(,t+M)内有两个及两个 以上的人口同时出生或同时死亡的概率为o(△) 根据生灭过程定义,并注意到∑P{N(t+△)=N(1)=}=1,由严格定义中的(1) 和(3)可得: PN(+△)=i|N()=l}=1-PN(t+△)=1+1()-=i}=1-4t+o(△) 上式表示在人口数为i的条件下,在区间(,t+△)内没有人口出生的概率为 1-△M+O(△n)。 由严格定义中的(2)和(3)可得: PN(+△)=l|N()=}=1-P{N(+△)=1-11|N(0)=i}=1-1+o(△7) 上式表示在人口数为i的条件下,在区间(,t+△)内没有人口死亡的概率为 1-△r+o(△r)。 212生灭过程状态概率的微分差分方程 生灭过程为{N(t≥0},我们希望求出在某个时刻t,人口数为i的概率,即 P()=P{N()=} 下面分析在区间(,t+△M)内人口数的可能变化情况。假定在时刻t+M人口数为i 则在区间(,t+M)中可能有以下四个事件发生 ①在时刻t人口数为1,而在(,t+△)内人口既无出生也无死亡 ②在时刻t人口数为1,而在(,t+△)内有一个人口出生还有一个人口死亡 ③在时刻t人口数为i-1,而在(t,t+△)内有一个人口出生 ④在时刻t人口数为i+1,而在(,t+△)内有一个人口死 这四种情况如图121所示

465 态转移称为一个人口死亡。i 表示为在人口数为i 的情况下的出生率， i 表示为在人口 数为i 的情况下的死亡率。那么，生灭过程可以形象地比喻成： 严格定义中的（1）表示在人口数为i 的条件下，在区间t，t  t内有一个人口出 生的概率为 t  t i   。 严格定义中的（2）表示在人口数为i 的条件下，在区间t，t  t内有一个人口死 亡的概率为 t  t i    。 严格定义中的（3）表示在人口数为i 的条件下，在区间t，t  t内有两个及两个 以上的人口同时出生或同时死亡的概率为ot。 根据生灭过程定义，并注意到    | 1    j I PNt t jNt i       ，由严格定义中的（1） 和（3）可得： P  N  t t i Nt i PNt t i Nt i  t t    |  1    1|  1 i   上式表示在人口数为 i 的条件下，在区间 t，t  t 内没有人口出生的概率为 t  t 1 i    。 由严格定义中的（2）和（3）可得： P  N  t t i Nt i PNt t i Nt i  t t    |  1    1|  1 i   上式表示在人口数为 i 的条件下，在区间 t，t  t 内没有人口死亡的概率为 t  t 1 i    。 2.1.2 生灭过程状态概率的微分差分方程 生灭过程为  N t ，t  0 ，我们希望求出在某个时刻t ，人口数为i 的概率，即： Pt PNt i i         下面分析在区间t，t  t内人口数的可能变化情况。假定在时刻t  t 人口数为i ， 则在区间  t，t  t 中可能有以下四个事件发生： ① 在时刻 t 人口数为i ，而在t，t  t内人口既无出生也无死亡； ② 在时刻 t 人口数为i ，而在t，t  t内有一个人口出生还有一个人口死亡； ③ 在时刻 t 人口数为i 1，而在t，t  t内有一个人口出生； ④ 在时刻 t 人口数为i 1，而在t，t  t内有一个人口死亡。 这四种情况如图 12.1 所示

无出生无死亡 生一人死亡一 图2.1进入状态i(人口数变为i)的可能情况 P1表示在M时间内人口既不出生又不死亡的概率 Pn表示在△t时间内有一个人口出生又有一个人口死亡的概率 P1表示在Mt时间内出生一个人口的概率; P1+1表示在M时间内死亡一个人口的概率。 我们可以把上述的转移过程写为 P(t+ Ar)=POp+ p(Pi+p_(pi-+P(p 把生灭过程定义代入上式,可得 P(+△)=P()-,△M+o(△)-u1△+o(△t)+P()E2△+o(△r)l△+o(△t +P(2-△M+o(△)+Pn(n△+o(△)+o△M)1≥1 将上式展开,忽略高阶无穷小,得 P(+△)=P()-(4+]+P1()2-M+P1()△+o(△n) 两边同减P(t),并除以M得 P(t+△t)-P (+A)P(O)+4-P-()+unP1()+c (2.1) △ 当i=0,不可能还有人口死亡,因而必须单独处理: P(+△)=P()-x2M+o(△)+P{()x4△+o(△)+o(△) 将上式展开,忽略高阶无穷小,得 466

466 i 1 t  t i 1 图 2.1 进入状态i （人口数变为i ）的可能情况 令： ii p 表示在t 时间内人口既不出生又不死亡的概率； ' pii 表示在t 时间内有一个人口出生又有一个人口死亡的概率； i i 1 p  表示在t 时间内出生一个人口的概率； i i 1 p  表示在t 时间内死亡一个人口的概率。 我们可以把上述的转移过程写为：         i i ii i ii i i i i pi i P t t P t p P t p P t p P t 1 1 1 1 '           把生灭过程定义代入上式，可得 P      t t P t   t t   t  t P t t o t t o t  i    i 1 i    1  i     i i    i   P    t   t t P t t o t o t  i1 i1    i1 i1     i 1 将上式展开，忽略高阶无穷小，得 P     t t P t  t P t t P t t  t i    i 1 i  i   i1 i1  i1 i1   两边同减 P  t i ，并除以t 得           t t P t P t P t t P t t P t i i i i i i i i i                     1 1  1 1 （2.1） 当i  0 ，不可能还有人口死亡，因而必须单独处理： P      t  t  P t   t  t  P t t  ot ot 0 0 0 1 1 1    将上式展开，忽略高阶无穷小，得

(+△)=B(t)-4B(t)△t+AP(t)△+o(△) 两边同减P(t),并除以M得 P(t+△)-P 42()+A4()+(M (22) 在(2.1)和(22)两式中令Mt→0得 dPQ=(+A)()+,.0)+aP()121(23) 2P()+p1P(t) (24) 这是一组同时包含微分运算和差分运算的方程,我们称它为微分差分方程,它表示 了生灭过程的动态特性,它的解就是我们所需的P()。 生灭过程的微分差分方程组是排队论理论中最基本的方程组,以后将看到,很多排 队模型中排队系统的状态概率的求解常求助于该微分差分方程组。 21.3生灭过程的简单应用 1、“纯生”过程 纯生”过程,其出生率为一个常数,死亡率为0,即 1= i=0,1.2, u= 为简单起见,我们假定当t=0时,人口数为0,由此有: P(0)= 0i≠0 由生灭过程的微分差分方程(23)和(24)式得: IP(t AP(+aP( i≥1 (25) dt dP(t (26) dt 首先解P(),根据(26)式的形式,我们可以立即得到P()的表达式 P() 代入初始条件P(0)=1,可知A=1,故 P()

467 P0 0 0 0 11 t t Pt Pt t Pt t t                    两边同减 P0  t ，并除以t 得        t t P t P t t P t t P t            0 0 1 1 0 0 （2.2） 在（2.1）和（2.2）两式中令t  0 得        P t P t P t dt dP t i i i i i i i i        1 1   1 1 i 1 （2.3）   P   t P t dt dP t 0 0 1 1 0     i  0 （2.4） 这是一组同时包含微分运算和差分运算的方程，我们称它为微分差分方程，它表示 了生灭过程的动态特性，它的解就是我们所需的 P t i 。 生灭过程的微分差分方程组是排队论理论中最基本的方程组，以后将看到，很多排 队模型中排队系统的状态概率的求解常求助于该微分差分方程组。 2.1.3 生灭过程的简单应用 1、“纯生”过程 “纯生”过程，其出生率为一个常数，死亡率为0 ，即 i   i  0，1,2，  0 i 为简单起见，我们假定当t  0时，人口数为0 ，由此有：         0 0 1 0 0 i i Pi 由生灭过程的微分差分方程（2.3）和（2.4）式得：   P  t P t dt dP t i i i     1 i  1 （2.5）   P  t dt dP t 0 0   i  0 （2.6） 首先解 P  t 0 ，根据（2.6）式的形式，我们可以立即得到 P t 0 的表达式：   t P t Ae 0  代入初始条件 P0 0 1，可知 A 1，故   t P t e 0 