Exponential chains and generalized inverses: New approaches to the approximate and exact solution of Markov chain problems

Markov chains are considered with emphasis on the compution of exact and approximate stationary distributions and expected first passage times. First, generalized inverses are used to unify the computations involved with Markov chains. It is shown that any generalized inverse of the infinitesimal generator of a Markov chain can be used to find the exact stationary distribution and expected first passage times, as well as to compute the effects on these quantities by a perturbation of the infinitesimal generator. Next, because of the use in the literature of birth-death chains in various forms as approximations to chains which have been loosely termed nearly birth-death chains, there is a discussion of what might be a useful definition of a nearly birth-death chain. The experimental results of birth-death approximations of some chains arising from the slotted ALOHA are then presented. These lend some validity to approximating such chains with birth-death chains which match the local drift and variance at each internal state. The discussion of nearly birth-death chains leads to the discovery of a new class of chains, called exponential chains, which generalizes the birth-death chain by introducing two parameters in addition to the birth-death rates. Explicit formulae for the stationary distribution and expected first passage times are computed, and seen to be similar to those used for birth-death chains. It is pointed out that the computational ease and the additional two parameters could make exponential chains better for approximating Markov chains. An example is given where the exponential chains yield good approximations. Finally, exponential chains are used to improve bounds on the ratios of stationary probabilities of adjacent states which were originally developed by Szpankowski. The improvements are in the form of an existence theorem, and a possible first step for the computation of the improved bounds is given