论文部分内容阅读
Abstract: The paper considers the problem of representing non-Markovian systems that evolve stochastically over time. It is often necessary to use approximations in the case the system is non-Markovian. Phase type distribution is by now indispensable tool in creation of stochastic system models. The paper suggests a method and software for evaluating stochastic systems approximations by Markov chains with continuous time and countable state space. The performance of a system is described in the event language used for generating the set of states and transition matrix between them. The example of a numerical model is presented.
Key words: Non-Markovian system approximation, phase type distribution, Markov chain, numerical model.
1. Introduction
A problem in system modeling having a wide range of important practical applications arises when the system is inherently stochastic and complete statistical description is not known. In order to evaluate system performance, a mathematical model must be developed. As the system is random in nature, a statistically based model is required.
Stochastic system models are often based on continuous-time Markov processes. Markov chains are commonly used for stochastic systems modeling.
However, some important aspects of system behavior cannot be easily captured in a Markov model. Very often the life-times distributions connected with a system are simply not exponential. For example, electronic component failure times often approximately follow a Weibull or lognormal distribution [1]. When an exponential distribution is both unrealistic and unsatisfactory for representing life-time distribution, then the usual approach is to use the “method of (exponential) stages” [2-6]. This method is both general and compatible with definition of Markov processes. It is general in what the authors can represent arbitrary distributions arbitrary closely. It is compatible with Markov processes because the only memory introduced is the distribution stage to accommodate this additional memory the authors refine their state definition.
It is known that creation of analytical models requires large efforts. Use of numerical methods permits to create models for a wider class of systems. The process of creating numerical models for systems described by Markov chains consists of the following stages: (1) definition of the state of a system; (2) definition of the set of events that can occur in the system; (3) generating the states of the system and infinitesimal generator matrix; (4) creating equations describing Markov chain; (5) computation of stationary probabilities of Markov chain; (6) computation of the performance measures of the system. The most difficult stages are obtaining the set of all the possible states of a system and transition matrix between them. A method for automatic construction of numerical models for systems described by Markov chains with a countable space of states and continuous time is proposed in the paper. To construct a model, it is needed to describe the performance of a stochastic system in the event language [7-9]. It allows automating some stages of the model. The created software in C++ generates the set of possible states, the matrix of transitions among states, constructs and solves equilibrium equations to find steady state probabilities. The paper is organized as follows: Section 2 introduces the description of the behavior of a stochastic system; section 3 is given the example; section 4 presents conclusions.
References
[1] D. Klinger, Y. Niekada, M. Menendez (Eds.), AT&T Reliability Manual, Van Nostrand Rheinhold, 1990.
[2] W.J. Stewart, Probability, Markov chains, queues, and simulation, Princeton University Press, 2009.
[3] T. Osogami, M. Harchol-Balter, Necessary and sufficient conditions for representing general distributions by Coxians, School of Computer Science, Carnegie Mellon University, CMU-CS-02-178, 2003.
[4] S. Asmussen, Applied Probability and Queues, Springer-Verlag, New York, 2003.
[5] M.A. Johnson, An empirical study of queuing approximations based on phase-type distributions, Commun. Statist.-Stochastic Models 9 (4) (1993) 531-561.
[6] M. Bladt, M.F. Neuts, Matrix-exponential distributions: Calculus and inerpretations via flows, Commun. Statist.-Stochastic Models 51 (1) (2003) 113-124.
[7] H. Pranevicius, E. Valakevicius, Numerical models for systems represented by Markovian processes, Kaunas, Technologija, 1996.
[8] E. Valakevicius, H. Pranevicius, An algorithm for creating Markovian models of complex system, in: Proceedings of the 12th World Multi-Conference on Systemics, Cybernetics and Informatics, Orlando, USA, June-July 2008, pp. 258-262.
[9] G. Mickevi?ius, E. Valakevi?ius, Modelling of non-Markovian queuing systems, Technological and Economic Development of Economy XII (4) (2006) 295-300.
[10] D.R. Cox, A use of complex probabilities in the theory of stochastic process, Mathematical Proceedings of the Cambridge Philosophical Society 51 (1955) 313-319.
Key words: Non-Markovian system approximation, phase type distribution, Markov chain, numerical model.
1. Introduction
A problem in system modeling having a wide range of important practical applications arises when the system is inherently stochastic and complete statistical description is not known. In order to evaluate system performance, a mathematical model must be developed. As the system is random in nature, a statistically based model is required.
Stochastic system models are often based on continuous-time Markov processes. Markov chains are commonly used for stochastic systems modeling.
However, some important aspects of system behavior cannot be easily captured in a Markov model. Very often the life-times distributions connected with a system are simply not exponential. For example, electronic component failure times often approximately follow a Weibull or lognormal distribution [1]. When an exponential distribution is both unrealistic and unsatisfactory for representing life-time distribution, then the usual approach is to use the “method of (exponential) stages” [2-6]. This method is both general and compatible with definition of Markov processes. It is general in what the authors can represent arbitrary distributions arbitrary closely. It is compatible with Markov processes because the only memory introduced is the distribution stage to accommodate this additional memory the authors refine their state definition.
It is known that creation of analytical models requires large efforts. Use of numerical methods permits to create models for a wider class of systems. The process of creating numerical models for systems described by Markov chains consists of the following stages: (1) definition of the state of a system; (2) definition of the set of events that can occur in the system; (3) generating the states of the system and infinitesimal generator matrix; (4) creating equations describing Markov chain; (5) computation of stationary probabilities of Markov chain; (6) computation of the performance measures of the system. The most difficult stages are obtaining the set of all the possible states of a system and transition matrix between them. A method for automatic construction of numerical models for systems described by Markov chains with a countable space of states and continuous time is proposed in the paper. To construct a model, it is needed to describe the performance of a stochastic system in the event language [7-9]. It allows automating some stages of the model. The created software in C++ generates the set of possible states, the matrix of transitions among states, constructs and solves equilibrium equations to find steady state probabilities. The paper is organized as follows: Section 2 introduces the description of the behavior of a stochastic system; section 3 is given the example; section 4 presents conclusions.
References
[1] D. Klinger, Y. Niekada, M. Menendez (Eds.), AT&T Reliability Manual, Van Nostrand Rheinhold, 1990.
[2] W.J. Stewart, Probability, Markov chains, queues, and simulation, Princeton University Press, 2009.
[3] T. Osogami, M. Harchol-Balter, Necessary and sufficient conditions for representing general distributions by Coxians, School of Computer Science, Carnegie Mellon University, CMU-CS-02-178, 2003.
[4] S. Asmussen, Applied Probability and Queues, Springer-Verlag, New York, 2003.
[5] M.A. Johnson, An empirical study of queuing approximations based on phase-type distributions, Commun. Statist.-Stochastic Models 9 (4) (1993) 531-561.
[6] M. Bladt, M.F. Neuts, Matrix-exponential distributions: Calculus and inerpretations via flows, Commun. Statist.-Stochastic Models 51 (1) (2003) 113-124.
[7] H. Pranevicius, E. Valakevicius, Numerical models for systems represented by Markovian processes, Kaunas, Technologija, 1996.
[8] E. Valakevicius, H. Pranevicius, An algorithm for creating Markovian models of complex system, in: Proceedings of the 12th World Multi-Conference on Systemics, Cybernetics and Informatics, Orlando, USA, June-July 2008, pp. 258-262.
[9] G. Mickevi?ius, E. Valakevi?ius, Modelling of non-Markovian queuing systems, Technological and Economic Development of Economy XII (4) (2006) 295-300.
[10] D.R. Cox, A use of complex probabilities in the theory of stochastic process, Mathematical Proceedings of the Cambridge Philosophical Society 51 (1955) 313-319.