There is an explicit formula for the equilibrium distribution of a continuous-time Markov chain in terms of weighted in-trees [20]. To describe this formula, we first define a directed graph on the states 1,...,n of the chain. The vertices of the graph are the states of the chain, and the arcs of the graph are ordered pairs of states (i, j) having transition rates λij > 0.

If it is possible to reach some designated state k from every other state i, then a unique equilibrium distribution π = (π1,...,πn) exists for the chain. Note that this reachability condition is weaker than requiring that all states communicate.

The equilibrium distribution is characterized by defining certain subgraphs called in-trees. An in-tree Ti to state i is a subgraph having n − 1 arcs and connecting each vertex j = i to i by some directed path. Ignoring orientations, an in-tree is graphically a tree; observing orientations, all paths lead to i. The weight w(Ti) associated with the in-tree Ti is the product of the transition rates λjk labeling the various arcs (j, k) of the in-tree. For instance, in the nucleotide substitution chain, one in-tree to A has arcs (G,A), (C,A), and (T,C).

Its associated weight is δσ.

In general, the equilibrium distribution is given by

πi =



Ti w(Ti)



j



Tj w(Tj )

. (10.17)

The reachability condition implies that in-trees to state k exist and consequently that the denominator in (10.17) is positive. The value of the in-tree formula (10.17) is limited by the fact that in a Markov chain with n states there can be as many as nn−2 in-trees to a given state. Thus, in the nucleotide substitution model, there are 44−2 = 16 in-trees to each state and 64 in-trees in all. If you are undeterred by this revelation, then use formula (10.17) to find the equilibrium distribution of the nucleotide substitution chain of Section 10.5 when detailed balance is not assumed. Your answer should match the distribution appearing in Problem 15.