GIG1排队系统队长的强大数定律和中心极限定理

1、GI/G/1排队系统队长的强大数定律和中心极限定理董海玲 (深圳大学数学与计算科学学院,深圳, 518060) 摘要：本文首先证明当服务强度小于1时,GI/G/1排队系统的队长是一个特殊的马尔可夫骨架过程正常返的Doob骨架过程,然后运用马尔可夫骨架过程的强大数定律和中心极限定理等重要结果,给出了队长的累积过程的期望和方差, 并给出了该累积过程满足强大数定律和中心极限定理的充分条件. 关键词：GI/G/1排队系统;队长;马尔可夫骨架过程;强大数定律;中心极限定理 Law of Strong Large Numbers and Central Limit Theorem of Queue Len

2、gth in a GI/G/1 Queueing System Dong Hailing(School of Mathematics and Computer Science, Shenzhen University, 518060) Abstract First, when service intensity is less than 1, the queue length in a queueing system is proved to be a positive recurrent Doob skeleton process, which is a special case of Ma

3、rkov skeleton processes. Second, the expectation and variance of the cumulative process of the queue length are obtained by using law of strong large numbers, central limit theorem and other important results of Markov skeleton processes. And finally, sufficient conditions for law of strong large nu

4、mbers and central limit theorem of the accumulated process are given, respectively. Keywords GI/G/1 queueing system; Queue Length; Markov skeleton processes; Law of strong large numbers; Central limit theorem1. 引言近几十年来,随着马尔可夫理论的不断深入和完善,关于排队论的研究得到了很大程度上的丰富和发展,获得了一系列研究成果,代表性文献参见1-6. 然而,关于 GI/G/1 排队系统,

5、由于其到达时间和服务时间都服从一般的分布,队长过程不再是马尔可夫过程,也无法通过嵌入马尔可夫链的方法来进行研究,因此关于这方面的研究相对较少.侯振挺教授给出了GI/G/1 排队系统队长的瞬时分布,文献8给出了队长的极限分布,本文主要研究该队长的累积过程的期望和方差, 大数定律和中心极限定理. 2. GI/G/1排队系统本文讨论的 排队系统细节如下（参见文献9）： (i)顾客到达系统的时间间隔是独立同分布的随机变量,其分布函数是.令, 为 之后顾客陆续到达服务台的时刻, 到达时间间隔 ,于是 .(ii)每个顾客的服务时间为独立同分布的随机变量,其分布函数是,并且与独立. 令 为 时系统的所有顾客

6、总的剩余服务时间（即系统的剩余工作负荷）, 为 之后第 个到达系统的顾客的服务时间.于是.(iii) 有一个服务员, 且按先到先服务规则进行服务.基金项目：国家自然科学基金青年基金资助项目 (11001179)令 称为系统的服务强度. 假定 . 3. 队长的强大数定律和中心极限定理设表示GI/G/1排队系统在时刻 的队长（即时刻 在服务台前等待的顾客数与正在被服务的顾客数之和）. 令 根据繁忙循环的定义,表示从开始,第个繁忙循环开始的时刻. 令, 则 表示第个繁忙循环的长度.引理1.如果 , 则 (1)其中 .定理 1. 对于排队中的队长, 如果, 是正常返的 Doob 骨架过程. 证明: (

7、1) 已知表示第个繁忙循环开始的时刻,此时, 则之后的取值,仅依赖于时刻的值,与前面的繁忙周期中 队长的取值完全无关, 即在 处有马尔可夫性. 于是, 是一个马尔可夫骨架过程, 为其骨架时序列. (2) 对于, , 即服从聚点分布,根据定义3.1.2,是以为更新点的Doob 骨架过程.(3) 如果 , 根据引理3.1, 于是根据定义3.1.3, 是一个正常返的 Doob 骨架过程. 由于 是以 为更新点的 Doob 骨架过程,根据引理3.1.3知 为独立同分布的随机变量序列,设 为 的分布函数. 令分别表示的期望和二阶矩. 令 , 则表示在两个更新点之间的累积过程. 由为正常返的Doob骨架过

8、程和 为独立同分布的随机变量序列可得, 也为独立同分布的随机变量序列. 令分别为的期望和方差, ,其中表示之前更新点的数目. 引理2. 设为独立同分布的随机变量序列,其共同的分布函数为 , 期望 .令 为一随机变量满足 , 并且对于任意的 , 与 独立, 则 的分布函数为非格子分布当且仅当 是非格子分布. 定理 2. 对于中的队长 , 如果 , 是非格子的, (i) 如果, 则当时,有 (2)(ii) 如果, ,其中 分别是和的方差, 则当时, (3)证明: 当 是非格子分布时,根据引理3.2, 的分布函数也是非格子分布. 如果 ,由定理3.1可知 是正常返的Doob骨架过程.于是,根据定理

9、3.3.3 可得(2)式和(3)式成立,定理得证. 定理 3. (强大数定律) 对于中的队长, 如果, 是非格子的,则对任意的,下式几乎必然成立 (4)证明: 当是非格子分布时,根据引理3.2,的分布函数也是非格子分布. 如果 ,由定理3.1可知 是正常返的Doob骨架过程.于是,根据定理 3.3.2 可得(4)式成立,定理得证. 定理 4. (中心极限定理) 对于中的队长, 如果, 是非格子的, , , , , 则 (5)其中 是一标准正态分布, .证明: 当是非格子分布时,根据引理3.2,的分布函数也是非格子分布. 如果 ,由定理3.1可知是正常返的Doob骨架过程.于是,根据定理 3.3

10、.4可得(5)式成立,定理得证.参考文献1 Kendall, G. Some problems in the theory of queues J. J. Roy. Statist. Soc. (Series. B), 1951, 13,151-185. 2 Kendall, G. Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains J. Ann. Math. Statist, 1953, 24,338-354. 3 K

11、ingman, J.F.C. The single server queue in heavy traffic J. Proc. Cambridge Phil. Soc, 1961, 57,902-904. 4 Kingman, J.F.C. On queues in heavy traffic J. J. R. Statist. Soc, 1962, 24,383-392. 5 Assumen, S. Calculation of the steady state waiting time distribution in GI/PH/c and MAP/PH/c Queues J. Queueing Systems, 2001, 37, 9-29. 6 Asmussen, S. Applied Probability and Queue (second edition) M. New York: Springer, 2003. 7 Hou Zhenting. Markov skeleton processes and application to queueing systems J. Acta Mathematicae Applicatae Sinica, English Series, 2002, 18(40), 537-552. 8 董海玲.马尔可夫骨架过程的极限理论D.