4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you sure about the statement in the second paragraph? $\endgroup$
    – Felix Goldberg
    Commented Jul 6, 2012 at 10:44
  • $\begingroup$ 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. $\endgroup$
    – Erik Aas
    Commented Jul 6, 2012 at 11:01
  • $\begingroup$ (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.) $\endgroup$
    – Erik Aas
    Commented Jul 6, 2012 at 11:02

1 Answer 1

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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