随机模型中密度演化方程的适定性
摘要
对具有马氏性的随机过程,柯尔莫哥洛夫建立了状态转移概率的向前和向后方程,把研究过程的问题转化为研究微分方程解的问题。对不具有马氏性的随机模型,问题就变得困难很多。为解决这类问题,产生了许多不同的方法,如Palm和Kendall的嵌入马氏链方法;Lindley的积分方程方法。此外,通过引入补充变量,扩大记录过程信息的状态变量的维数,使非马氏过程具有马氏性也是一种有效的方法。称引入补充变量后得到的扩维随机过程为向量马氏过程。对许多实际问题,想建立其状态转移概率函数的向前或向后方程从而确定整个过程有不少困难。能否退而求其次,建立状态概率或密度函数满足的方程?比较早的尝试性工作可以参见文献[28],M/ G/1比较完整地建立模型队长过程的状态概率密度演化方程可参见文献[27]。史定华教授在其专著中,则用状态概率密度演化方法系统处理了向量马氏过程的随机模型问题,在证明了向量马氏过程的频度转移公式后,就能通过系统的状态概率密度函数得到过程的许多性能指标,从而利用密度演化方法重新处理了排队论和系统可靠性中的许多模型。这样,尽管有时不能完全确定向量马氏过程,但得到这些性能指标后,对解决实际问题显然仍裨益非浅。
在马氏过程中得到向前向后方程,或者在向量马氏过程中得到密度演化方程,都是想把随机模型的研究转化为方程的研究,也即把随机过程的研究转化为确定性的方程问题研究。对柯尔莫哥洛夫的向前或向后方程适定性和渐近性问题的研究已经非常系统完整。1940年,费勒首先通过构造最小非负解,证明了解的存在性问题[29];1945年杜勃研究了解的唯一性问题[24],而候振挺在1974年则给出了解的唯一性条件[12]。如果解不唯一,那么如何得到所有的解也有许多结论,见文献[8], [24], [42], [50], [54]等。
对向量马氏过程中得到的状态概率密度演化方程,自然也仍旧必须讨论解的存在唯一性问题。在建立了随机模型的密度演化方程后,有这样一些问题亟待解决:方程的解是否对任何可能的初始状态概率密度都存在?如果不是,那么对什么样的初始状态概率密度,方程的解存在?解是否唯一?如果解存在唯一,解是否渐近稳定?
本文的主要内容之一就是研究解决这些问题。我们主要采用两种方法:半群理论和更新方程方法。
从目前排队论和可靠性理论中的模型看,得到的密度演化方程通常是一些带有积分项的常微分或偏微分方程组,且带有比较复杂的边界条件,现有的方程理论很难在这里直接应用。目前研究这类问题主要运用半群理论方法,即把方程转化为一个抽象柯西问题处理。半群理论是处理动力系统方程的一种有效方法。把得到的由微分或偏微分方程描述的动力系统归结为巴拿赫空间上的抽象柯西问题,从而用一般的半群理论统一处理,这方面的工作已有丰富的结果,见文献[33],[48]等。在密度演化方程研究中,采用此方法应该是一件有意义的工作。近来,已有一些这方面的尝试性工作。如文献[36]中,在有界风险率假设下,利用半群理论证明了M/ G/1队长模型的密度演化方程解的存在唯一性和渐近性;在文献[4]中,证明了M/M/∞密度演化方程解的存在唯一性。但从总体上看,密度演化方程解的研究工作还在起步阶段。本文的将继续这方面的研究工作。
除继续利用算子半群方法研究外,我们发现一些密度演化方程解的适定性问题可以转化为边界函数的共轭更新方程解的存在唯一性问题来研究。通过证明共轭更新方程解的存在唯一性和渐近性,不但可以得到这些方程解的存在唯一性,也能得到解的渐近稳定性结果。
本文的另一工作是用密度演化方法对经典排队理论很难处理的分形排队模型进行了初步的探索性研究。
随着计算机网络技术的不断发展,自20世纪90年代开始,对网络数据传输的研究逐渐引起重视。网络数据传输的实证研究揭示了数据到达过程具有重尾,自相似和长程相依这样一些特征[43],建立在到达过程是马氏或独立基础上的方法就难以在此应用。而由一个分形映射驱动到达过程的分形排队模型是描述数据传输模型的有效方法之一,具有直观且较易数值模拟的特点。对分形排队模型,我们建立了映射状态和队长的联合密度演化方程,利用数值计算和数值仿真模拟的方法对方程的解作了初步的探索性研究。
下面是本文主要内容和结果。
第一章中,我们简要介绍了密度演化方法的基本思想。并阐述了密度演化方程和向前向后方程之间的联系和区别:转移概率的向前方程是状态概率方程的一个特殊情况,是特殊初始条件下的状态概率演化方程。同时给出了本文的总体结构安排和主要结果。
第二章主要是给出本文所涉及的有关分析方面的一些基本概念和结果。大致包括两方面的内容: C_0-半群和积分方程理论。在第一和第二节中,除了给出半群理论的一些基本概念和结论外,我们对连续状态空间上的半群算子建立了抽象柯西问题解适定的一个充分条件(定理2.2.7),该条件要求相应的过程具有某种正则性。第三节中,则证明了l~1空间上抽象柯西问题中的相应算子成为闭算子的一个充分条件(定理2.3.1),从而就能证明离散空间上密度演化方程解存在唯一的充分条件(推论2.3.3)。在第四节中,讨论了抽象柯西问题解何时具有概率意义的问题。该章的最后一节引入共轭更新方程的概念并讨论了共轭更新方程解的存在唯一性和渐近性问题。利用更新定理,对无限维共轭更新方程证明了解的渐近稳定性。
第三章将用密度演化方法的观点重新讨论离散状态马氏过程模型。在第一节中,进一步讨论了状态概率和转移概率函数之间的联系和差异:尽管状态概率不能完全确定转移概率,但如果状态概率演化方程相应的算子的定义域中包含的函数足够广,那么也能确定转移概率。第二节则从过程的概率特性出发,建立了一类离散状态马氏过程的密度演化方程,给出了该方程解存在唯一的充分条件(定理3.2.1)。第三节用密度演化方法重新得到了有关生灭过程中的一些重要结论(推论3.3.3,3.3.4)。文献[4]中得到的M /M/∞密度演化方程解的存在性和唯一性可以作为这里结论的特例。结果表明,密度演化方法处理随机模型有时会更简洁,易于理解。
在第四和第五章中,我们将讨论向量马氏过程的密度演化方程解的存在性问题。按照所采用的方法的不同,我们分两部分来讨论向量马氏过程的密度演化方法解的存在唯一性。
在第四章中,我们利用算子半群理论,分别讨论了可靠性和排队论中的二个典型模型——两部件可修串联系统和M/ G/1忙闲过程模型——的密度演化方程解的存在唯一性问题。第一节中,证明了忙闲过程的密度演化方程中得到的算子的一些性质(定理4.1.1,4.1.2和4.1.3),给出了相应柯西问题解存在唯一的结果(定理4.1.4)。第二节则研究了两部件可修串联系统密度演化方程的适定性问题,在不假设风险率函数有界时,证明了闭化算子对应的柯西问题解的适定性(定理4.2.10),而仅对适当的初始条件,原来的问题解存在唯一(推论4.2.11);而如果风险率函数有界,那么密度演化方程的解存在唯一(定理4.2.13)。
第五章运用更新定理证明了排队论中M/ G/1队长过程和可靠性问题中两部件并联可修系统的密度演化方程适定性和渐近稳定性问题。我们把这两个模型的密度演化方程解的适定性问题转化为特殊积分方程——共轭更新方程——的相应问题,利用第一章的无限维共轭更新方程解的结果,证明了密度演化解的存在唯一性和渐近性。第一节中,建立了M/ G/1队长过程的密度演化方程和一个可列更新方程之间的联系(定理5.1.1,5.1.2),然后证明了该可列更新方程解的存在唯一性和渐近稳定性(定理5.1.5),得到的结论和已有的经典结论是一致的(推论5.1.5),这里不再需要假设风险率函数是有界函数。第二节中研究并联可修系统密度演化方程解的适定性问题,同样得到了原来问题和更新方程解的存在唯一性之间的关系(定理5.2.1,推论5.2.2),随后在较弱的条件下证明了更新方程解的存在唯一性和渐近稳定性(引理5.2.4,定理5.2.5),由此可以得到原来密度演化方程解的适定性和渐近稳定性(定理5.2.6)。最后,与已有的结果进行了比较(注3)。
比较第四章和第五章两种方法,半群方法应该是更一般,但是由于对涉及的算子的谱计算较困难,目前尚无很好的方法来讨论解的渐近稳定性问题。积分方程的办法对特殊的模型较有效,不但能得到存在唯一性,而且解的渐近行为也有较完整的结论,但是究竟什么样的密度演化方程可以转化为积分方程处理还有待进一步研究。
在第三章,第四章和第五章中我们侧重于在已得到密度演化方程后,方程解的存在唯一性的研究。事实上,密度演化方法可以用来处理许多经典方法难以入手的随机模型问题。最后第六章我们讨论的离散分形排队模型就是一个例子。
网络数据传输的实证研究发现,节点上到达的数据流量具有分形,自相似和重尾特性。建立在到达过程具有马氏性或独立性假设上的模型都不能很好地刻画相应的数据传输过程。到达过程由分形映射驱动的排队模型是一个能从物理机制角度解释每个节点的数据产生过程并且适宜于计算机仿真模拟的模型。由于此时到达的时间间隔不再是独立的,而是具有长程相依性,这类问题经典排队论的方法很难处理。用密度演化方法我们仍可建立状态和队长的密度演化方程。对得到的密度演化方程,尽管还没有较好的方法从理论上进行研究,但是,可以用数值计算方法或利用到达过程比较容易计算机仿真模拟这个特点,利用统计方法进行研究。在第一节中,我们简要介绍了网络数据传输的物理背景。第二节中则介绍了从密度演化观点研究分形映射的一些基本思想。决定分形映射密度演化方程的不变密度一直是一个比较困难的问题,这里,我们给出了近似得到不变密度的两种方法:数值计算和统计方法。第三节研究了由混沌映射驱动的到达过程的闲期和忙期逗留时间分布,得到了它们的联合分布(定理6.3.1)。结果表明,尽管映射的状态是平稳的,联合分布是同分布的,但并不一定独立。因此,分形排队模型和on-off模型之间还是稍有不同的。对Bernoulli映射,进一步得到了联合密度的解析表达式表达式(推论6.3.2)。对一般的混沌映射,我们利用数值计算和仿真模拟的方法讨论了闲期逗留时间分布,结果显示:相应于非线性映射的逗留时间分布是渐近幂率的。这个结果和文献[40]中的结论是一致的。最后一节,我们建立了分形排队的密度演化方程。对Bernoulli映射,我们得到了状态和队长的平稳联合分布存在的条件和具体的表达式(定理6.4.1)。但是,对非线性的映射,理论上要给出或证明平稳分布还比较困难。我们同样利用仿真模拟的方法讨论了队长边际分布,结果显示,如果刻画到达的映射是线性的,那么该分布是几何的,如果是非线性的,那么是渐近幂率的。
总之,本文比较系统地研究了可靠性和排队论中已经得到的一些具有典型性的密度演化方程解的存在唯一性问题,对某些模型则进一步讨论了解的渐近性问题。同时,对涉及的过程比较一般,不具有再生点的离散时间分形排队模型,能否利用密度演化方程去解决也作了初步探讨。在处理密度演化方程适定性问题的方法上,不但采用了通常所用的算子半群方法,还注意到模型的特殊性,充分利用了共轭更新方程的结果。对理论上尚无较好方法处理的分形排队模型的密度演化方程,利用数值计算和统计方法进行了初步的研究。
本文是在史定华教授悉心指导和帮助下完成的。特别是第六章,主要思想来自史定华教授,此外,一些数值计算和计算机仿真的方法也是和黄月芳博士一起讨论产生的,在此一并表示感谢。
It is always an attractive methodology to study a non-markovian process in a similar way used by Kolmogorov to treat a Markovian process, that is to set up a group of equations which can determine the process in most cases. It is much more difficult to do so. Many methods have been used to study a non-markovian process, such as, the embedded Markov chain put forward by Palm and Kendall; the Lindley’s integral equations etc. Besides it is possible to transform a non-markovian process into a Markovian process called as a vector Markovian process by extending the state dimensions of the process after defining the supplementary variables to record the history of the process. Although it is always difficult to obtain the forward or backward equations for most stochastic models but it is possible in some cases to set up the equations of the state density functions. The early attempt to treat non-markovian models can be found in [28] and state density evolution equations of queueing length for M/ G/1 model refer to [27]. A systematic treatment by the methodology can be found in professors Shi’s monograph[1] in which the frequency transition formula is proved and then many performance index of the models in queueing and reliability problems can be calculated. It is significant to the practical application to determine these performance indexes though the process may not be fixed by the density evolutions.
For a Markovian process the problem to decide the process is transformed to prove the existence and uniqueness of the equations after obtaining the forward and backward equations. In 1940 Feller proved the existence of the solution by constructing a minimal nonnegative solution[29] and Doob studied the uniqueness problem[24] in 1945. Ho found the conditions of uniqueness of the solution[12] in 1974 and as for how to find all solutions if it is not unique refers to [8], [24], [42], [50], [54] etc.
For the density evolution equations of a VMP it is quite nature to find answers to questions such as whether the solutions exist uniquely for any given initial conditions; if not, what conditions are required to guarantee the existence of the solutions; if the solution exists uniquely it is stable or not. One of the main contents of this paper is to try to find answers to these questions. The semi-group and renewal equations theories are main tools to solve these problems.
In most cases integral differential equations with complex boundary conditions resulted from the stochastic models in queueing and reliability systems. There are hardly any known conclusions in differential equations to be applied directly here. Semi-group approaches are quite effective to deal with dynamical systems, in which the problems are descried uniformly as abstract Cauchy problems and abundant results achieved in this field[33],[48]。It seems to be significant to use the method to study the density evolution equations and in fact some attempts have been carried on, for example, in [36], under the assumption that the risk function is bounded, the existence, uniqueness and asymptocity of the solutions for the bM/ G/1 queueing system are proved; in [4] the similar conclusion is proved for M /M/∞system. We will continue the work in this field in this paper.
On the other hand we find that there exists tight connections in some cases between the density evolution equations and a special kind of integral equations called as conjugate renewal equations here. In that case the solutions are determined by boundary functions satisfying conjugate renewal equations. It implies that it is sufficient to study the features of solutions of conjugate equations instead of the original ones.
The density evolution methods are especially useful in the studying of stochastic models which are difficult to deal with in classical queueing theory. In the final chapter of this paper we will probe the possibility to study the fractal queueing models using the method.
One of the reasons to study fractal queueing models is as follows. Since the 90s of last century with the development of computer science and technology more and more studies to the date traffics demonstrate that heavy tail, self-similarity and long range dependence are common features in the date transmission[43]. The usual methodology based on the assumption of markovian or independence to the arrival process is not suitable to treat the problems. A discrete queueing model with arrivals driven by a fractal mapping is supposed to be an effective one for its simplicity to simulate. We set up the evolution equations for joint density function of the mapping state and queueing length. The algorithm and simulation methods are used to study the features of the solutions.
The main results and contents are described as follows.
In chapter 1 the main ideas of the density evolution are introduced. It is shown that the forward equation is its special case. The outline and arrangements of the whole paper are also given there.
Some analytical results and concepts concerned are given in the second chapter, including C_0 semi-groups, integral equations and especially renewal equations. In section 1 and 2, a sufficient condition of the existence and uniqueness for a ACP (abstract Cauchy problem) is proved (theorem 2.2.7) which is relevant to the assumption of regularity to the process. In section 3 a sufficient condition (theorem 2.3.1) for an operator in l~1 to be closed is proved and by which the existence and uniquness of solutions for evolution equations in discrete space can be proved (corollary 2.3.3). In section 4 we discuss the problem for a solution to be a probability density. In the final section of this chapter we discuss the properties of solutions for conjugate renewal equations. Using the renewal theorem we prove the stability of the solution for the equation.
In chapter 3 we study the discrete state Markovian chain model by the approach of density evolution method. In section 1 we point out the connection and difference between the transition probability and the state probability. Although the later cannot always decide the process but if the domain of the operator of the evolution equation includes enough functions it is possible to decide the transition probability. In section 2 we set up state density evolution equations for a class of Markov chain defined in the view of probability and prove a sufficient condition for the existence of the solution (theorem 3.2.1). In the last section we prove again by the method of density evolution equations some well-known important conclusions for birth-death process (corollary 3.3.3, 3.3.4) and the result about M / M/∞model in [4] is derived as a special case.
In chapter 4 and 5 we discuss the problems for MAP. According the method used the contents are divided into two parts.
In chapter 4 using semi-group method we study two models in reliability and queueing theory. In section 1, after proving some properties of the operator for busy and idle process of M/ G/1 model (theorem 4.1.1, 4.1.2 and 4.1.3) we obtain the main results of the section (theorem 4.1.4). In section 2 without the assumption of bound to the risk function we prove the existence and uniqueness of the solution to ACP with closed operator (theorem 4.2.10) while for the original problem the conclusion holds for some special initial condition (corollary 4.2.10). If the risk function is bound the conclusion holds for any given initial conditions (theorem 4.2.13).
In chapter 5 we study the problems for M/ G/1 queueing length and parallel repairable system using conjugate renewal equations. In these two models the solutions of the density evolution equations can be determined by the boundary functions satisfying conjugate renewal equations. By the results in chapter 1, the existence, uniqueness and asymptocity of the solutions for these two models are proved. In section 1 we display the connections between the evolution equations and renewal equations (theorem 5.1.1 and 5.1.2) by which the main result of this section is proved (corollary 5.1.5). The result is consistent with the well-known conclusion. In section 2 the similarity process as in section 1 is carried on to dealt with the parallel repairable systems theorem and the similar conclusions see theorem 5.2.1, corollary 5.2.2, lemma 5.2.4 and theorem 5.2.5. The main result is offered in theorem 5.2.6 which is compared with the well-known conclusions (notes 3).
In chapter 3, chapter4 and chapter 5 we focus on the problems to prove the existences and the uniqueness of the density evolutions obtained in stochastic models. On the hand the evolution density method can be used to deal with problems difficult to treat by classical methods. As an example the discrete fractal queueing model is discussed in the final chapter.
In the 90s last century, the observation to date traffics in network manifests that the fractals, heavy tailed and long range dependence are common in network. The queueing models based on the assumption that the arrival process is dependent or markovian are not quite suitable to describe the date traffics in network. A discrete queueing model in which the arrival process is driven by a fractal mapping is a possible model to explain the phenomena from physical mechanism and is easy to simulate. Because of the long-range dependence of arrival process it is difficult to treat in classical queueing theory, but even so, we still can set up the density evolution equation for the model. To the equation it is still not found the theoretical method to study but the algorithm and simulation are possible. In section 1 the physical background to the problem is described. In section 2 we study the invariant density of fractal mapping using statistics and algorithm methods. In section 3 we obtain the joint distribution of idle and busy periods for the arrival process driven by chaotic mappings (theorem 6.3.1) and the analytic expression is shown for Bernoulli case (corollary 6.3.2). In the last section of this chapter we set up the density evolution equations and study the stable density using simulation method. The results show that if the mapping is linear the distribution is geometry and otherwise decays in power.
Overall we have studied the existence and uniqueness of density evolution equations in queueing and reliability models and if possible, the stable problems in some cases. And for models which is not suitable to treat in classical queueing theory we have probed the possibility to study in density evolution methods. Both semi-group and conjugate renewal equation methods are used. For a models which is difficult to study in theory we probe the possibilities of algorithm and simulation methods.
This paper is finished under the supervision of professor Shi. Especially the main idea of chapter 6 comes from Prof. Shi. And the algorithm and simulation in chapter 6 are discussed with Doc. Huang. Thanks to them here.
在马氏过程中得到向前向后方程,或者在向量马氏过程中得到密度演化方程,都是想把随机模型的研究转化为方程的研究,也即把随机过程的研究转化为确定性的方程问题研究。对柯尔莫哥洛夫的向前或向后方程适定性和渐近性问题的研究已经非常系统完整。1940年,费勒首先通过构造最小非负解,证明了解的存在性问题[29];1945年杜勃研究了解的唯一性问题[24],而候振挺在1974年则给出了解的唯一性条件[12]。如果解不唯一,那么如何得到所有的解也有许多结论,见文献[8], [24], [42], [50], [54]等。
对向量马氏过程中得到的状态概率密度演化方程,自然也仍旧必须讨论解的存在唯一性问题。在建立了随机模型的密度演化方程后,有这样一些问题亟待解决:方程的解是否对任何可能的初始状态概率密度都存在?如果不是,那么对什么样的初始状态概率密度,方程的解存在?解是否唯一?如果解存在唯一,解是否渐近稳定?
本文的主要内容之一就是研究解决这些问题。我们主要采用两种方法:半群理论和更新方程方法。
从目前排队论和可靠性理论中的模型看,得到的密度演化方程通常是一些带有积分项的常微分或偏微分方程组,且带有比较复杂的边界条件,现有的方程理论很难在这里直接应用。目前研究这类问题主要运用半群理论方法,即把方程转化为一个抽象柯西问题处理。半群理论是处理动力系统方程的一种有效方法。把得到的由微分或偏微分方程描述的动力系统归结为巴拿赫空间上的抽象柯西问题,从而用一般的半群理论统一处理,这方面的工作已有丰富的结果,见文献[33],[48]等。在密度演化方程研究中,采用此方法应该是一件有意义的工作。近来,已有一些这方面的尝试性工作。如文献[36]中,在有界风险率假设下,利用半群理论证明了M/ G/1队长模型的密度演化方程解的存在唯一性和渐近性;在文献[4]中,证明了M/M/∞密度演化方程解的存在唯一性。但从总体上看,密度演化方程解的研究工作还在起步阶段。本文的将继续这方面的研究工作。
除继续利用算子半群方法研究外,我们发现一些密度演化方程解的适定性问题可以转化为边界函数的共轭更新方程解的存在唯一性问题来研究。通过证明共轭更新方程解的存在唯一性和渐近性,不但可以得到这些方程解的存在唯一性,也能得到解的渐近稳定性结果。
本文的另一工作是用密度演化方法对经典排队理论很难处理的分形排队模型进行了初步的探索性研究。
随着计算机网络技术的不断发展,自20世纪90年代开始,对网络数据传输的研究逐渐引起重视。网络数据传输的实证研究揭示了数据到达过程具有重尾,自相似和长程相依这样一些特征[43],建立在到达过程是马氏或独立基础上的方法就难以在此应用。而由一个分形映射驱动到达过程的分形排队模型是描述数据传输模型的有效方法之一,具有直观且较易数值模拟的特点。对分形排队模型,我们建立了映射状态和队长的联合密度演化方程,利用数值计算和数值仿真模拟的方法对方程的解作了初步的探索性研究。
下面是本文主要内容和结果。
第一章中,我们简要介绍了密度演化方法的基本思想。并阐述了密度演化方程和向前向后方程之间的联系和区别:转移概率的向前方程是状态概率方程的一个特殊情况,是特殊初始条件下的状态概率演化方程。同时给出了本文的总体结构安排和主要结果。
第二章主要是给出本文所涉及的有关分析方面的一些基本概念和结果。大致包括两方面的内容: C_0-半群和积分方程理论。在第一和第二节中,除了给出半群理论的一些基本概念和结论外,我们对连续状态空间上的半群算子建立了抽象柯西问题解适定的一个充分条件(定理2.2.7),该条件要求相应的过程具有某种正则性。第三节中,则证明了l~1空间上抽象柯西问题中的相应算子成为闭算子的一个充分条件(定理2.3.1),从而就能证明离散空间上密度演化方程解存在唯一的充分条件(推论2.3.3)。在第四节中,讨论了抽象柯西问题解何时具有概率意义的问题。该章的最后一节引入共轭更新方程的概念并讨论了共轭更新方程解的存在唯一性和渐近性问题。利用更新定理,对无限维共轭更新方程证明了解的渐近稳定性。
第三章将用密度演化方法的观点重新讨论离散状态马氏过程模型。在第一节中,进一步讨论了状态概率和转移概率函数之间的联系和差异:尽管状态概率不能完全确定转移概率,但如果状态概率演化方程相应的算子的定义域中包含的函数足够广,那么也能确定转移概率。第二节则从过程的概率特性出发,建立了一类离散状态马氏过程的密度演化方程,给出了该方程解存在唯一的充分条件(定理3.2.1)。第三节用密度演化方法重新得到了有关生灭过程中的一些重要结论(推论3.3.3,3.3.4)。文献[4]中得到的M /M/∞密度演化方程解的存在性和唯一性可以作为这里结论的特例。结果表明,密度演化方法处理随机模型有时会更简洁,易于理解。
在第四和第五章中,我们将讨论向量马氏过程的密度演化方程解的存在性问题。按照所采用的方法的不同,我们分两部分来讨论向量马氏过程的密度演化方法解的存在唯一性。
在第四章中,我们利用算子半群理论,分别讨论了可靠性和排队论中的二个典型模型——两部件可修串联系统和M/ G/1忙闲过程模型——的密度演化方程解的存在唯一性问题。第一节中,证明了忙闲过程的密度演化方程中得到的算子的一些性质(定理4.1.1,4.1.2和4.1.3),给出了相应柯西问题解存在唯一的结果(定理4.1.4)。第二节则研究了两部件可修串联系统密度演化方程的适定性问题,在不假设风险率函数有界时,证明了闭化算子对应的柯西问题解的适定性(定理4.2.10),而仅对适当的初始条件,原来的问题解存在唯一(推论4.2.11);而如果风险率函数有界,那么密度演化方程的解存在唯一(定理4.2.13)。
第五章运用更新定理证明了排队论中M/ G/1队长过程和可靠性问题中两部件并联可修系统的密度演化方程适定性和渐近稳定性问题。我们把这两个模型的密度演化方程解的适定性问题转化为特殊积分方程——共轭更新方程——的相应问题,利用第一章的无限维共轭更新方程解的结果,证明了密度演化解的存在唯一性和渐近性。第一节中,建立了M/ G/1队长过程的密度演化方程和一个可列更新方程之间的联系(定理5.1.1,5.1.2),然后证明了该可列更新方程解的存在唯一性和渐近稳定性(定理5.1.5),得到的结论和已有的经典结论是一致的(推论5.1.5),这里不再需要假设风险率函数是有界函数。第二节中研究并联可修系统密度演化方程解的适定性问题,同样得到了原来问题和更新方程解的存在唯一性之间的关系(定理5.2.1,推论5.2.2),随后在较弱的条件下证明了更新方程解的存在唯一性和渐近稳定性(引理5.2.4,定理5.2.5),由此可以得到原来密度演化方程解的适定性和渐近稳定性(定理5.2.6)。最后,与已有的结果进行了比较(注3)。
比较第四章和第五章两种方法,半群方法应该是更一般,但是由于对涉及的算子的谱计算较困难,目前尚无很好的方法来讨论解的渐近稳定性问题。积分方程的办法对特殊的模型较有效,不但能得到存在唯一性,而且解的渐近行为也有较完整的结论,但是究竟什么样的密度演化方程可以转化为积分方程处理还有待进一步研究。
在第三章,第四章和第五章中我们侧重于在已得到密度演化方程后,方程解的存在唯一性的研究。事实上,密度演化方法可以用来处理许多经典方法难以入手的随机模型问题。最后第六章我们讨论的离散分形排队模型就是一个例子。
网络数据传输的实证研究发现,节点上到达的数据流量具有分形,自相似和重尾特性。建立在到达过程具有马氏性或独立性假设上的模型都不能很好地刻画相应的数据传输过程。到达过程由分形映射驱动的排队模型是一个能从物理机制角度解释每个节点的数据产生过程并且适宜于计算机仿真模拟的模型。由于此时到达的时间间隔不再是独立的,而是具有长程相依性,这类问题经典排队论的方法很难处理。用密度演化方法我们仍可建立状态和队长的密度演化方程。对得到的密度演化方程,尽管还没有较好的方法从理论上进行研究,但是,可以用数值计算方法或利用到达过程比较容易计算机仿真模拟这个特点,利用统计方法进行研究。在第一节中,我们简要介绍了网络数据传输的物理背景。第二节中则介绍了从密度演化观点研究分形映射的一些基本思想。决定分形映射密度演化方程的不变密度一直是一个比较困难的问题,这里,我们给出了近似得到不变密度的两种方法:数值计算和统计方法。第三节研究了由混沌映射驱动的到达过程的闲期和忙期逗留时间分布,得到了它们的联合分布(定理6.3.1)。结果表明,尽管映射的状态是平稳的,联合分布是同分布的,但并不一定独立。因此,分形排队模型和on-off模型之间还是稍有不同的。对Bernoulli映射,进一步得到了联合密度的解析表达式表达式(推论6.3.2)。对一般的混沌映射,我们利用数值计算和仿真模拟的方法讨论了闲期逗留时间分布,结果显示:相应于非线性映射的逗留时间分布是渐近幂率的。这个结果和文献[40]中的结论是一致的。最后一节,我们建立了分形排队的密度演化方程。对Bernoulli映射,我们得到了状态和队长的平稳联合分布存在的条件和具体的表达式(定理6.4.1)。但是,对非线性的映射,理论上要给出或证明平稳分布还比较困难。我们同样利用仿真模拟的方法讨论了队长边际分布,结果显示,如果刻画到达的映射是线性的,那么该分布是几何的,如果是非线性的,那么是渐近幂率的。
总之,本文比较系统地研究了可靠性和排队论中已经得到的一些具有典型性的密度演化方程解的存在唯一性问题,对某些模型则进一步讨论了解的渐近性问题。同时,对涉及的过程比较一般,不具有再生点的离散时间分形排队模型,能否利用密度演化方程去解决也作了初步探讨。在处理密度演化方程适定性问题的方法上,不但采用了通常所用的算子半群方法,还注意到模型的特殊性,充分利用了共轭更新方程的结果。对理论上尚无较好方法处理的分形排队模型的密度演化方程,利用数值计算和统计方法进行了初步的研究。
本文是在史定华教授悉心指导和帮助下完成的。特别是第六章,主要思想来自史定华教授,此外,一些数值计算和计算机仿真的方法也是和黄月芳博士一起讨论产生的,在此一并表示感谢。
It is always an attractive methodology to study a non-markovian process in a similar way used by Kolmogorov to treat a Markovian process, that is to set up a group of equations which can determine the process in most cases. It is much more difficult to do so. Many methods have been used to study a non-markovian process, such as, the embedded Markov chain put forward by Palm and Kendall; the Lindley’s integral equations etc. Besides it is possible to transform a non-markovian process into a Markovian process called as a vector Markovian process by extending the state dimensions of the process after defining the supplementary variables to record the history of the process. Although it is always difficult to obtain the forward or backward equations for most stochastic models but it is possible in some cases to set up the equations of the state density functions. The early attempt to treat non-markovian models can be found in [28] and state density evolution equations of queueing length for M/ G/1 model refer to [27]. A systematic treatment by the methodology can be found in professors Shi’s monograph[1] in which the frequency transition formula is proved and then many performance index of the models in queueing and reliability problems can be calculated. It is significant to the practical application to determine these performance indexes though the process may not be fixed by the density evolutions.
For a Markovian process the problem to decide the process is transformed to prove the existence and uniqueness of the equations after obtaining the forward and backward equations. In 1940 Feller proved the existence of the solution by constructing a minimal nonnegative solution[29] and Doob studied the uniqueness problem[24] in 1945. Ho found the conditions of uniqueness of the solution[12] in 1974 and as for how to find all solutions if it is not unique refers to [8], [24], [42], [50], [54] etc.
For the density evolution equations of a VMP it is quite nature to find answers to questions such as whether the solutions exist uniquely for any given initial conditions; if not, what conditions are required to guarantee the existence of the solutions; if the solution exists uniquely it is stable or not. One of the main contents of this paper is to try to find answers to these questions. The semi-group and renewal equations theories are main tools to solve these problems.
In most cases integral differential equations with complex boundary conditions resulted from the stochastic models in queueing and reliability systems. There are hardly any known conclusions in differential equations to be applied directly here. Semi-group approaches are quite effective to deal with dynamical systems, in which the problems are descried uniformly as abstract Cauchy problems and abundant results achieved in this field[33],[48]。It seems to be significant to use the method to study the density evolution equations and in fact some attempts have been carried on, for example, in [36], under the assumption that the risk function is bounded, the existence, uniqueness and asymptocity of the solutions for the bM/ G/1 queueing system are proved; in [4] the similar conclusion is proved for M /M/∞system. We will continue the work in this field in this paper.
On the other hand we find that there exists tight connections in some cases between the density evolution equations and a special kind of integral equations called as conjugate renewal equations here. In that case the solutions are determined by boundary functions satisfying conjugate renewal equations. It implies that it is sufficient to study the features of solutions of conjugate equations instead of the original ones.
The density evolution methods are especially useful in the studying of stochastic models which are difficult to deal with in classical queueing theory. In the final chapter of this paper we will probe the possibility to study the fractal queueing models using the method.
One of the reasons to study fractal queueing models is as follows. Since the 90s of last century with the development of computer science and technology more and more studies to the date traffics demonstrate that heavy tail, self-similarity and long range dependence are common features in the date transmission[43]. The usual methodology based on the assumption of markovian or independence to the arrival process is not suitable to treat the problems. A discrete queueing model with arrivals driven by a fractal mapping is supposed to be an effective one for its simplicity to simulate. We set up the evolution equations for joint density function of the mapping state and queueing length. The algorithm and simulation methods are used to study the features of the solutions.
The main results and contents are described as follows.
In chapter 1 the main ideas of the density evolution are introduced. It is shown that the forward equation is its special case. The outline and arrangements of the whole paper are also given there.
Some analytical results and concepts concerned are given in the second chapter, including C_0 semi-groups, integral equations and especially renewal equations. In section 1 and 2, a sufficient condition of the existence and uniqueness for a ACP (abstract Cauchy problem) is proved (theorem 2.2.7) which is relevant to the assumption of regularity to the process. In section 3 a sufficient condition (theorem 2.3.1) for an operator in l~1 to be closed is proved and by which the existence and uniquness of solutions for evolution equations in discrete space can be proved (corollary 2.3.3). In section 4 we discuss the problem for a solution to be a probability density. In the final section of this chapter we discuss the properties of solutions for conjugate renewal equations. Using the renewal theorem we prove the stability of the solution for the equation.
In chapter 3 we study the discrete state Markovian chain model by the approach of density evolution method. In section 1 we point out the connection and difference between the transition probability and the state probability. Although the later cannot always decide the process but if the domain of the operator of the evolution equation includes enough functions it is possible to decide the transition probability. In section 2 we set up state density evolution equations for a class of Markov chain defined in the view of probability and prove a sufficient condition for the existence of the solution (theorem 3.2.1). In the last section we prove again by the method of density evolution equations some well-known important conclusions for birth-death process (corollary 3.3.3, 3.3.4) and the result about M / M/∞model in [4] is derived as a special case.
In chapter 4 and 5 we discuss the problems for MAP. According the method used the contents are divided into two parts.
In chapter 4 using semi-group method we study two models in reliability and queueing theory. In section 1, after proving some properties of the operator for busy and idle process of M/ G/1 model (theorem 4.1.1, 4.1.2 and 4.1.3) we obtain the main results of the section (theorem 4.1.4). In section 2 without the assumption of bound to the risk function we prove the existence and uniqueness of the solution to ACP with closed operator (theorem 4.2.10) while for the original problem the conclusion holds for some special initial condition (corollary 4.2.10). If the risk function is bound the conclusion holds for any given initial conditions (theorem 4.2.13).
In chapter 5 we study the problems for M/ G/1 queueing length and parallel repairable system using conjugate renewal equations. In these two models the solutions of the density evolution equations can be determined by the boundary functions satisfying conjugate renewal equations. By the results in chapter 1, the existence, uniqueness and asymptocity of the solutions for these two models are proved. In section 1 we display the connections between the evolution equations and renewal equations (theorem 5.1.1 and 5.1.2) by which the main result of this section is proved (corollary 5.1.5). The result is consistent with the well-known conclusion. In section 2 the similarity process as in section 1 is carried on to dealt with the parallel repairable systems theorem and the similar conclusions see theorem 5.2.1, corollary 5.2.2, lemma 5.2.4 and theorem 5.2.5. The main result is offered in theorem 5.2.6 which is compared with the well-known conclusions (notes 3).
In chapter 3, chapter4 and chapter 5 we focus on the problems to prove the existences and the uniqueness of the density evolutions obtained in stochastic models. On the hand the evolution density method can be used to deal with problems difficult to treat by classical methods. As an example the discrete fractal queueing model is discussed in the final chapter.
In the 90s last century, the observation to date traffics in network manifests that the fractals, heavy tailed and long range dependence are common in network. The queueing models based on the assumption that the arrival process is dependent or markovian are not quite suitable to describe the date traffics in network. A discrete queueing model in which the arrival process is driven by a fractal mapping is a possible model to explain the phenomena from physical mechanism and is easy to simulate. Because of the long-range dependence of arrival process it is difficult to treat in classical queueing theory, but even so, we still can set up the density evolution equation for the model. To the equation it is still not found the theoretical method to study but the algorithm and simulation are possible. In section 1 the physical background to the problem is described. In section 2 we study the invariant density of fractal mapping using statistics and algorithm methods. In section 3 we obtain the joint distribution of idle and busy periods for the arrival process driven by chaotic mappings (theorem 6.3.1) and the analytic expression is shown for Bernoulli case (corollary 6.3.2). In the last section of this chapter we set up the density evolution equations and study the stable density using simulation method. The results show that if the mapping is linear the distribution is geometry and otherwise decays in power.
Overall we have studied the existence and uniqueness of density evolution equations in queueing and reliability models and if possible, the stable problems in some cases. And for models which is not suitable to treat in classical queueing theory we have probed the possibility to study in density evolution methods. Both semi-group and conjugate renewal equation methods are used. For a models which is difficult to study in theory we probe the possibilities of algorithm and simulation methods.
This paper is finished under the supervision of professor Shi. Especially the main idea of chapter 6 comes from Prof. Shi. And the algorithm and simulation in chapter 6 are discussed with Doc. Huang. Thanks to them here.
引文
[1]史定华,随机模型的密度演化方法,科学出版社,1999
[2]史定华,计算可修系统在中平均故障次数的新方法,应用数学学报,1 (1985), 101-110 ( 0,t]
[3]史定华,连续时间马氏链中的两个记数过程,应用概率统计,1 (1994),84-89
[4] Shi, D.H., Xiong,Y., Xu, H., C0-Semigroup Method of the Density Evolution Equation for , Journal of Shanghai University (Englishi Edition), Vol. 5, No.4 (Dec.2001), pp265-268 M/M/∞
[5]史定华,两部件串联系统的可靠性分析,福建师大学报(自然科学版),2(1982)
[6] Yan Qingqiang, Shi Dinghua and Guo Xingguo, A new vector Markov process for M/G/1, J. Shanghai University, 2(2005), 120-123
[7]田乃硕,拟生灭过程与矩阵几何解,科学出版社,2002
[8]杨向群,可列马尔可夫过程构造,湖南科学技术出版社,1981
[9]]徐光辉,随机服务系统,科学出版社,1980
[10]基赫曼,随机过程论,科学出版社,1986
[11]斯米尔诺夫,高等数学教程,第四卷,第一分册,人民教育出版社,1979
[12]候振挺,Q过程的唯一性准则,中国科学,2(1974),115-130
[13]候振挺,马氏骨架过程(?出版社)
[14]随机过程引论,华东师范大学出版社,1989
[15]伊藤清,随机过程,上海科学技术出版社,1961(附录)
[16]郑维行,王声望,实变函数与泛函分析概要,高等教育出版社,1986
[17]王梓坤,生灭过程与马尔可夫链,科学出版社,1980
[18]张恭庆、林源渠,泛函分析讲义,北京大学出版社,2000
[19]崔明奇等编译,排队论,上海科学技术出版社,1961,124-154
[20]费勒,概率论及其应用(中译本,第二卷),科学出版社,1994
[21] Benoite, D.S., Renewal theorem for a system of renewal equations, E-mail: Benoite de-Saporta@univ-rennesl.fr, March 2, 2004
[22] G., Birkhoff, Lattice Theory, 3rd.ed. Amer.Math.Soc., vol.25, Providence, 1967
[23] Boxma, O.J., Kurkova, I.A., The M/G/1 Queue With Two Service Speeds, Adv.Appl.Prob.33, p.520-540 (2001)
[24] Chung, K.L., Markov chains with stationary transition probabilities, Springer-Verlag, 1960
[25] Chung, K.L., On the boundary theory for Markov chains, Acta.Math. 110 (1963), 19-77. ibid. 115 (1966), 111-163
[26] Cinlar, E., An introduction to Probability and Stochastic Process, Prentice-Hall, Inc., Englewood Cliffs, New Jersey
[27] Cohen, J.W., The single server queue (second Edition), North-Holland, Amsterdam, 1982 [Cox]
[28] Cox, D.R., The analysis of non-Markovian stochastic process by the inclusion of supplementary variables, Proc.Camb.Phil.Soc.,51,1955,433-441
[29] Doob, J.L., Markov chains-denumerable case, Tran.Amer.Math, (58) (1945), 455-473
[30] Dippon, J., H., Walk, Simplified analytical proof of Blackwell’s renewal theorem, Oct. 2004, http://www.mathematik/uni-stuttgart.de/preprints
[31] Erramilli, A., Singh, R.P. and Pruthi, P., Chaotic maps as models of packet traffic,Proc.14th Int.Teletraffic Conf.,1994,North Holland,329-38
[32] Engibaryan, N.,B., Conservative systems of integral convolution equations on the half-line and the entire line, Sbornik, Mathematics 193: 6, 847-867, 2002 RAS (DoM) and LMS
[33] Fattorini, H.O., The Cauchy problem, Addision-Wesley Publishing Company, Inc., 1983
[34] Feller, W., On the Integro-differential Equations of Purely Discontinuous Markoff Process, Trans. Amer. Math. Soc., 48, 1940
[35] Feller, W., On Boundaries and lateral Conditions for the Kolmogoroff Differential Equations, Ann. Math., 65, 1957
[36] Gupur, G., Li, X.Z. and Zhu, G.T., Functional analysis method in queueing theory, Research Information Ltd., 2001
[37] Hunter, J., Mathematical Techniques of Applied Probability, Vol.2, Academic Press, 1983, New York
[38] Hille E., and Phillips, R.S., Functional Analysis and Semi-groups, Amer. Math. Soc., 1957
[39] Hsieh, M., Hurvich, C.M., Soulier, P., asymptotics for duration-driven long range dependent process, sep., 2003, http://econwpa.wustl.edu:80/eps/em/papers/0412/0412009.pdf
[40] Ji, Y.,S., Fujino,T., Abe, S., Matsukata, J. and Asano, S., On the impact of time scales on tail behavior of long-range dependent internet traffic, http://
[41] Kasahara, S., Internet traffic modelling:Markovian approach to self-similar traffic and predictions of loss probability for finite queues, IEICE TRANS.COMMUN., VOL.E84-B, NO.8, AUGUST 2001
[42] Kallenberg, O., Foundations Of Modern Probability, Springer, 2001
[43] Kosten, L., Stochastic Theory of Service Systems, Pergamon Press Ltd., 1973
[44] Lorenz, E.N., The essence of chaos, The University of Washington Press, 1993
[45] Lasota, A., Mackey, M.C., Chaos, Fractals, and Noise, 2nd. Ed., Springer-Verlag, 1994
[46] Neuts
[47] Paxson V., and Floyd, S., Wide-area traffic: the failure of Poisson modeling, IEEE/ACM Trans. on Networking, 3, No.3, 1995, 226-244
[48] Pazy, A., semigroups of linear operators and applications to partial differential equations, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1983
[49] Pruthi, P., Erramilli, A., Heavy-tailed on/off source behavior and self-similar traffic, Proceedings of the ICC’95, June18-22, 1995
[50] Reuter, G.E.H., Denumerable Markov process and the Associate Semigroup on l, Acta. Math., 97(1957), 1-46
[51] Riedi, R., Crouse, M., Ribeiro, Baraiuk, V., R., A multifractal wavelet model with application to network traffic, IEEE Trans. Commun., Vol.43, No.,2/3/4, pp1566-1579, 1995
[52] Ross, S.M., Stochastic process, John Wiley & Sons, Inc., 1983
[53] Schmidli, H., An extension to the renewal theorem and an application to risk theory, The Annals of Applied Probability, 1997, Vol., No.1, 121-133
[54] D., Williams, On the Construction Problem for Markov chains, Zs. f. Wahrsch., 3, 1964
[55] Willinger, W., Leland, W.E., Taqqu, M.S., and Wilson, D.V., On the self-similar nature of Ethernet traffic, Proc ACM SIGCOMM 93, 1993
[56] Willinger, W., Paxson, V., Riedi R.L. and Taqqu, M.S., Long-Range dependent and network traffic
[57] K., Yosida, Functional Analysis, Springer, Berlin, 1965
[58] A highly efficient M/G/ model for generating self-similar traces, Proceedings of the 2002 Winter simulation Conference, Yucesan, E., Chen, C.H., Snowdon, J.L., and Charnes, J.M., eds.∞
[2]史定华,计算可修系统在中平均故障次数的新方法,应用数学学报,1 (1985), 101-110 ( 0,t]
[3]史定华,连续时间马氏链中的两个记数过程,应用概率统计,1 (1994),84-89
[4] Shi, D.H., Xiong,Y., Xu, H., C0-Semigroup Method of the Density Evolution Equation for , Journal of Shanghai University (Englishi Edition), Vol. 5, No.4 (Dec.2001), pp265-268 M/M/∞
[5]史定华,两部件串联系统的可靠性分析,福建师大学报(自然科学版),2(1982)
[6] Yan Qingqiang, Shi Dinghua and Guo Xingguo, A new vector Markov process for M/G/1, J. Shanghai University, 2(2005), 120-123
[7]田乃硕,拟生灭过程与矩阵几何解,科学出版社,2002
[8]杨向群,可列马尔可夫过程构造,湖南科学技术出版社,1981
[9]]徐光辉,随机服务系统,科学出版社,1980
[10]基赫曼,随机过程论,科学出版社,1986
[11]斯米尔诺夫,高等数学教程,第四卷,第一分册,人民教育出版社,1979
[12]候振挺,Q过程的唯一性准则,中国科学,2(1974),115-130
[13]候振挺,马氏骨架过程(?出版社)
[14]随机过程引论,华东师范大学出版社,1989
[15]伊藤清,随机过程,上海科学技术出版社,1961(附录)
[16]郑维行,王声望,实变函数与泛函分析概要,高等教育出版社,1986
[17]王梓坤,生灭过程与马尔可夫链,科学出版社,1980
[18]张恭庆、林源渠,泛函分析讲义,北京大学出版社,2000
[19]崔明奇等编译,排队论,上海科学技术出版社,1961,124-154
[20]费勒,概率论及其应用(中译本,第二卷),科学出版社,1994
[21] Benoite, D.S., Renewal theorem for a system of renewal equations, E-mail: Benoite de-Saporta@univ-rennesl.fr, March 2, 2004
[22] G., Birkhoff, Lattice Theory, 3rd.ed. Amer.Math.Soc., vol.25, Providence, 1967
[23] Boxma, O.J., Kurkova, I.A., The M/G/1 Queue With Two Service Speeds, Adv.Appl.Prob.33, p.520-540 (2001)
[24] Chung, K.L., Markov chains with stationary transition probabilities, Springer-Verlag, 1960
[25] Chung, K.L., On the boundary theory for Markov chains, Acta.Math. 110 (1963), 19-77. ibid. 115 (1966), 111-163
[26] Cinlar, E., An introduction to Probability and Stochastic Process, Prentice-Hall, Inc., Englewood Cliffs, New Jersey
[27] Cohen, J.W., The single server queue (second Edition), North-Holland, Amsterdam, 1982 [Cox]
[28] Cox, D.R., The analysis of non-Markovian stochastic process by the inclusion of supplementary variables, Proc.Camb.Phil.Soc.,51,1955,433-441
[29] Doob, J.L., Markov chains-denumerable case, Tran.Amer.Math, (58) (1945), 455-473
[30] Dippon, J., H., Walk, Simplified analytical proof of Blackwell’s renewal theorem, Oct. 2004, http://www.mathematik/uni-stuttgart.de/preprints
[31] Erramilli, A., Singh, R.P. and Pruthi, P., Chaotic maps as models of packet traffic,Proc.14th Int.Teletraffic Conf.,1994,North Holland,329-38
[32] Engibaryan, N.,B., Conservative systems of integral convolution equations on the half-line and the entire line, Sbornik, Mathematics 193: 6, 847-867, 2002 RAS (DoM) and LMS
[33] Fattorini, H.O., The Cauchy problem, Addision-Wesley Publishing Company, Inc., 1983
[34] Feller, W., On the Integro-differential Equations of Purely Discontinuous Markoff Process, Trans. Amer. Math. Soc., 48, 1940
[35] Feller, W., On Boundaries and lateral Conditions for the Kolmogoroff Differential Equations, Ann. Math., 65, 1957
[36] Gupur, G., Li, X.Z. and Zhu, G.T., Functional analysis method in queueing theory, Research Information Ltd., 2001
[37] Hunter, J., Mathematical Techniques of Applied Probability, Vol.2, Academic Press, 1983, New York
[38] Hille E., and Phillips, R.S., Functional Analysis and Semi-groups, Amer. Math. Soc., 1957
[39] Hsieh, M., Hurvich, C.M., Soulier, P., asymptotics for duration-driven long range dependent process, sep., 2003, http://econwpa.wustl.edu:80/eps/em/papers/0412/0412009.pdf
[40] Ji, Y.,S., Fujino,T., Abe, S., Matsukata, J. and Asano, S., On the impact of time scales on tail behavior of long-range dependent internet traffic, http://
[41] Kasahara, S., Internet traffic modelling:Markovian approach to self-similar traffic and predictions of loss probability for finite queues, IEICE TRANS.COMMUN., VOL.E84-B, NO.8, AUGUST 2001
[42] Kallenberg, O., Foundations Of Modern Probability, Springer, 2001
[43] Kosten, L., Stochastic Theory of Service Systems, Pergamon Press Ltd., 1973
[44] Lorenz, E.N., The essence of chaos, The University of Washington Press, 1993
[45] Lasota, A., Mackey, M.C., Chaos, Fractals, and Noise, 2nd. Ed., Springer-Verlag, 1994
[46] Neuts
[47] Paxson V., and Floyd, S., Wide-area traffic: the failure of Poisson modeling, IEEE/ACM Trans. on Networking, 3, No.3, 1995, 226-244
[48] Pazy, A., semigroups of linear operators and applications to partial differential equations, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1983
[49] Pruthi, P., Erramilli, A., Heavy-tailed on/off source behavior and self-similar traffic, Proceedings of the ICC’95, June18-22, 1995
[50] Reuter, G.E.H., Denumerable Markov process and the Associate Semigroup on l, Acta. Math., 97(1957), 1-46
[51] Riedi, R., Crouse, M., Ribeiro, Baraiuk, V., R., A multifractal wavelet model with application to network traffic, IEEE Trans. Commun., Vol.43, No.,2/3/4, pp1566-1579, 1995
[52] Ross, S.M., Stochastic process, John Wiley & Sons, Inc., 1983
[53] Schmidli, H., An extension to the renewal theorem and an application to risk theory, The Annals of Applied Probability, 1997, Vol., No.1, 121-133
[54] D., Williams, On the Construction Problem for Markov chains, Zs. f. Wahrsch., 3, 1964
[55] Willinger, W., Leland, W.E., Taqqu, M.S., and Wilson, D.V., On the self-similar nature of Ethernet traffic, Proc ACM SIGCOMM 93, 1993
[56] Willinger, W., Paxson, V., Riedi R.L. and Taqqu, M.S., Long-Range dependent and network traffic
[57] K., Yosida, Functional Analysis, Springer, Berlin, 1965
[58] A highly efficient M/G/ model for generating self-similar traces, Proceedings of the 2002 Winter simulation Conference, Yucesan, E., Chen, C.H., Snowdon, J.L., and Charnes, J.M., eds.∞