Well-posed Problems For Density Evolution Equations In Stochastic Models

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₀ 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¹ 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.