ISSN:
1070-5325
Keywords:
Continuous and discrete-time Markov chains
;
P-cyclic graph structure
;
Reduced schemes
;
Numerical solution methods
;
Engineering
;
Engineering General
Source:
Wiley InterScience Backfile Collection 1832-2000
Topics:
Mathematics
Notes:
Markov chains with periodic graphs arise frequently in a wide range of modelling experiments. Application areas range from flexible manufacturing systems in which pallets are treated in a cyclic manner to computer communication networks. The primary goal of this paper is to show how advantage may be taken of this property to reduce the amount of computer memory and computation time needed to compute stationary probability vectors of periodic Markov chains. After reviewing some basic properties of Markov chains whose associated graph is periodic, we introduce a ‘reduced scheme’ in which only a subset of the probability vector need be computed. We consider the effect of the application of both direct and iterative methods to the original Markov chain (permuted to normal periodic form) as well as to the reduced system. We show how the periodicity of the Markov chain may be efficiently computed as the chain itself is being generated. Finally, some numerical experiments to illustrate the theory, are presented.
Additional Material:
3 Ill.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1002/nla.1680010305