zbMATH — the first resource for mathematics

A generalized recursive technique for finite Markov processes. (English) Zbl 0736.60068
Numerical solution of Markov chains, Pap. Workshop 1990, Probab., Pure Appl. 8, 203-221 (1991).
Summary: [For the entire collection see Zbl 0733.00019.]
The concept of the \(i\)-th order recursive computation for state probabilities of finite Markov processes is introduced. As a special case, the conventional recursive computation of Markov processes turns out to be the first-order recursive computation. Structures of Markov processes are systematically analyzed and the set of all finite Markov processes is partitioned according to their structures into classes \(M_ 1,M_ 2,\dots,\) etc. It is shown that any Markov process in \(M_ i\) can be evaluated with an \(i\)-th order recursive computation whose complexity is \(O(2^{i-1}n)\), where \(n\) is the number of states in the process. Examples and comparisons with some other techniques are also presented.
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
65C99 Probabilistic methods, stochastic differential equations