A Graph Theoretic Formula for the Steady State Distribution of Finite Markov Processes

This paper presents a formula which expresses the solution to the steady-state equations of a finite irreducible Markov process in terms of subgraphs of the transition diagram of the process. The formula is similar in spirit to well-known flowgraph formulas, but possesses several unique advantages. The formula is the same whether the process is discrete or continuous in time; it is efficient in the sense that no cancellation of terms can occur (it is a simple sum of positive terms); and it is both conceptually and computationally simple. Because these advantages are gained by exploiting properties of Markov processes, the formula is not applicable to linear equations in general, as are the flowgraph methods. The paper states and proves the theorem for both the discrete and continuous cases, gives examples of each, and cites computational experience with the formula.