Row-Continuous Finite Markov Chains, Structure and Algorithms

摘要

For any finite bivariate Markov chain J(t), N(t) on state space for which row-continuity is present, i.e., N(t) changes by at most one at transitions, the ergodic distribution and mean passage times may be found by a simple algorithm. Related structure will be described. The procedure is based on probabilistic insights associated with semi-Markov processes and birth-death processes. The resulting algorithms enable efficient treatment of chains with as many as 5000 = 50 x 100 states or more. Such bivariate chains are of importance to countless applied models in congestion theory, inventory theory, computer design, etc. The algorithm developed is to be used as a basis for calculating the distribution of the maximum of certain stationary meteorological processes over a specified interval.