SOLUTION OF STOCHASTIC DIFFERENTIAL EQUATIONS OF THE MODELS OF QUEUEING THEORY BY THE METHOD OF GENERATIONG FUNCTION

Ivanova Svetlana; Pavsky Valeriy

doi:doi:10.21603/2500-1418-2016-1-1-53-62

SOLUTION OF STOCHASTIC DIFFERENTIAL EQUATIONS OF THE MODELS OF QUEUEING THEORY BY THE METHOD OF GENERATIONG FUNCTION

Submit manuscript Download PDF
Text

To cite

Citations:

SOLUTION OF STOCHASTIC DIFFERENTIAL EQUATIONS OF THE MODELS OF QUEUEING THEORY BY THE METHOD OF GENERATIONG FUNCTION

Journal: SCIENCE EVOLUTION Volume 1 № 1 , 2016

Rubrics: MATHEMATICAL SCIENCES

Ivanova Svetlana ¹

Pavsky Valeriy ²

Author and publication information

Authors:

1. Kemerovo Institute of Food Science and Technology (University)

Russian Federation

2. Kemerovo Institute of Food Science and Technology (University)

Russian Federation

Type:

Article

DOI:

https://doi.org/10.21603/2500-1418-2016-1-1-53-62

Pages:

from 53 to 62

Status:

Published

Received:

27.06.2016

Accepted:

27.06.2016

Published:

27.06.2016

Subject area:

GRNTI 29.01 Общие вопросы физики
GRNTI 27.01 Общие вопросы математики
GRNTI 31.01 Общие вопросы химии
GRNTI 34.01 Общие вопросы биологии

Language:

English

Keywords:

the Queuing theory, systems of stochastic differential equations, generating (characteristic) function, probability distribution, moments, Markov process

Abstract and keywords

Abstract (English):
The object is mathematical models and their formalization by differential equation systems. The aim is to popularize stochastic models and differential equation systems which solution allows an analytical form. A model formulation and a process of finding a solution to equation systems are of interest. In the queueing theory many models are formalized by systems of linear differential equations with one or more parameters in which distribution of states of queueing systems are unknown functions. In such systems Markov processes are often grounding in the theory of differential equations construction; in a special case postulates of Poisson process are used. Analytical solution of equation systems exists but it is hard to find by traditional methods. In our study we offer a method which allows to find an analytical solution not only for probability distribution but also for moments of any order from one equation system. Description of procedure of differential equation generation for moments of random order varieties is presented. The method is based on the usage of generating (characteristic) functions. This method is effective because it allows to find solutions for moments (here it is expectation and variance) without complex probability calculations. It is especially important in empirical researches of systems that consist of many elements. For example, when we analyze function effectiveness of operating and designed scaling computing systems and supercomputers. Three models and their formalization by differential equation systems that correspond to stochastic processes and analytical solutions of diverse complexity are formulated. Connection between stochastic differential equations systems and their solutions with probability distributions that are classical in probability theory is shown.

Keywords:
the Queuing theory, systems of stochastic differential equations, generating (characteristic) function, probability distribution, moments, Markov process

Text

Publication text (PDF): Read Download

INTRODUCTION Mathematical modeling takes the leading position in researching and analysis of complex system functioning. Models which appear in theory of stochastic processes, theory of computer science, theoretical physics, engineering sciences, economics, and ecology are often formalized by linear differential equations. Usually such models are formulated from common grounds at the first approximation and reflect a common trend of real process development. Many of them are stochastic and they are effectively described by queueing theory methods that are connected with Markov process in which functions of time representing probability distributions are unknown [1-10]. Though analytical solutions exist, they are found by approximate methods. Often it is connected with absence of necessity to search for exact solutions because propose tasks that have no concern with mathematics are solved. In recent years significant results in development of calculations methods were achieved [11-13] but they refer to improvement of numerical algorithms. Though analytical solutions exist, they are usually found by approximate methods. In our article we give systems of analytical equations of diverse complexity, solutions of which are found with the usage of a generating function. All equation systems formalize models that are formulated by the authors in terms of queueing theory and are directly relevant to the theory of computer science [14-17], chemistry and biotechnology [18-23]. The aim of the research is a construction of such stochastic models which are formalized by differential equation systems that allow analytical solution and have practical importance. According to the aim stochastic models are developed and their analytical solutions of diverse complexity are obtained. Connection between differential equation systems and their solutions with probability distributions that are classical in probability theory is shown. MATERIALS AND METHODS Markov process. In terms of queueing theory queueing systems described by random process of Markov type with denumerable number of states k (beginning with zero) and postulates of Poisson process [24-26], whose unknown functions of time are probability distributionsare considered. Assume a queueing system consisting of finite number of states, . Time of system presence in every state is random and is described by exponential law of distribution. System transition from one state to another at a time is realized by a jump. Assumption about exponential law of distribution of time of system presence in every state is equivalent to fulfillment of the conditions of absence of aftereffects and ordinariness, and, if the parameter of the exponential law is fixed, then also of stationarity [27, 28]. The fulfillment of the conditions allows to construct a system of differential equations of motion of a point inside a system defines by graduated state graph, whose scheme depends on the object under study [29]. Let us denote through a possibility that at the point of time the system is in the state k. The process under consideration is formalized in the differential equation system which describes connection of possibilities that there is some number of units at the moment of time t, in a queueing system. Method of generating functions. The method of generating functions allows to reduce a system, consisting of arbitrary number of differential equations, for probability distribution of system presence in every state to one partial differential equation of a generating function with its following finding. Let us have probability distribution, , or any other sequence of functions. Let us note every member of this sequence by its multiplying by variable z to such degree that is equal to a sequential number of sequence members, then obtain the product and consider the series . (1) Considering that , the function is analytical in the circle . Function is called generating for distribution . The original function is reconstructed from the formula . (2) Further we will need linearityfunction and representation of a derived generating function [30]. Linearity of a generating function allows to bring differential equation system for to one equation in partial derivatives from with initial conditions and , . Principle of the method. The substitution of probability distribution of random variables for generating function leads to a recurrent system of differential equations from its moments. At the first step a generating function reduces an equation system from probability distributions to equation of a generating function. At the second step we express moments through a generating function. The third step allows to write the equation for the first moment by differentiation of equation of generating function. Second differentiation allows us to write the second moment with regard to the first and so one. With increase of moment orders we increase the number of equations. The complexity of calculations also increases because the result of every element depends on all previous ones [15]. If we differentiate an equation in partial derivatives of generating function with respect to variable z, we obtain ordinary differential equation for finding - moment of the first order (of expectation). For finding that is the central or initial moment of the order k we differentiate an equation in partial derivatives k times and after every differentiation we obtain an ordinary differential equation for finding a moment whose order corresponds with differentiation order. After k-multiple differentiation we obtain a system of ordinary differential equations of k order that reduces to , where a - const, is a k-order moment . Initial conditions take the form , , , , . Let us denote through an expectation of number of requirements that exist at a time t in some fixed state with a condition that at a time t = 0 they were in this state i, . We have , . (3) For variance corresponding to expectation we obtain . (4) Let us express and through generating function (1), differentiate it with respect to z and obtain . (5) Taking into account the expectation definition for random variables with denumerable number of states when z = 1 we obtain . (6) Differentiating (5) with respect to z we obtain . If z = 1 we obtain . (7) Noting that , with regard to (5) - (7) we obtain , final . (8) For finding of the k-order (initial or central) moment by differentiating k times the function with respect to z if z = 1 we obtain a polynomial of the form , . RESULTS AND DISCUSSION Model 1 formulation. There is a queueing system consisting of N unites. Each of them can be in one of two inconsistent states. Transition of arrival from one state to another and back satisfies Poisson postulates with intensities l and m, accordingly. We need to find a probability of the fact that at a time we obtain k arrivals in the first state. A model is formalized by a system with initial conditions , , , (10) and denotes a behavior of a process in a queueing system at any time . Let us call the system (9) a Bernoulli process. For possibilities a condition of standardization which is a model 1 consequence is satisfied , . (11) Formula (11) is also true for denumerable number of states of a queueing system, . Let us solve the system (9). By differentiating with respect to variables t and z we obtain ; , accordingly. By summing the first equation of the system (9) with the second multiplied by and the last multiplied by , we obtain . Thus, with made assumptions, the equation system (9) reduces to the following equation in partial derivatives [31, 14]: (12) A general equation solution (12) can be presented in the form , where , are characteristic’s equations, g is an arbitrary differential function. Let us solve the equation (12). For characteristics we have a system: , where , from which we take two equations: , . We find their solution by ordinary methods: , . Thus, , . Then the solution of the equation (12) will take the form (13) or . Taking initial conditions into consideration, that follows from (1) if t = 1, we obtain or . If t is arbitrary, is a function argument of g, thus, substituting y for this value, we obtain Taking into consideration (13) we have (14) Let us introduce the following notation (15) (16) while , . Then (14) with regard to (15), (16) may be written in the form . (17) Let us apply the formula (2). It should be noted that the function is a product of two functions. If , , then for finding from the formula (2) we can apply Leibniz formula [32] to the formula (17) Substituting in it corresponding differential functions , we obtain (18) With regard to (15), (16), we write finally , where . With zero initial conditions, at every fixed time t we have (19) In steady-state mode of operation with regard to equation irrespective to initial conditions we obtain =. (20) Formulas (19) at every fixed time and (20) are known as Bernoulli distribution. Then from (6) with regard to (17) we obtain expectation: Let us define in the equation (8) every summand separately with regard to (17): Let us substitute obtained expressions in the equation (8) Thus, the solution for (6) and (8) takes the form or, with regard to notation (15), (16), In a special case if I = 0, we obtain . For a steady-state mode we have It is evident that at every fixed time the formulas (19) and (20) are probability distributions, and also obtained moments with zero initial conditions and in steady-state mode refer to enumerative characters of Bernoulli distribution [23]. That is why the equation system (9) can be considered as formalization of the Bernoulli process with two parameters, digital number of states and continuous time [29]. Model 1 consequence. Let us simplify the model 1. Assume that arrivals come from a plentiful () source of intensity l and are served by intensity m with the same queue discipline and Poisson postulates. Then considering from the system (9) we obtain the equation system Let us introduce a generating function (1), with initial conditions , By applying it to the equation system we obtain a partial differential equation[1] By analogy with finding a solution of the partial differential equation (12) it is also possible to find solutions of this equation for probability distributions, expectation and variance. Let us give a differential equation system and solutions for expectation and variance With initial conditions , . The solution takes the form (21) All solutions are in a steady-state mode: probability distribution, expectation and variance are characteristics of Poisson distribution , and probability distribution and moments (21) at every fixed time and zero initial conditions are a Poisson process with two parameters formalized by the equation system of the consequence 1. Model 2. From a plentiful source a stream of arrivals comes on a queueing system with intensity l. Arrival k in a queueing system that arrived with other arrivals awaits inception of service. At arbitrary time service of all k arrivals starts without regard to their number in a queueing system with general intensity m. Let us find possibility of existing k arrivals at a time t in a queueing system, , The model is formalized by a differential equation system (22) with initial conditions (23) and normalization condition , Considering that the system (22) takes the form Let us introduce a function By multiplying an equation of k system by after adding equations to further elementary transformations we obtain a partial differential equation . (24) Differentiating the equation (24) with respect to variable z and taking into consideration (6) and (8) we obtain a system of ordinary differential equations (25) whose solution takes the form of For the solution of the system (22) with regard to (23) let us use the method of finding a solution of the partial differential equation (12). The procedure of finding a solution is rather difficult. Let us show the final result In a steady-state case from (26) we obtain (27) The formulas (26) with zero initial conditions and (27) are a famous geometrical distribution. Setting we obtain a famous geometrical distribution [25] of possibilities {}, . In a steady-state mode the solution of the system (25) takes the form , . The equation system (22) can be seen as a formalization of some Markov process with two parameters. In these models we demonstrated how to find a solution of equation systems with the usage of generating functions, and in this case we found solutions for moments with regard not to their definition, but a partial differential equation for a generating function. It helped us to find solutions for moments easier. When applied, the usage of possibilities for calculations, except for theoretical studies, is unreasonable because of its fewer informative value and greater inconvenience. In practical studies it is better to use moments. The use of generating functions is also effective because it is possible to find moments when probability distribution cannot be found or is found approximately. Let us give as an example a model in which an accurate solution can be obtained only for moments. The difficulty also discussed in the work [29] is that an accurate, even a steady-state solution is connected with finding roots of a polynomial numerically. Moreover, a partial differential equation contains even two unknowns. Model 3. A Poisson stream of arrivals with intensity a comes on a single-server queueing system. Each arrival undergoes several serving stages. The time of a service is subordinated by Erlang distribution [33] of n-order with a parameter m. When one service is complete the other service starts. Let us find expectation of number of arrivals in a system and its variance Model study. Let be a probability of a fact that at a time t in a queueing system exist k arrivals, , . A differential equation system takes the form [2]: (28) with initial conditions (29) and normalization condition (30) Let us introduce a generating function for solving the system (28) (31) Multiplying an equation k of the system (28) by and summing we obtain After the reduction of similar terms we obtain a linear equation . (32) It is possible to find a solution of the equation (32) using Laplace transformation, but it will be lengthy and of a little use in engineering calculations, that is why it will be difficult to find an original. Even in a steady-state mode its solution given in [29] is found by numerical methods. Let us find an accurate solution for expectation and variation by the method given in [14]. Considering that the model is related to the class [29], it is ergodic and a steady-state mode always exists. Let us introduce the following notation: and, besides, then the formula (32) takes the form (33) It follows from (31) that F(1) = 1 and, besides, because of analyticity F(z) in equation (33) a notation is to be a root of a numerator and denominator. Let us use these facts to find . If , then we have an uncertainty {0/0}, and by applying l'Hospital's rule to (33) we obtain an equality . After division of a numerator and denominator by , we eliminate and obtain . (34) Let z be an arbitrary notion characterizing a number of stages required for completion of service in a queueing system. Taking into consideration (6) and (8) in a steady-state mode а (35) Let us take a derivative of a generating function in (34), then After elementary transformations After calculating a second derivation we obtain Taking into consideration (35) we find Note, that, according to formulas (36), an average number of stages in queueing systems has been found. In order to find expectation and variance of a random variable x that characterizes a number of arrivals in a system with regard to moment’s properties, we obtain If then we obtain famous formulas [29] CONCLUSION On the example of models that describe queueing system processes we have analyzed solutions of differential systems where probability distributions are unknown functions. We have shown that the peculiarity of generating function application is the possibility to find not only unknown functions, but also moments. It is the advantage of the theory of probability and random processes over other mathematic theories. Solutions obtained in the analytical form allow to have more information on process researches than approximate or numerical methods. Model 1 shows that Poisson process is naturally obtained from Bernoulli process. Model 2 shows new possibilities for geometrical distribution application. Model 3shows how to find an accurate solution of integral characteristic (moments) without calculations of probability distribution. Presented models and their solutions are of an interest for researches and creators of fast computing facilities consisting of hundreds computational nodes. They are also useful for researches of wireless networks. They are applied to logistics, economics, and analysis of effectiveness of different companies functioning.

References

1. Li T. Analysis of explicit tau-leaping schemes for simulating chemically reacting systems. Multiscale modeling and simulation, 2007, vol. 6, no. 2, pp. 417-436.

2. Zhang D., Nastac L. Numerical modeling of the dispersion of ceramic nanoparticles during ultrasonic processing of aluminum-based nanocomposites. Journal of Materials Research and Technology, 2014, vol. 3, no. 4, pp. 296-302.

3. Paschalis A., Molnar P., Fatichi S., Burlando P. On temporal stochastic modeling of precipitation, nesting models across scales. Advances in Water Resources, 2014, vol. 63, pp. 152-166.

4. Niu, Y., Burrage, K., Zhang, C. Multi-scale approach for simulating time-delay biochemical reaction systems. IET Systems Biology, 2014, vol. 9, no. 1, pp. 31-38.

5. Babich O., Prosekov A.Yu., Dyshlyuk L.S., Ivanova S.A. Investigation of kinetic aspects of L-phenylanine ammonia-lyase production in pigmental yeast Kinetic aspects of L-phenylanine production. Chimica Oggi-Chemistry Today, 2015, vol. 33, no. 6, pp. 16-20.

6. Barbuti R., Bove P., Milazzo P., Pardini G. Minimal probabilistic P systems for modelling ecological systems. Theoretical Computer Science, 2015, vol. 608, no. 1, pp. 36-56.

7. Rieck C., Bück A., Tsotsas E. Stochastic Modelling of Particle Coating in Fluidized Beds. Procedia Engineering, 2015, vol. 102, pp. 996-1005.

8. Chan J.C.C., Grant A.L. Modeling energy price dynamics: GARCH versus stochastic volatility. Energy Economics, 2016, vol. 54, pp. 182-189.

9. Pesmazoglou I., Kempf A.M., Navarro-Martinez S. Stochastic modeling of particle aggregation. International Journal of Multiphase Flow, 2016, vol. 80, pp. 118-130.

10. Stratford D.S., Pollino C.A., Brown A.E. Modelling population responses to flow: The development of a generic fish population model. Environmental Modelling & Software, 2016, vol. 79, pp. 96-119.

11. MacNamara S., Burrage K. Stochastic modeling of naïve t cell homeostasis for competing clonotypes via the master equation. Multiscale modeling and simulation, 2010, vol. 8, no. 4, pp. 1325-1347.

12. Munsky B., Khammash M. The finite state projection algorithm for the solution of the chemical master equation. The Journal of chemical physics, 2006, vol. 124, no. 4, pp. 44-104.

13. Niu Y., Burrage K., Chen L. Modelling biochemical reaction systems by stochastic differential equations with reflection. Journal of Theoretical Biology, 2016, vol. 396, pp. 90-104.

14. Pavsky V.A., Pavsky K.V., Khoroshevsky V.G. Vychislenie pokazateley zhivuchesti raspredelennykh vychislitel'nykh sistem i osushchestvimosti resheniya zadach [Calculation of vitality metrics distributed computing systems and the feasibility of solving problems]. Iskusstvennyy intellekt [Artificial Intelligence], 2006, no. 4, pp. 28-34.

15. Khoroshevsky V.G., Pavsky V.A. Calculating the efficiency indices of distributed computer system functioning. Optoelectronics, Instrumentation and Data Processing, 2008, vol. 44, no. 2, pp. 95-104.

16. Pavsky V.A., Pavsky K.V. Stokhasticheskoe modelirovanie i otsenki razmera strukturnoy izbytochnosti masshtabiruemykh raspredelennykh vychislitel'nykh sistem [Stochastic modeling and estimation of the size of the structural redundancy scalable distributed computing systems]. Izvestiya YuFU. Tekhnicheskie nauki [Proceedings of the SFU. Engineering], 2014, no. 12, no. 161, pp. 66-73.

17. Pavsky V.A., Pavsky K.V. Stochastic simulation and analysis of the operation of computing systems with structural redundancy. Optoelectronics, instrumentation and data processing, 2014, vol. 50, no. 4, pp. 363-369.

18. Yustratov V.P., Pavskii V.A., Krasnova T.A., Ivanova S.A. Mathematical modeling of electrodialysis demineralization using a stochastic model. Theoretical foundations of chemical engineering, 2005, vol. 39, no. 3, pp. 259-262.

19. Pavsky V.A., Skolubovich Yu.L., Krasnova T.A. Modelirovanie protsessa ochistki prirodnykh i stochnykh vod [Modeling process of purification natural and waste waters]. Novosibirsk NSABU Publ., 2005. 144 p.

20. Ivanova S.A. Stokhasticheskie modeli tekhnologicheskikh protsessov pererabotki dispersnykh sistem obezzhirennogo moloka [Stochastic models of technological processes of processing of dispersions of skim milk]. Kemerovo KemTIPP Publ., 2010. 124 p.

21. Ivanova S.A., Pavsky V.A., Poplavskaya M.A., Novoselova M.V. Studying the biokinetics of pigmented yeast by stochastic methods. Food and Raw Materials, 2014, vol. 2, no. 1, pp. 17-21.

22. Ivanova S.A. Studying the foaming of protein solutions by stochastic methods. Food and Raw Materials, 2014, vol. 2, no. 2, pp. 140-146.

23. Ivanova S.A., Pavsky V.A. Stochastic modeling of protein solution foaming process. Theoretical foundations of chemical engineering, 2014, vol. 48, no. 6, pp. 848-854.

24. Saaty T. Elements of queueing theory with application. New York: Dover publications, 1961. 436 p.

25. Feller W. An introduction to probability theory and its applications. New York: Wiley interscience, 1968. 528 p.

26. Gnedenko V.E. Kurs teorii veroyatnostey [The course in probability theory]. Moscow: LKS Publ., 2007. 448 p.

27. Venttsel' E.S., Ovcharov L.A. Teoriya sluchaynykh protsessov i ee inzhenernye prilozheniya [The theory of random processes and its engineering applications]. Moscow: High School Publ., 2000. 480 p.

28. Gnedenko B.V., Kovalenko I.N. Vvedenie v teoriyu massovogo obsluzhivaniya [Introduction to queuing theory]. Moscow: Editorial URSS Publ., 2005. 400 p.

29. Kleinrock L. Queueing systems, volume 1. Theory. New York: Wiley interscience, 1975. 432 p.

30. Sveshchnikov A.G., Tikhonov A.N. Teoriya funktsii kompleksnogo peremennogo [The theory of functions of a complex variable]. Moscow: FIZMATLIT Publ., 2010. 336 p.

31. Pavsky V.A. Ob osushchestvimosti resheniya potoka prostykh zadachna odnorodnykh vychislitel'nykh sistemakh [On the feasibility of solving a task flow simple homogeneous computing systems]. Vychislitel'nye sistemy [Computational Systems], 1972, vol. 51, pp. 48-58.

32. Prabkhu N. Metody teorii massovogo obsluzhivaniya i upravleniya zapasami [Methods of queuing and inventory management]. Moscow: Editorial URSS Publ., 1984. 499 p.

33. Pavsky V.A., Pavsky K.V. Vychislenie momentov sluchaynykh velichin pri erlangovskom vremeni obsluzhivaniya [Calculation of moments of random variables with Erlang service time]. Materialy 13 mezhdunarodnoy nauchno - prakticheskoy konferentsii «Informatsionnye tekhnologii i matematicheskoe modelirovanie», ch.2 [Proceedings of the 13th international scientific - practical conference "Information Technologies and Mathematical Modeling", Part 2], Tomsk, TSU Publishing House, 2014, pp. 198-202.

This work is licensed under Creative Commons Attribution 4.0 International

Submit manuscript Download PDF
Text

To cite

Citations:

Confirmation

Регистрация