The spanning tree structure of stationary Markov Chains

Abstract

A theorem is given that relates the directed spanning tree structure of the associated state graph of homogeneous Markov Chains with their stationary probabilities when these exist. It is demonstrated that this theorem applies to both discrete and continuous parameter cases.In tutorial fashion, small probabilities recursively for general Markov Chains is discussed. It is shown that the graphs of some queuing formulations are particularly well suited to this process on account of their regular structure. The resulting algorithms are efficient and easily incorporate arbitrary state transition relationships, and some sensitivity analyses are automatic. An example is included that illustrates this method, and some interesting open question formulated.