Title :
Product Form Approximations for Communicating Markov Processes
Author_Institution :
Dept. of Comput. Sci., Tech. Univ. Dortmund, Dortmund
Abstract :
Exact product form solutions have been found for several classes of stochastic models including some networks of stochastic automata or communicating Markov chains. In this paper a theory of approximate product forms is presented. The idea is to define an approximate product form solution as a Kronecker product of vectors that minimizes the Euclidean norm of the residual vector for arbitrary networks of communicating Markov processes. By adopting ideas from numerical analysis to approximate a matrix by a sum of Kronecker products of small matrices, higher order product forms that result in better approximations are defined.The paper presents the general theory of product form approximations for communicating Markov processes and it introduces first algorithms to compute product form solutions. By means of some examples it is shown that the approach allows one to compute approximations with increasing accuracy by increasing the order of the product form.
Keywords :
Markov processes; approximation theory; matrix algebra; numerical analysis; stochastic automata; vectors; Euclidean norm; Kronecker product; Markov process communication; arbitrary networks; matrix approximation; numerical analysis; product form approximations; residual vector; stochastic automata; Algebra; Automata; Computer science; Distributed computing; Equations; Markov processes; Numerical analysis; Petri nets; Stochastic processes; Stochastic systems; Approximate Analysis; Product Form; Stochastic Automata Networks;
Conference_Titel :
Quantitative Evaluation of Systems, 2008. QEST '08. Fifth International Conference on
Conference_Location :
St. Malo
Print_ISBN :
978-0-7695-3360-5
DOI :
10.1109/QEST.2008.23