A Generalized Recursive Technique for Finite Markov Processes
Tao Yang, Morton J. M. Posner, James G. C. Templeton · 2021
In this paper, 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 , …, 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.