Combinatorial descriptions of the stationary distribution of a Markov chain

When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible.

If the Markov chain happens to be equivalent to an "undirected Markov chain", i.e. for each directed arc (u,v) with weight w there is an arc (v,u) with same weight w, then it is easy to characterize the stationary distribution directly in terms of the graph; the stationary distribution at a vertex v is proportional to the out-degree (which in this case is half the total degree) of v.

However I know of no such direct description of the stationary distribution in terms of the graph of a Markov chain that does not come from an undirected graph (except possibly for time-reversible chains, but this is a very special special case). My question is: are there any such descriptions?

This is of course a bit vague(since the stationary distribution clearly depends only on the graph) but I hope it is not too vague.

I would not expect an as easy description as in the undirected case (where it suffices to look in a neighbourhood of radius 1 to find the probability of any vertex), but it seems reasonable that there could be a description involving, say, all trees rooted at the vertex.

This seems not to be treated in standard texts on Markov chains (correct me if wrong), where usually most effort is spent on proving existence, estimating speed of convergence, and the underlying graph is considered as 'auxilliary'.

• Are you sure about the statement in the second paragraph? – Felix Goldberg Jul 6 '12 at 10:44
• Felix: yes. It is easy to check that letting p(v) = degree(v) / (sum of all degrees of vertices) satisfies the equation A*p = p where A is the transition matrix in this case. This occurs in many places in the literature, for example in Lovasz' notes on random walks in graphs. – Erik Aas Jul 6 '12 at 11:01
• (well I don't even need to scale p(v) to be integers for Ap = p to hold - but the space of solutions is 1-dimensional and contains the stationary distribution.) – Erik Aas Jul 6 '12 at 11:02