Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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'.

share|improve this question
    
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

1 Answer 1

up vote 10 down vote accepted

"Markov Chain Tree Theorem" is what you should look up: it says essentially that the stationary probability of a given state/vertex is given by the sum of the weights of all spanning trees rooted at that vertex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.